Data Structures Homework 8, Fall 1999

Due: Dec 8, 1999, 12 PM using turnin

Absolutely no late submissions accepted since solutions will be posted soon after the deadline.

In this project, you will implement a Red-Black Tree interface and use it for your checked list (instead of the Hash Table used in HW6). Construct a concrete class, RedBlackTree, which implements the following interface:

public interface RedBlackLocator {
 public int size();
 public boolean isEmpty();
 public Position find(Object k); // Return position for item (k',e) w/ k=k'
 public Position insert(Object k, Object o); // Insert (k,o), get back Position
 public Object remove(Position l); // Remove item at locator l
}

Your class should have a constructor that accepts a Comparator object and builds an initially-empty red-black tree. Use the comparator object from last programming assignment.

Use the rest of the classes from the solution to the previous homework for implementing and testing solution to this homework.