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