CSC311: Data Structures
Fall 2007
Programming
Project 3
Due December 13, Thursday, 2007
Dictionary and AVL Trees
Description:
Chapter 10 discusses the
definition and properties of binary search trees, and claims that performance
of operations including search, insertion and deletion of a binary search tree depends
on the height of the tree. Especially, the worst performance is O(n), where n is the number of nodes in the binary tree, and
the best performance is O(logn). To achieve the best
performance, we would like to main the height of binary search tree as
balanced. This is the task of AVL tree.
AVL trees guarantee that
the height is O(logn), with
n being the number of entries stored in the tree. To implement an AVL tree, two
operations, single rotation and double rotation, are needed to update the tree
structure if the AVL height-balance property is violated due to insertion of
new entries or deletion of existing entries. Section 10.2.2 lists the Java
implementation of AVL trees.
In Section 9.3, the unordered
dictionary ADT is defined to support 7 operations (p. 389). In Section 9.5.2,
the ordered dictionary ADT is defined as an unordered dictionary plus 4
operations to support the orders (p.408). Carefully read Sections 9.3, 9.5.2,
and 10.2, and complete the following task.
Task:
Write a Java class to
implement the unordered dictionary ADT. You can make a copy of the AVL
implementation in Section 10.2.2 (or you can find other implementations
online). Use the implemented AVL to develop a class to implement the 7 operations
for unordered dictionary defined in Section 9.3.
Write a Java class to
test your unordered dictionary class by inserting the following sequence
of keys: 5, 16, 22, 45, 2, 10, 18, 30, 50, 12, and 1 to your dictionary and
delete the following sequence of keys: 16, 30, 10, 12, and 22 from your dictionary.
Extra credit (15%): Write
a Java class (as a subclass) to extend above unordered dictionary (as a superclass) by implementing 4 more methods required by
ordered dictionary ADT and defined in Section 9.5.2.
Submission:
· The project will due on
· Only
electronic submission will be accepted.
· Your
submission should include
o Java source code,
o A class diagram describing
the relationships of the interface and classes, if necessary,
o Necessary documentation for the implemented
operations.