Homework - Red Black Trees

Conditions

This work is due before Monday June 12 2006 at 18:00 in my mail box. (In the lobby of the Rolex building). This work has to be delivered on paper (no e-mail).

This homework will be done by groups of two. If a class contains an odd number of students, one person will work alone.
You will have to implement the following program in Java.

Presentation

We want to produce a Java "Red Black Tree Dictionary". This data-structure is explained in the slides that you received in course. You can also download it from here.
Red-Black Trees
Handshout (4 pages on 1 page)
Slides
This data structure is a binary search tree with a heigh bounded by 2.log(n-1). You can experience more about the Red-Black Trees in the pages 170 to 184 of the book Algorithm Design of Goodrich and Tamassia (also known as the book).

Subject

You have to implement a red-black tree dictionary using the following classes and interfaces.

Dictionary.java: A dictionary interface (do not forget to add a comparator in the constructor of your red-black dictionary).
Entry.java The interface being returned by the dictionary
RedBlackNode.java The nodes used to build a tree.
Comparator.java The interface to be implemented by classes used to compare elements.

To do

You have to write a class that implements the Dictionary using the RedBlackNodes. Do not forget to also use a Comparator
You have to use an instance of the class RedBlackNode as instance variable of your Dictionary. (this means that you will not have to implement a tree or a binary tree, just use directly the nodes).
You can write all of this with generics classes or without. You are free. If you want to work with generics, just change my classes and interfaces.

Report

You have to give me a Listing of the program you have written.
This listing will contain:

The program
Test programs
Execution Trace (output of your program);
Comments; (This is very important, can be JavaDoc)
useful names (no names like "l", "t1"...);
Some Error Handling with usefull Exceptions