CSCI 3300
Spring 2010
Exercises for Quiz 5

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

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

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

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

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

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

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

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

9. What is log₂(32)?

   Answer

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

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

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

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

14. Type Node is shown at the bottom of the page. It is used as the node type for binary search trees.

    Assume that function insert(x,t) is available to you, where insert(x,t) inserts x into binary search tree t, modifying t.

    Write a definition of function insertAll(s,t), which takes two binary search trees s and t and inserts all members of tree s into tree t.

    Answer