CSCI 3300
Spring 2009
Exercises for Quiz 11

1. Which of the following is true about log₂(500)?

   1. 6 < log₂(500) < 7
   2. 8 < log₂(500) < 9
   3. 10 < log₂(500) < 11
   4. 250 < log₂(500) < 251
   5. 499 < log₂(500) < 501

   Answer

2. What is log₂₍₃₂₎?

   Answer

3. To within a constant factor, how much time does it take to insert a value into a height-balanced binary search tree that has n values in it already, in the worst case?

   Answer

4. To within a constant factor, how much time does it take to remove a value from a height-balanced binary search tree that has n values in it, in the worst case?

   Answer

5. Does the height-balancing algorithm based on single and double rotations always keep a tree height-balanced, or are there some rare sequences of insertions and removals that can cause the tree to become non-height-balanced?

   Answer

6. If you insert 20 into the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?

   

   Answer

7. If you insert 26 into the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?

   

   Answer

8. If you insert 27 into the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?

   

   Answer

9. If you insert 27 into the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?

   

   Answer

10. If you remove 8 from the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?

    

    Answer

11. If you remove 40 from the following binary search tree using the algorithm that keeps the tree height-balanced by doing rotations, what tree do you get?

    

    Answer