In this programming assignment you will implement a dynamic dictionary ADT using a red-black tree.

You will have to hand in a physical printout of each of your programs. We will also electronically check your programs.

As usual, please remember to submit your work before the deadline. If you have any questions about this assignment, please send emails to shenyh@ust.hk.

DUE DATE

The deadline of the assignment is 12:00 noon, Wed 20 Nov 2002. Late assignments will not be accepted, since ACS will not collect them.

GRADING

Each function written should be adequately documented so that a reader will be able to understand what is being done. Your programs will be run on a standard test data set.

This assignment will account for 80 points in your final score. The general grading criteria for a program is as follows:

• 80% - Correctness
• 10% - Programming style
• 10% - Documentation

When your program does not run correctly on the test data, then your program will be graded by visual examination and the maximum score you can then get for Correctness is 30%.

ACS SUBMISSION

• You must use your Computer Science department UNIX account to submit your homework (do not use other campus account from ITSC or other departments). If for some reason this is not possible please come see one of the instructors.
• You should have already activated this account for Assignment 0. If you have not, you can do it in the CSSystem home page (https://cssu3.cs.ust.hk:8443/pass.html).
• Your program must compile properly on your CS department account, using the g++ compiler. Other C++ compilers or computers cannot be used for your final submission.
• Create your homework directory "~/comp171/a2/" under your CS department UNIX account.
• Put the source code for your functions in a single file "dictionary.hpp" (not "dictionary.cpp" since templates must go in the .hpp file) under your homework directory before the deadline. Make sure you name your file exactly as specified.
• Make sure that there is no main() function in your dictionary.hpp. Header files cannot contain a main() function, and are intended to be used as a library of functions that some other main program can call.
• You may also have one other file "dictionary.cpp" in this directory, if your implementation requires it (note that it is possible to do the assignment without this, but you may prefer to have some non-template functions that go in "dictionary.cpp"). If you do this, make sure this file does not contain any main() function.
• Make sure there are no other files in this directory. You are encouraged to compile and run your program to check if it gives the right result, but use another directory for your implementation and testing.
• Your file must compile correctly and work, using the testing {\tt main} program that will be posted.

IMPLEMENTATION

Use the following type declarations for the tree node. You are allowed to add any other public or protected member variables and functions as you wish to this class, so long as you implement at least these members correctly.

enum RBColor { RED, BLACK };

template <class T>
class RBTreeNode {
public:
  T key;
  RBTreeNode* leftchild;
  RBTreeNode* rightchild;
  RBTreeNode* parent;
  RBColor color;
};

You are required to program a red-black tree container class that supports three member functions. This class provides a Dictionary API. As such, you may not add any other public member variables or functions to this class (except, of course, constructors or destructors).

template <class T>
class RedBlackTree {
public:
  T* find(const T& x) const;
    // Search the tree to find x.  Return a pointer to the matching key,
    // or NULL if x is not found.
  bool insert(const T& x);
    // Insert x into the tree.  If x has been inserted before, then it
    // is NOT inserted again.  Return true iff this is the first time
    // that x is inserted.
  int erase(const T& x);
    // Delete x from the tree.  Return 1 if x was found and deleted,
    // or 0 if x was not found.
protected:
  RBTreeNode<T>* getRoot();
    // Return a pointer to the root of the red-black tree.
  RBTreeNode<T>* getSentinel();
    // Return a pointer to the node being used as a sentinel.
};

Rules to be observed:

1. All insertion and deletion should be performed in the fashion as described in the textbook (and in lecture). Do not program according to any other textbook.
2. During deletion, when you try to perform a rotation, you should check with the left sibling of a node to see whether rotation can be done. If the left sibling does not exist or rotation cannot be done, then check with the right sibling to see whether a rotation can be done.

A TEST DRIVER

You may find the following files helpful for your implementation and testing:

• The files containing the test arrays: array8.txt, array16.txt, array32.txt, array64.txt, array1024.txt
• The files testdriver.cpp

The files containing the test arrays:

These files containing arrays of different length to do your testing. The length of an array is always an exponent of 2. The files have the filename with the style "array*.txt" in which "*" represents the length of the array, i.e. the file "array32.txt" contains an array with the length of 32 and the file "array1024.txt" contains an array with the length of 1024.

The test driver:

The test driver uses one argument which is the length of the array you want to test your algorithm with.

The test driver is composed of four parts:

1. Read an array of the length defined in the argument from the corresponding file.
2. The sample code that inserts the keys of the array into an empty red black tree one by one and examines the red black property after each insertion.
3. The sample code that tries to find a key in the red black tree.
4. The sample code that erases the keys of the array from a red black tree one by one and examines the red black property after each erasion.

Testing your algorithm with the test driver:

Please follow the following steps to go on with the test:

• Put the files "testdriver.cpp", "dictionary.hpp" and the files containing the arrays under the same directory.
• If you do all your implementation in "dictionary.hpp", use the command "g++ testdriver.cpp -o filename" to create the executable output file with the filename designated by you, i. e. for "g++ testdriver.cpp -o TestRedBlack" you will get the executable file "TestRedBlack". If you have an extra "dictionary.cpp" file, use the command "g++ testdriver.cpp dictionary.cpp -o filename" to create the executable file.
• Use the command "filename arg1" to test your algorithm, i. e. if you have the executable file "TestRedBlack" and you want to use an array with the length 32 to test your algorithm, use the command "TestRedBlack 32".

We strongly suggest you begin your test with arrays of small size to find the problems with your algorithm.