CS 3500 Assignment #6: Red-Black Tree Implementation
Due: Friday, November 1, 2013

The purposes of this assignment are:
* To implement the BTree ADT with good worst-case efficiency
* To give you an opportunity to implement red-black trees
* To give you more design responsibility

You will modify your implementation of the BTree that was specified in 
Assignments 4 and 5 to make it efficient even in the worst case. You will 
make BTree efficient for worst case by implementing it as a red-black 
tree.

Collaboration between students is forbidden on this assignment. You are 
responsible for keeping your code hidden from all other students. You 
will submit this assignment within Web-CAT.

Your file of Java code should begin with a block comment that lists:
    1.  Your name, as you want the instructor to write it.
    2.  Your email address.
    3.  Any remarks that you wish to make to the instructor.

Part of your grade will depend on the quality and correctness of your 
code, part will assess the tests you design - especially the test 
coverage, part will depend on the readability of your code (comments and 
indentation), and part will depend on how well you follow the procedure 
above for submitting your work.  Assignments submitted between 12:00 am 
and 11:59 pm the day after the due date will receive a 20 percentage 
point penalty on the assignment. 

---------------------------------------------------------------------------

Your assignment is to write the code for a file, BTree.java, that 
implements the class BTree as given for Assignments 4 and 5 and two 
classes StringByLength and StringByLex each of which implements the 
Comparator<String> interface - the first one ordering the String-s by 
their length, the second by their lexicographical ordering. BTree is 
still a mutable data type whose values represent String data items, but 
now it will be organized as red-black tree (rather than just a binary 
search tree), with the ordering specified by the provided 
Comparator<String>.

---------------------------------------------------------------------------

You will need to make sure that you have tested BTree completely. You 
will submit your test program which will be graded for test coverage. 
Your test program should be written using JUnit testing or the Tester 
library. Web-CAT will check that you have tested each method and 
decision within your implementation.

---------------------------------------------------------------------------

For this assignment, you will submit BTree.java along with your test 
program (BTreeTest.java or ExamplesBTree.java).

---------------------------------------------------------------------------

This assignment will be out of 100 points:
 * 50: Correctness/Testing - Testing against our tests along with test 
       coverage of your test program.
 * 20: Style
 * 30: Design/Readability (Graded by tutors) which will include
       timing/efficiency