CSSE 230: Red Black Trees - Removal of Elements

The purpose of this exercise is to understand in detail the mechanics of top-down deletion in red-black trees.
  1. This is an individual exercise.
  2. Continue working on your RedBlackTree project.
  3. Add a remove method with the following signature: public boolean remove(T element) It and its companion in the BinaryNode class must implement top/down removal. The method throws an IllegalArgumentException if null is passed to it. The only parameter is the element to be removed from the tree. It has to be of the parameterized type Comparable that was used to create the tree. This method returns true if the element was successfully removed and false otherwise.
  4. Ensure that you implement top-down removal. If you use a loop or if most of the remove related methods in your BinaryNode class return void, that is a good indicator that you are using top-down removal. When in doubt, ask us.
  5. Again, you are not permitted to use a parent pointer as a field in the BinaryNode class.
  6. Design and develop your code using good style and implementing it in an efficient manner. Review your code and ensure that it is well written. Look for places where you can simplify through code reuse and other methods. Among others, none of the methods in the RedBlackTree class proper should be recursive. Recursion should only take place in the BinaryNode class. Ensure that your code follows true OO-style, i.e. do not pass in the object to which you apply a method. Use good function decomposition, i.e. avoid spagetti code. Violating these principles of good code design will cause you to loose many points, i.e. 70 points.
  7. Please implement the four rotations as specified for TDRB trees. Please ensure that you actually rotate the nodes. Do not create new nodes! Additionally, do not call a method, in either insert or remove, that first checks whether the element is in the tree.
  8. Use this test-suite as well as test cases of your own design to debug your software.
  9. Here is the Tree visualizer, modified to contain a remove button.
  10. Submit your RedBlackTree.java file to the appropriate drop-box on Moodle.