Lab 4 Solution

This lab involves implementing a Red-Black Tree




Overview




You will Construct a Red-Black Tree of numbers. You will extend your code in programming as-signment 2 to now include a balancing operations. If you prefer, we have posted a working BST and Node class for you to build o of. Note: BST.java is there as a reference. No need to turn it in along with your code.




A BST is a Red-Black tree if it satis es the following Red-Black Properties:







Every node is either red or black



Every leaf node counts as black



If a node is red, then both its children are black



Every simple path from a node to a descendant leaf contains the same number of black nodes



The root node is always black






Fill out all of the methods in the provided skeleton code.




You may add additional methods, but should NOT add public elds. You also should not change the name of any of the classes or les.




The program should continually accept instructions until exit is entered.




In particular, you will implement the following functionality for your Red-Black Tree:




insert




Preform BST insert




Check to see if the tree breaks any of the Red-Black Properties




If so, preform the appropriate rotations and or re-colorings




delete




Preform BST delete




Check to see if the tree breaks any of the Red-Black Properties If so, preform the appropriate rotations and or re-colorings Note: You will not be asked to remove the most di cult nodes (ie) you won’t need to recursively rebalance See Extra Credit













1



search




Return the node corresponding to the given number




Print "Found" if the corresponding key is in the tree.




Otherwise, print "Not Found"




leftRotate




If x is the root of the tree to rotate with left child subtree T1 and right child y, where T2 and T3 are the left and right children of y:







x becomes left child of y and T3 as its right child of y




T1 becomes left child of x and T2 becomes right child of x







rightRotate




If y is the root of the tree to rotate with right child subtree T3 and left child x, where T1 and T2 are the left and right children of x:







y becomes right child of x and T1 as its left child of x




T2 becomes left child of y and T3 becomes right child of y







Additionally, implement the following instructions in the main() function in lab4.java




traverse




Preform the preorder traversal of the Red-Black Tree




exit




Exit the program




Print "Successful Exit"










Input Description







The input will be a text le, for example inSample.txt below will be provided. Each of the lines (unknown how many) will contain a di erent set of words specifying a task along with a number (if applicable). You should create an empty Red-Black Tree (with root null), and then perform a sequence of actions on that tree.




Note: You should implement your Red-Black tree with generics, but create a Red-Black tree that takes in integers.






















2



insert 10




insert 5




insert 20




insert 3




traverse




insert 2




traverse




search 17




insert 1




delete 20




traverse




exit










Output Description







Using the sample input above, your program should output:







10
5
3
20




10
3
2
5
20
Not Found




3 2


1 10
5


Successful
Exit









Testing Protocol







We will test your program in the same fashion as previous labs. We strongly suggest you test your program in the following ways:







While creating it With inSample.txt




With the provided test.sh le found in /home/users/smergend/public/cs313/lab4 on ix-dev.








































3
Grading







This assignment will be graded as follows:




Correctness 40%




Your program compiles without errors (including the submitted les NOT containing package names at the top. Delete the package name from the top of the les before you submit them): 10% Your program runs without errors: 10%




Your program produces the correct output: 20%




Implementation 40%




Insert, delete, search, traverse, and exit all preform in the correct time complexity for the RBT:




10%




leftRotate, and rightRotate are also preform in the correct time complexity: 30%




Documentation 20%




To earn points for implementation, your code must be clear enough for us to understand










Extra Credit 20%







Each part of the extra credit will be worth 10%




We will test the extra credit similarly to how we test the rest of the assignment.




Add an additional public function isRBT() to your RBT.java that checks if the current tree matches RBT rules. Add an extra command in lab4.java that is called "test"







Instantiate a new object from the given class WrongTree.java at the beginning of lab4.java



Instantiate a new RBT from your RBT.java at the beginning of lab4.java



Set root on your RBT to the root returned in WrongTree.getRoot()



Determine if your current RBT is in fact a RBT



Don’t change WrongTree.java, write code in RBT.java




Print the private time eld in WrongTree.java using the getTime() method



Print true or false depending on if you think the tree is a RBT






For the other half, we will simply run a more in depth test input le.

























4