red black tree

The assigment is overdue now. I will up the price I am willing to pay to have it done. It must be completed by the latest on the 8th. However I would greatly preffer for it to be finished on the 7th. I will add $20 to the price if you can complete it by then.

 

I need the files to run in Eclipse. Please upload them as such. See my file as an example. 

They must be coded in java. 

This is for a 200 level data structures class so please match that level accordingly. 

I need java Test cases and comments please.  (see my example file)

 

I have included part of the previous assigment so you can see what mine looks like and it also may have things you may need like map etc. Though I cannot guarantee all of it is working properly. (named example)

 

—–

 

 

Implementing a red-black tree

The main goal of this assignment is for you to implement a red-black tree. As we did with the previous binary search tree, we are going to implement this as a Map, so it should have exactly the same interface as the last time. In keeping with the naming convention established last time, you should name your new class RBMap. To help you test your code, add three extra public methods:

public boolean redViolationExists()

This method will traverse the tree and return true if any red node has a red child.

public int blackHeight()

This method will return the black height of the tree. If the black height of the two children of the tree do not agree, it will return -1, indicating a black height violation

public String toString()

This overrides the default 
toString method to print out a traversal of the tree. This should be in the form of a preorder traversal of the tree in which each node is printed out in the form of the key, followed by a colon and then a B or an R, all in square brackets. So a tree with root 5 and children 3 and 9 would look like [5:B][3:R][9:R].

We would not, of course, include these in any production code (just like the Node class, the use of red and black are meaningless to actual uses of your class). These will a) assure me that you know what those are, and b) be useful in testing your code (provided you write them correctly…). Note that while these are useful for testing, they are not replacements for testing the functionality of the tree (they only tell us that there are no red or black violations), and they cannot themselves be tested in the usual way (there shouldn’t be a way to create a tree with violations). Also, DO NOT USE THESE ANYWHERE IN YOUR CODE — THEY ARE FOR TESTING ONLY!

As I said in class, the actual mechanics of most of the functionality of the BSTMap class will remain the same. The biggest difference is that you need to rebalance the tree after insertions and deletions. To help you out, I have created some starter code for you. This is basically an implementation of the BSTMap class that you had to build for the last homework, with some features to help with the red-black tree added in. You are not required to use this code, but I encourage you to read through it.

This is an assignment about details. There are a lot of different cases that you need to worry about, and you need to be careful how you handle them. As I said in class, I didn’t show you a number of cases because they were the mirror of the cases we did discuss. You, of course, need to cover them. Think about ways to write your code so that you can cover these right and left differences at the same time (the less code you write, the easier it will be to debug).

Testing

I would like you to be particularly careful in writing your tests. It is not enough to just reuse your tests from the last map and dump some values in and read them back out. You can keep them around to make sure that the Map still behaves properly as a map, but we also want to make sure that all of your correction code is functioning correctly. This time, I want to see tests that exercise each of the conditions that we discussed in class (you can have tests that hit more than one condition; for example, you can test case 2 and case 3 insertion at the same time). In your comments, be explicit about which case you are testing and how your test makes sure that it worked.

 

 

 

please note I need a javaTests for all of the methods. 

 

The example of the methods used in the previous binary tree are attatched as well as the sample code