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.
- This is an individual exercise.
- Continue working on your RedBlackTree project.
- 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.
- 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.
- Again, you are not permitted to use a parent pointer as a field in
the BinaryNode class.
- 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.
- 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.
- Use this test-suite as well as test
cases of your own design to debug your software.
- Here is the Tree visualizer,
modified to contain a remove button.
- Submit your RedBlackTree.java file to the appropriate drop-box on Moodle.