CSE373 Data Structures Wi06, Homework 3

Programming problems due online Thursday, 1/27/06, at 11 pm.
Written problems due at the beginning of class, Friday, 1/27/06, 2:30 pm.
No late assignments will be accepted.

This assignment covers the basics of trees and, in particular, binary search trees (BSTs). We'll get to balanced trees later in the course; work the problems on this homework using unbalanced binary trees.

As usual, your code should not only work properly, but it also should be high-quality. In particular:

• Write clean code - prefer simple and clear to complicated, unless there is a compelling reason, which should be clearly explained in comments. Avoid duplicate code or other situations where the same thing appears in more than one place. Use sensible names, indent clearly, and format your code so it blends cleanly with existing code.
• Use appropriate JavaDoc comments to specify all public classes, interfaces, methods, and any other features of your code that need documenting.

What to do - Written Problems

Answer these questions on a separate sheet of paper. We suggest you do these problems early as part of your preparation for the programming part of the assignment.

1. (Binary search trees)
1. Draw the BST containing integer values that results when these values are inserted in this order: 15, 7, 10, 3, 4, 8, 17, 42, 12.
2. Which nodes are the leaves of this tree? Which node is the root?
3. What is the depth of the node containing 3? What is the height of the node labeled 7?
4. Write down the order in which the node values are reached by (i) a preorder, (ii) an inorder, and (iii) a postorder traversal of the tree.
5. Draw the tree that results if we perform these operations in this order on the original tree: add(9), delete(17), add(13), delete(7).
2. Draw the BST that results when the values from the previous question are inserted in this order: 3, 4, 7, 8, 10, 12, 15, 17, 42. What is the difference in the height of this tree compared to the one in part (a) of the previous question, experssed (roughly) in O() notation.
3. (G&T R-7.14) Draw a single binary tree such that each node contains a single character and a preorder traversal of the tree yields EXAMFUN, and an inorder traversal yields MAFXUEN.
4. (Answer this last question after you're done with the programming part of the assignment.) Write down a chart showing the expected and worst-case running times of each of the operations in your tree set and iterator, expressed in O() notation. In an additional sentance or two, describe why some of the operations have different expected and worst-case times and what could cause this to happen.
5. (Another question to answer after you're done with the programming part.) If we allowed each tree node to contain an additional pointer to its parent, how would this change your implementation of the tree and tree iterator operations? Would it make a significant difference? (Be brief and to the point.)

What to do - Programming

One of the applications of BSTs is to implement ordered sets. A set is a container that contains 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 the set we retrieve the elements in order as defined by the comparison function for those elements. Not visible to the user, but useful in the implementation, is that we can take advantage of the binary search tree to speed up various operations, including searches and modifications of the set.

For this assignment, provide Java interfaces for ordered sets and their iterators and an implementation of those interfaces using a binary search tree as the underlying data structure. Specifically, 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 describes the supported 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 in the iteration. 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 an iterator's next() method.

After defining the interfaces, create an implementation of BasicSet in a class named BasicOrderedTreeSet. That class should contain a nested class BasicOrderedTreeSetIterator that implements the BasicSetIterator interface.

Constraints

1. Your implementation of BasicOrderedTreeSet must use an unbalanced binary tree to store the set items in the order resulting from the add() and remove() operations used to create the set, using the compareTo() method for the set items..
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. These links should be null if the node has no children.
3. A tree node should not contain an extra link referring to its parent.
4. There should be no extra dummy leaf nodes in the tree. All of the tree nodes should refer to items stored in the tree.
5. Use a single instance variable in BasicOrderedTreeSet to refer to the root node of the tree. This should be null for an empty tree.
6. Your tree methods should only traverse parts of the tree that are necessary. 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. Also, you do not need to check for or signal a ConcurrentModificationException in the iterator.
3. 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 verify that it works, and JUnit might be a useful tool for that.

Hints

Implementation of the BST used for the set should be relatively straightforward. The trickiest part is being sure that remove properly deletes items and that the resulting tree is a proper binary tree.

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 list (actually 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.

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 your written questions at the beginning of class, Friday, 1/27.