|
|
|
|
|
CSE373 Data Structures Au07, Homework 3 - Part 2
Due Date Extended - Due online Sunday,
Nov 4, 2007, at 11 pm.
Please turn in your code
here. Please bring code printouts (stapled) to the class on Nov 5, 2007.
One of the applications of BSTs is to implement ordered sets. A set is a container
that stores a collection of items with no duplicates; attempting to add a
duplicate item to a set has no effect. An ordered set is a set with the additional
property that when we iterate through it, we retrieve the elements in order
as defined by the comparison function
for those elements.
For this assignment, create Java interfaces for ordered sets and their iterators
and implement those interfaces using an AVL tree as the
underlying data structure. Specifically, define and implement the following
two interfaces:
- Interface
BasicSet. This is the interface describing the set
operations. Include the following:
add(item) Add the specified item to the set if it is not already present.
Return true if the item was added; false if not.contains(item) Return true if the item is an element of the
set, false if not.size() Return the number of elements in the set.remove(item) Remove item from the set if present. Return true if the item
was removed; false if not.iterator() Return an iterator for this set.
- Interface
BasicSetIterator. This interface specifies iterator
operations for a BasicSet.
hasNext() Return true if there is another available element in the iteration;
false if not.next() Return the next item in the iteration. Throw a
NoSuchElementException if there is no next item.
Successive calls to next() should return the items in the
set in order.
Because this is a sorted set, the items in the set must have type Comparable,
meaning that whatever kind of objects they are, they implement the Comparable interface,
which includes the compareTo() method. The ordering specified
by compareTo() is the one that determines the order in which the
items are returned from the set by successive calls to the iterator's next() method.
After defining the interfaces, create an implementation of BasicSet in
a class named BasicOrderedAVLTreeSet. That class should contain
a nested class BasicOrderedTreeSetIterator that implements the BasicSetIterator interface.
Constraints
- Your implementation of
BasicOrderedAVLTreeSet must use an
AVL tree to store the set items. The tree should be rebalanced as necessary
when
items are added to it.
- Tree nodes should be defined as a private class inside
BasicOrderedAVLTreeSet.
A tree node should only contain a reference to the item stored at
that node and single links to the node's left and right children, plus whatever
balance information is needed to maintain the tree's AVL property, and, if
you use lazy deletion as suggested, a bit to indicate deleted nodes.
- Use a single instance variable in
BasicOrderedAVLTreeSet to
refer to the root node of the tree. This should be null for an empty tree.
- Your tree methods should only traverse necessary parts of the tree. For
instance,
contains() should only search
the left or right subtree of a node when looking for a particular item.
Simplifying Assumptions
- You only need to implement the listed operations for your set. You do not
need to implement all of the set operations provided by the standard Java
collection classes.
- Similarly, you do not need to implement
previous(), hasPrevious() or remove() for
the
BasicSetIterator.
- You may use a lazy deletion strategy, where deleted nodes
are simply marked as "empty" and are not physically removed from the tree.
- Your code does not need to use generics. As long as it works with arbitrary
Comparable objects that is sufficient.
- You are not required to provide a comprehensive set of tests for your code,
JUnit or otherwise. However, you do need to test your code, and JUnit might
be a useful tool for that.
Hints
Instead of trying to implement everything at once, it would probably be easier
to implement the set as an unbalanced binary tree first, then add the necessary
code to keep the tree balanced as items are added.
The iterator is probably the trickiest part since it is basically doing an
inorder traversal of the tree, but one node at a time each time that next() is
called. To make this work, the iterator needs to keep track of the current
node in the tree reached by the iteration and also all of the anscestors
of that node. After visiting a node and all of its children, the iteration
needs to back up to the parent of the node. If the original node was a left
child of the parent, the iteration next needs to visit the parent and then
its right children. You can keep track of this information
by keeping a stack of the anscestor nodes along with information
needed to remember whether each anscestor and/or its children have been visited
yet. This information should be private data in the iterator class, and you
should feel free to use an appropriate Java library list class to implement
it.
What to turn in
You should include the Java source code
for both the interfaces and implementations of the tree set.
|
