Assignment #9 - Trees, Logs, and Dictionaries

Objectives:

The main objectives of this assignment are:
• Build a tree-based dictionary that offers consistent O(lg n) time.
• Practice incorporating advanced Data Structures to replace simple ones.
• Earn extra credit for going above and beyond.
  

The Assignment:

The Concept:

B&C Corporation has noticed some severe problems with their bcPhone recently, and realized that their Beige & Chartruese Library is taking up a lot of extra memory.   So, to compensate, they've decided to change their Library to include a better sized dictionary.

They recognize that unlike the Lookup Table and Hash Table, there are a number of fast maps which have very little wasted space, and would like you to build, then incorporate, one of those dictionaries into your Beige & Chartruese Library program.

Your Job:

You have two tasks:
1. Build an AVL Tree (and possibly a Red-Black tree) to implement a dictionary.
2. Use your tree-based dictionary to replace the one used in the Beige-Chartruese Library, then, add removal capabilities to the Library.

Getting Started:

1. Download and import the following zip file: Assignment9.zip. For Eclipse:
   1. Open Eclipse
   2. Choose "File → Import".
   3. Select the "General" category.
   4. Pick "Existing Projects into Workspace"
   5. Click on "Next"
   6. Select the button for "Select Archive File" and browse to/select the zip file.
   7. Click on "Finish"
2. Move your completed BeigeChartrueseLibrary.java file, and any other necessary files into the cs2321 directory of the TreeBasedDictionary project.

Requirements:

You are to implement a Binary Tree based Dictionary which uses the AVL technique to balance. For bonus points, you may complete a functional Red-Black tree (balancing appropriately). As in other recent assignments, you are responsible for creating and running the tests necessary to ensure the Dictionary is functional.

Instead of trying to create the entire tree in one file, you should implement a generic LinkedBinaryTree using the LinkTree interface, then use an instance of that to develop the AVL Tree (and Red-Black Tree).Skeleton code has been provided for both types of Dictionaries, and a LinkedBinaryTree.

In the Beige-Chartruese Library, you should add, and implement the following method:


/**
* Remove the given record from the Library
*/
public void deleteRecord(Record r){
return null;
}


Adjust the main method so that the following input will be accepted appropriately.


REMOVE,X


Where X is the "number" of the record in the last list of records returned. For instance, if a list of 5 records was returned by a search (Adams, Brown, Carter, Davis, and Einstein), then the user calls:


REMOVE,3
REMOVE,5


The calls will remove Carter and Einstein from the Beige Chartruese Library, respectively. Nothing should be displayed. An invalid number, or a number which has already been deleted should have no effect (and no error should be thrown).
HINT: Once you complete your AVL Tree, it can be turned into a Red-Black Tree without a complete overhaul.

Submission:

First, look at the following checklist:
1. Does the program compile on CS machines? (Programs that don't compile for us will not be graded)
2. Do you ever import from java.util. If so, be sure you only import allowed components (like Iterator, Exceptions, etc.). Unless the assignment specifically mentions it is permissible, you should never include any of Java's native data structures.
3. Does the program meet all required interfaces?
4. Have you tested every method in some way?
5. Do all your methods have a @TimeComplexity indicator?
6. If any methods have a good amortized or expected cost, do they have both the @TimeComplexity and either @TimeComplexityAmortized or @TimeComplexityExpected
7. Do all your data structures (and other classes like iterators) have a @SpaceComplexity indicator?
8. Do you provide adequate TCJ and SCJ comments to prove your time and space complexity?
9. Is the indentation easily readable? You can have Eclipse correct indentation by highlighting all code and select "Source → Correct Indentation".
10. Have you removed any of the "cs2321" comments (/*#)?
11. Are comments well organized and concise?
If you have reviewed your code and all the criteria on the checklist are acceptable, follow the submission procedure.

Grading Criteria:

• Implementing an AVL tree based Dictionary which correctly implement all methods: 60
• Correctly balancing the tree so that the major methods run in O(lg n) time: 20
• Correct documentation of time and space complexity: 10
• Clear concise code with good commenting: 10
• *BONUS* implementing a dictionary with a Red-Black tree: +25