1 2 3 4 5 6 7 8

a. A binary search tree

1


1
  2


1
  2
    3


1
  2
    3
      4


1
  2
    3
      4
        5


1
  2
    3
      4
        5
          6


1
  2
    3
      4
        5
          6
            7


1
  2
    3
      4
        5
          6
            7
              8


b. An AVL tree

1


1
  2


  2
1   3


  2
1   3
      4


   2
1     4
    3   5


      4
  2       5
1   3       6


      4
  2       6
1   3   5   7


      4
  2       6
1   3   5   7
              8


c. A red-black tree

1B


1B
   2R


   2B
1R    3R


   2B
1B    3B
         4R


     2B
1B        4B
       3R    5R


     2B
1B        4R
       3B    5B
                6R


       2B
1B            4R
         3B        6B
                5R    7R


          4B
   2R            6R
1B    3B      5B    7B
                       8R