2 1 4 5 9 3 6 7

a. A binary search tree

2


  2
1


  2
1   4


  2
1   4
      5


  2
1   4
      5
        9


    2
1       4
      3   5
            9


    2
1       4
      3   5
            9
          6


    2
1       4
      3   5
            9
          6
            7

b. A AVL tree

2


  2
1


  2
1   4


  2
1   4
      5


    2
1       5
      4   9


      4
  2       5
1   3       9


      4
  2       6
1   3   5   9


       4
  2         6
1   3    5     9
             7

c. A red-black tree

2B


    2B
1R


    2B
1R      4R


    2B
1B      4B
            5R


    2B
1B      5B
      4R  9R


     2B
1B        5R
       4B    9B
     3R


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


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