Assignment #6 - AVL Tree
Objectives:
The main objectives of this assignment are:
- Build a tree-based map that offers consistent O(lg n) time.
- Practice incorporating advanced Data Structures to replace simple ones.
- TEACH YOU TO START ASSIGNMENTS EARLY! (This one will take a while)
The Assignment:
The Concept:
The LookupTable from the previous assignment has a great advantage over the
HashMap: it can search for a range of values. Unfortunately, there is no
easy way of doing this in the current implementation of the HashMap.
But, the LookupTable does suffer a disadvantage: adding a single
element may cause many elements to have to shift in order to make room, which
can be a huge cost if many elements exist in the LookupTable.
There are a number of fast maps that do both - range
search and insert/remove update - efficiently
without performance degradation after many inserts and removes. Your job is
to build one of these, specifically, an AVL Tree.
Your Job:
You have three tasks:
- Complete the LinkedBinaryTree class. (Remember to make the constructor PUBLIC)
- Complete the BinarySearchTree class, which extends
LinkedBinaryTree and implements
SortedMap, like LookupTable.class in the last assignment.
- Build an AVL Tree which extends BinarySearchTree to maintain a
balanced binary search tree.
Getting Started:
- Download and import the following zip file: Assignment6.zip. For
Eclipse:
- Open Eclipse
- Choose "File → Import".
- Select the "General" category.
- Pick "Existing Projects into Workspace"
- Click on "Next"
- Select the button for "Select Archive File" and browse to/select the zip file.
- Click on "Finish"
Requirements:
You are to implement a Binary Tree based Map which uses the AVL technique to balance.
As in other recent assignments, you are responsible for creating and running the tests necessary to
ensure the map is functional.
You may create other methods and classes. You may create your own main functions for each class and leave them there with your code when
you submit. You do need to remove all the debugging system.out.print before
submission.
Submission:
First, look at the following checklist:
- Does the program compile on CS machines?
(Programs that don't compile for us will not be graded)
- 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.
- Does the program meet all required interfaces?
- Have you tested every method in some way?
- Do all your methods have a @TimeComplexity
indicator?
- If any methods have a good amortized or expected cost, do
they have both the @TimeComplexity and either @TimeComplexityAmortized
or @TimeComplexityExpected
- Do you provide adequate TCJ comments to prove your time complexity?
- Is the indentation easily readable? You can have Eclipse
correct indentation by highlighting all code and select "Source
→ Correct Indentation".
- 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 Linked Binary Tree correctly : 20
- Implementing Binary Seach Tree correctly : 30
- Implementing AVL correctly : 20
- Correctly balancing the tree so that the major methods run in O(lg n) time: 10
- Correct documentation of time complexity: 10
- Clear concise code with good commenting: 10
- Starting the project VERY EARLY: 0 points, but you stand a chance at finishing it by the due date