Balanced Trees
Red-Black trees

Web Exercises

1. Given a sorted sequence of keys, describe how to construct a red-black BST that contains them in linear time.
2. Suppose that you do a search in a red-black BST that terminates unsuccessfully after following 20 links from the root. Fill in the blanks below with the best (integer) bounds that you can infer from this fact about any unsuccessful search
   • Must follow at least ______ links from the root
   • Need follow at most _______ links from the root
3. With 1 bit per node we can represent 2-, 3-, and 4-nodes. How many bits would we need to represent 5-, 6-, 7-, and 8-nodes.
4. Substring reversing. Given a string of length N, support the following operations: select(i) = get the ith character, and reverse(i, j) = reverse the substring from i to j.Solution sketch. Maintain the string in a balanced search tree, where each node records the subtree count and a reverse bit (that interchanges the role of the left and right children if there are an odd number of reverse bits on the path from the root to the node). To implement select(i), do a binary search starting at the root, using the subtree counts and reverse bits. To implement reverse(i, j), split the BST at select(i) and select(j) to form three BSTs, reverse the bit of the middle BST, and join them back together using a join operation. Maintain the subtree counts and reverse bits when rotating.
5. Memory of a BST. What is the memory usage of a BST and RedBlackBST and TreeMap?Solution. MemoryOfBSTs.java.
6. Randomized BST. Program RandomizedBST.java implements a randomized BST, including deletion. Expected O(log N) performance per operations. Expectation depends only on the randomness in the algorithm; it does not depend on the input distribution. Must store subtree count field in each node; generates O(log N) random numbers per insert.Proposition. Tree has same distribution as if the keys were inserted in random order.
7. Join. Write a function that takes two randomized BSTs as input and returns a third randomized BST which contains the union of the elements in the two BSTs. Assume no duplicates.
8. Splay BST. Program SplayBST.java implements a splay tree.
9. Randomized queue. Implement a RandomizedQueue.java so that all operations take logarithmic time in the worst case.
10. Red-black BST with many updates. When performing a put() with a key that is already in a red-black BST, our RedBlackBST.java performs many unnecessary calls to isRed() and size(). Optimize the code so that these calls are skipped in such situations.