The purpose of this exercise is to learn about top-down red black
trees. In this exercise, we focus exclusively on insertion. There will
be a separate exercise on removal.
Work on this assignment by yourself.
Design and develop a RedBlackTree class.
Add the following enumeration to your RedBlackTree class:
public enum Color {RED, BLACK}
Design and develop a BinaryNode class which is an inner
class to the RedBlackTree class. It holds elements of parameterized
generic comparable types. For testing purposes make this class
public. Each node should have a color associated with it.
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 points. In particular,
code that is not in O/O style will receive zero 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.
Ensure that you implement top-down insertion. If you use a loop or
if most of the insert 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.
It is crucially important that you install the TreeVisualizer adapted to RedBlack
trees as it makes testing much easier.
In the RedBlackTree class:
An insert method with the following signature: public boolean
insert(T element) It and its companion in the BinaryNode class
must implement top/down insertion. The method throws an
IllegalArgumentException if null is passed to it. This
method returns true if the element was successfully added and false
otherwise.
public int height(), which returns the height of the
root. This method traverses the tree as you are not maintaining
height information with each node.
public Iterator<RedBlackTree.BinaryNode> iterator(),
which returns a pre-order iterator. Notice that for testing purposes,
this iterator returns BinaryNode elements rather than the data elements
stored in the tree.
public int getRotationCount(), which returns the number of
rotations. A single rotation counts as 1 rotation and a double
rotation counts as 2 rotations.
In the BinaryNode class:
public T getElement(), which returns the element stored
at the node.
public Color getColor(), which return the color of this
node.
Use this test-suite as well as test
cases of your
own design to debug your software.
Ensure that your code is efficient and well-written.
You may implement the tree traversal using recursion or
iteration. However, in your BinaryNode class, you may NOT have a field
that maintains a pointer to the parent node.
Submit your project to the appropriate dropbox on Moodle.