CSE373 Data Structures Wi07, Homework 4

Due online Thursday, 2/1/07, at 11 pm.
Written printout due at the beginning of class, Friday, 2/2.
No late assignments will be accepted.

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:

1. 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.
2. 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

1. 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.
2. Tree nodes should be defined as a private class inside BasicOrderedTreeSet. 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.
3. Use a single instance variable in BasicOrderedAVLTreeSet to refer to the root node of the tree. This should be null for an empty tree.
4. 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

1. 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.
2. Similarly, you do not need to implement previous(), hasPrevious() or remove() for the BasicSetIterator.
3. You may use a lazy deletion strategy, where deleted nodes are simply marked as "empty" and are not physically removed from the tree.
4. Your code does not need to use generics. As long as it works with arbitrary Comparable objects that is sufficient.
5. 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.

Extra Credit

A small amount of extra credit will be awarded for interesting extensions. A few suggestions:

1. When an item is deleted from the tree, remove the corresponding node instead of just marking it empty, and rebalance the tree as needed.
2. Add generics so that you can create BasicSet<T> for any type T that implements Comparable<T>.
3. Create a mechanism to print or visualize the structure of the tree to help verify that the balance operations are working properly.

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

Turn in your programming assignment online using the turnin form linked from the course web site (when available). You should include the Java source code for both the interfaces and implementations of the tree set.

Turn in a printed copy of your code at the beginning of class, Friday, 2/2.