CSCI 3300
Fall 2009
Exercises for Quiz 8

Some of these problems use the following type, Node.

struct Node
{
  int item;
  Node* left;
  Node* right;
  Node(int i, Node* L, Node* R)
  {
    item = i;
    left = L;
    right = R;
  }
};

1. Write a function that writes all of the numbers in a binary search tree in ascending order on the standard output, one number per line. The function takes a parameter of type const Node*, pointing to the tree, and has a void return type.

   Answer

2. Write a function to return the largest number in a binary search tree. There should be one parameter, of type const Node*, pointing to the tree. Assume that the tree is nonempty.

   Answer

3. If you insert 62 into the following binary search tree, using the basic algorithm that does not rebalance, what tree do you get?

   

   Answer

4. If you insert 26 into the following binary search tree, without rebalancing, what tree do you get?

   

   Answer

5. 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

6. If you insert 27 into the following binary search tree, without rebalancing, what tree do you get?

   

   Answer

7. 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

8. If you remove 40 from the following binary search tree using the algorithm discussed in class, without rebalancing, what binary search tree do you get?

   

   Answer

9. 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

10. If you remove 60 from the following binary search tree using the algorithm discussed in class, without rebalancing, what binary search tree do you get?

    

    Answer

11. 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

12. 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

13. 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

14. 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

15. What is log₂(32)?

    Answer

16. 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

17. 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

18. 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