Balanced Trees
Red-Black BST
The insertion algorithm for 2-3 trees just described is not difficult to understand. We consider a simple representation known as a red-black BST that leads to a natural implementation.
- Encoding 3-nodes. The basic idea behind red-black BSTs is to encode 2-3 trees by starting with standard BSTs (which are made up of 2-nodes) and adding extra information to encode 3-nodes. We think of the links as being of two different types: red links, which bind together two 2-nodes to represent 3-nodes, and black links, which bind together the 2-3 tree. Specifically, we represent 3-nodes as two 2-nodes connected by a single red link that leans left. We refer to BSTs that represent 2-3 trees in this way as red-black BSTs.One advantage of using such a representation is that it allows us to use our get() code for standard BST search without modification.
- A 1-1 correspondence. Given any 2-3 tree, we can immediately derive a corresponding red-black BST, just by converting each node as specified. Conversely, if we draw the red links horizontally in a red-black BST, all of the null links are the same distance from the root, and if we then collapse together the nodes connected by red links, the result is a 2-3 tree.
- Color representation. Since each node is pointed to by precisely one link (from its parent), we encode the color of links in nodes, by adding a boolean instance variable color to our Node data type, which is true if the link from the parent is red and false if it is black. By convention, null links are black.
- Rotations. The implementation that we will consider might allow right-leaning red links or two red-links in a row during an operation, but it always corrects these conditions before completion, through judicious use of an operation called rotation that switches orientation of red links. First, suppose that we have a right-leaning red link that needs to be rotated to lean to the left. This operation is called a left rotation. Implementing a right rotation that converts a left-leaning red link to a right-leaning one amounts to the same code, with left and right interchanged.
- Flipping colors. The implementation that we will consider might also allow a black parent to have two red children. The color flip operation flips the colors of the the two red children to black and the color of the black parent to red.
- Insert into a single 2-node.
- Insert into a 2-node at the bottom.
- Insert into a tree with two keys (in a 3-node).
- Keeping the root black.
- Insert into a 3-node at the bottom.
- Passing a red link up the tree.
Implementation.
Program RedBlackBST.java implements a left-leaning red-black BST. Program RedBlackLiteBST.java is a simpler version that only implement put, get, and contains.
Deletion.
Proposition.
The height of a red-blackBST with N nodes is no more than 2 lg N.
Proposition.
In a red-black BST, the following operations take logarithmic time in the worst case: search, insertion, finding the minimum, finding the maximum, floor, ceiling, rank, select, delete the minimum, delete the maximum, delete, and range count.
Property.
The average length of a path from the root to a node in a red-black BST with N nodes is ~1.00 lg N.
Visualization.
Insert 255 keys in a red-black BST in random order.
Your browser can not display this movie.
Be sure that Javascript is enabled and that you have Flash 9.0.124 or better.
Exercises
- Which of the follow are legal balanced red-black BSTs?
Solution. (iii) and (iv) only. (i) is not balanced, (ii) is not in symmetric order or balanced.
- True or false: If you insert keys in increasing order into a red-black BST, the tree height is monotonically increasing.Solution. True, see the next question.
- Draw the red-black BST that results when you insert letters A through K in order into an initially empty red-black BST. Then, describe what happens in general when red-black BSTs are built by inserting keys in ascending order.
Insert 255 keys in a red-black BST in ascending order.
Your browser can not display this movie.
Be sure that Javascript is enabled and that you have Flash 9.0.124 or better.
- Answer the previous two questions for the case when the keys are inserted in descending order.Solution. False.
Insert 255 keys in a red-black BST in descending order.
Your browser can not display this movie.
Be sure that Javascript is enabled and that you have Flash 9.0.124 or better.
- Create a test client TestRedBlackBST.java.
Creative Problems
- Certification. Add to RedBlackBST.java a method is23() to check that no node is connected to two red links and that there are no right-leaning red links. Add a method isBalanced() to check that all paths from the root to a null link have the same number of black links. Combine these methods with isBST() to create a method isRedBlackBST() that checks that the tree is a BST and that it satisfies these two conditions.
- Fundamental theorem of rotations. Show that any BST can be transformed into any other BST on the same set of keys by a sequence of left and right rotations.Solution sketch: rotate the smallest key in the first BST to the root along the leftward spine; then recur with the resulting right subtree until you have a tree of height N (with every left link null). Do the same with the second BST. Remark: it is unknown whether there exists a polynomial-time algorithm for determining the minimum number of rotations needed to transform one BST into the other (even though the rotation distance is at most 2N – 6 for BSTs with at least 11 nodes).
- Delete the minimum. Implement the deleteMin() operation for RedBlackBST.java by maintaining the correspondence with the transformations given in the text for moving down the left spine of the tree while maintaining the invariant that the current node is not a 2-node.
- Delete the maximum. Implement the deleteMax() operation for RedBlackBST.java. Note that the transformations involved differ slightly from those in the previous exercise because red links are left-leaning.
- Delete. Implement the delete() operation for RedBlackBST.java, combining the methods of the previous two exercises with the delete()operation for BSTs.
Web Exercises
- Given a sorted sequence of keys, describe how to construct a red-black BST that contains them in linear time.
- 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
- 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.
- 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.
- Memory of a BST. What is the memory usage of a BST and RedBlackBST and TreeMap?Solution. MemoryOfBSTs.java.
- 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.
- 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.
- Splay BST. Program SplayBST.java implements a splay tree.
- Randomized queue. Implement a RandomizedQueue.java so that all operations take logarithmic time in the worst case.
- 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.
