RedBlackTree Specifications
Start by making a copy of your RedBlackTree class from last week’s Rotation Activity. You can also remove the three JUnit Test methods from this copy, since they may break while changing the mechanics of this new class’s insert operation. If there are any unresolved bugs in your code from last week’s activity, please work through fixing those first. If additional assistance from the course staff would be helpful for this, please contact us for that help.
Add a public boolean isBlack field to the Node
At the end of the insert method, add a statement to always set the root node of your red black tree to be black. No further changes to this method should be made.
Add a new private method to your RedBlackTree class called enforceRBTreePropertiesAfterInsert which takes a reference to a newly added red node as its only parameter. Note that this method may also be called recursively, in which case the input parameter may reference a different red node in the tree that potentially has a red parent node. The job of this enforceRBTreePropertiesAfterInsert method is to resolve any red property violations that are introduced by inserting new nodes into a red-black tree. While doing so, all other red-black tree properties must also be preserved.
The enforceRBTreePropertiesAfterInsert method should be called from insertHelper after adding a new red node to the tree (in both the cases of adding this new node as a left child and as a right child). No further changes to the insertHelper method should be made.
Implement the enforceRBTreePropertiesAfterInsert method to recognize and handle each of the possible cases described in your lecture videos and readings. You should make use of the rotate method that you implemented last week, by calling it from your definition of enforceRBTreePropertiesAfterInsert. Implementing this method correctly should ensure that the worst-case height of your tree remains O(log n), where n = the size or number of elements stored in your red black tree.
To help keep your RedBlackTree implementation compatible with your team’s Project Two Application, avoid adding any extra fields or methods to these classes, other than those explicitly described above. Also notice that you are not being asked to implement the remove operation for this red black tree implementation.
TestRedBlackTree Requirements
In addition to your RedBlackTree.java implementation, you must develop and submit a JUnit test class within a separate source file named TestRedBlackTree.java. This test class must include at least four distinct and descriptively named test methods. Each test should be designed to test a different case for inserting into a red black tree, and ensuring that your enforceRBTreePropertiesAfterInsert method functions is being used correctly. Be sure to include JavaDoc style method header comments for each of these test methods that clearly describe what high-level “case” they are testing.
Last Completed Projects
| topic title | academic level | Writer | delivered |
|---|