CS 223 Out-lab 4
Week of 2/13

Due: to TA by 3/7 (extension granted)

Red-Black Trees

For this out-lab assignment, you are to implement a red-black tree.  Rather than start from scratch, you should start with the BinarySearchTree  and SearchNode classes that we developed in class and modify their attributes and methods to implement the red-black balancing that occurs when inserting or deleting a node.  Your BinarySearchTree class should have the following methods:

• insert - inserts a new SearchNode into the tree
• delete - deletes the given SearchNode from the tree
• search - given a key value, returns a SearchNode in the tree with the same key, or null if none exists
• printTree - you can use the existing method.  Extra credit: modify so that red nodes are printed in red and black nodes black (you will need to create a JTextPanel to display colored text.  Here is a simple program that does this to borrow from: ColorPane.java)
• treeHeight - this should return the height of the tree (you don't need to be too concerned with the efficiency of this method)
• treeMaximum - returns the largest value in the tree
• treeMinimum - returns the smallest value in the tree

What to Turn In

• a printed copy of all source code.  Ensure the source code is documented.
• a printout of several test runs including the following:

Test One

Insert the following numbers into a new search tree:

1, 5, 10, 9, 4, 6, 8, 12, 20, 25, 30, 35, 11

Print out the tree

Delete 25 and then 20.

Print out the resulting tree

Test Two

Insert the numbers 1 to 25 in order into a new search tree.

Call delete(search(10)), ..., delete(search(20)) on the search tree

Print out the resulting tree

Another extra credit possibility: add a simple GUI to the application with a simple dialog to add and delete values in the tree.  Display the tree in a separate pane and redraw each time there is a change.