Project Description

Red-Black Tree Implementation [65pts]

• insert -- adds the given element to the tree
  
• remove -- removes the given element from the tree
  
• find -- returns the matching element in the tree, or a nullptr
  
• contains -- returns a boolean whether the tree contains the given element
  
• getHeight -- returns the height of the tree
  
• findMin -- returns the min element of the tree
  
• findMax -- returns the max element of the tree
  
• isEmpty -- returns a boolean whether the tree is empty
  
• makeEmpty -- removes all elements from the tree
  
• inOrderIterator -- returns an interator that performs an in-order traversal of the tree
  
• preOrderIterator -- returns an iterator that performs a pre-order traversal of the tree
  
• postOrderIterator -- returns an iterator that performs a post-order traversal of the tree
  

Testing [35pts]

Write two programs to test your red-black tree:

1.  The first program, called unit_test_rbtree, should run a series of automated tests of the red-black tree, outputting whether or not the red-black tree passed or failed the tests based on the expected result.  It should run multiple tests of all operations of the red black tree, and test the red-black tree as a container for at least two data types.

2. The second program, called manual_test_rbtree, should be interactive and support the following commands (one per line):

• "i <number>"  -- inserts the given number into the red-black tree
• "r <number>"  -- removes the given number from the red-black tree
• "c <number>"  -- returns whether or not the red-black tree contained the given number
• "e" -- makes the red-black tree empty
  
• "h" -- prints the height of the red-black tree
• "p" -- prints two traversals of the red-black tree on two separate lines, first a pre-order traversal and then an in-order traversal
  

Neither of these test programs should take in any command line arguments.

Write Up

In a separate brief write-up, discuss the following:

• Provide a high-level overview of how you implemented the red-black tree
• Explain any design choices you made
  
• What, if any, problems you encountered during your implementation
• What unit-tests you chose and why you chose them
  

Final Program

Submit one assignment for all partners, following the assignment guidelines and submission instructions. 

Be sure to list all partners' names in your README file. 

Provide a working Makefile for your assignment.  The Makefile should support four commands:  make, make unit_test, make manual_test, and make clean.  I must be able to:

1. Uncompress your submission
2. "cd" into the directory
3. Type "make" and have your program compile itself.
4. Type "make unit_test" and have it output the results of the unit test.
5. Type "make manual_test" and have it run the manual test program.

Put all source code, the data files, the README, your writeup, and Makefile into a single .tar.gz file.

Additionally, each partner should also submit an independent and private brief statement via e-mail to Eric that describes each partner's contribution to the project.  Use the subject "CS246 HW5 Partner Work Distribution".