red-black trees

Learning objectives: Show understanding of red-black trees, a common data structure for efficiently implementing search Write code that correctly manipulates trees Analyze the complexity of an operation on balanced trees (This is adapted from Problem 14-2 in Introduction to Algorithms by Cormen, Leiserson, and Rivest (first edition), pages 278-279.) I recommend reviewing the materials from Week 13, Tuesday: Balanced Trees before you attempt this problem. Your task is to implement the following operation on red-black trees: public void join(Key k, Value v, RedBlackBST t) { assert (max().compareTo(k) != 1); // k must be >= all keys in this assert(k.compareTo(t.min()) != -1; // k must be <= all keys in t /* If N == size() + t.size(), then with ~lg(N) comparisons, make this tree include v and all the keys and values in t. Both t and this may be mutated. */ } Example call: RedBlackBST t1 = // initialize t1 here RedBlackBST t2 = // initialize t2 here // Make sure that all the keys in t1 are = 29 t1.join(29, "whatever", t2); // after join() returns, t1 will contain all the original keys from t1; plus 29; // plus all the keys from t2 Definition: Black height Black height is defined as the number of black links from the root of the tree to any leaf. For example: IMG_2737.jpg This is a tree whose black height is 4. Its left child, which is black, has black height 3. For example, the path consisting of the nodes 26, 17, 14, 10, 7, and 3 contains four black links. The black link from a leaf (such as 3) to null counts as a black link. Example The following examples show what join() does: IMG_2720.jpg NOTE: the picture above is slightly wrong -- the 29 node should be red, not black. A "fixup" pass has to be applied, because the joined tree has a right-leaning red node. This pass applies a rotateLeft operation, and then sets the root's color to be black: IMG_2736.jpg In the top half of the first page, st1 and t2 are shown before calling: st1.join(29, "whatever", t2); st1's black height is 3 and t2's black height is 2. join() needs to find a node, y, within st1 such that y's black height is 2 and y's key is as big as possible. That node is 27, circled in pink in the bottom half of the page. join() makes a new node containing k, makes y the left child of k, and makes t2 the right child of k. As an exercise, it's worth figuring out: why this operation is guaranteed to create a valid binary search tree (assuming st1 and t2 were both valid red-black trees) why this operation is guaranteed to uphold all of the red-black tree properties... ...assuming that the correct color is chosen for the node with key k. (What color is that?) And assuming that a "fixup" step is performed after splicing the new tree rooted at k into st1. (What is the "fixup" step?) Required Strategy The RedBlackBST class has been modified for you to include a new instance variable that denotes the black height of this red-black tree. Right now, the value of blackHeight is always 0. You need to figure out what code to modify so that it correctly reflects the black height of the tree. private static int blackHeight; You only need to modify the RedBlackBST class. You do not need to modify the Node inner class. Hint: The isBalanced() method computes the black height dynamically, but there's still work involved in keeping this instance variable consistent after insertions or deletions. Hint: When put() is called, where are all the locations in the code where the black height of the tree could change? The answer will tell you where to add code to change the blackHeight instance variable. Hint: Ask yourself the same question about deletion (note that there are three different deletion methods). While descending through a tree, you can determine the black height of each node in constant time. I've added two new methods to the RedBlackBST class for you. Explain how to fill in the missing code in these methods. Hint: use recursion. private Node findBlackNodeWithLargestKey(int blackHeight) { // Returns a black node whose black height is blackHeight, // and has the largest possible key of all such nodes } private Node findBlackNodeWithSmallestKey(int blackHeight) { // Returns a black node whose black height is blackHeight, // and has the smallest possible key of all such nodes } Suppose y is any node and Ty is the subtree rooted at y. Describe how you can replace Ty with a new tree T3 that contains all the keys and values from Ty, as well as k and v, as well as all the keys and values from t, so that T3 is still a binary search tree. This is the core of what the join() method does. What color should the new node for k and v be so that the red-black-tree properties are still true? Describe how to make these properties be true in ~lg(n) time. Argue that the running time of your new join() method is ~lg(n). (Your answer to this question can be very short. You will give a more detailed answer in the final lab report.) Before writing your design document, read through the starter code. The comments at the top of the file explain what methods you need to change. Be sure you look at the code for those methods so you can see what is already provided and what code you will need to write. This is a challenging problem! Please don't be discouraged if you don't "get it" right away. Please do ask questions. I'm here to help. I expect most students, if not all, will need some more explanation. Partial credit will be given for partial solutions. Focus on doing your best. Do not change the types of any of the methods (return types or argument types). You will not receive credit. Starter code: In Eclipse: Right-click on the "Lab3" icon in the left sidebar. If using eclipse with git, you may need to first right-click on the "cis27" folder and then select Team, then Pull, before you can see the "Lab3" icon. Select "Build Path" from the pop-up menu, then select "Add Libraries..." from the second menu that pops up. Make sure "JRE System Library" is selected (highlighted). Click Next. Click Finish. Right-click on the "Part1" folder underneath the "Lab3" icon. In the menu that pops up, select "Build Path", then select "Use as source folder" from the second menu that pops up. To run the code, right-click on the "RedBlackBST.java" icon in the sidebar and select "Run As", then "Java application" from the second menu that pops up. You can also go to the Run menu > "Run As" > "Java application". You will see an assertion failure, which is expected; start editing the code so that the tests will pass! Without Eclipse: See https://github.com/catamorphism/cis27/blob/master/Lab3/Part1/RedBlackBST.java (Links to an external site.)