Assignment #4: Binary Search Trees


In this assignment, you will implement the cop3530.Set interface from Assignment #1 using a binary search tree. You binary search tree DOES NOT have to be balanced. WARNING: Assignment is a little tricky, and I will discuss details in class. Make sure you are in class!!!! Please do not ask me to re-explain material that you were not present for.

Covers

Linked data structures, binary search trees, Java programming

Testing the Class

I will provide a program to test your implementation. It is basically the same program as in Assignment #1, except that the number of operations and the size of the set are both significantly larger. Compile the program, and give me the output. Warning: you should probably write another program to make sure everything works.

Requirements

Recall the cop3530.Set interface is as follows:

package cop3530;

public interface Set<AnyType> extends Iterable<AnyType>
{
    boolean isEmpty( );
    int getSize( );
   
    boolean add( AnyType x );
    boolean remove( AnyType x );
    boolean contains( AnyType x );
   
    java.util.Iterator<AnyType> iterator( );   
}

Were it not for the iterator method, it would be trivial to implement this interface by directly using some of the code in Section 19.1 of the text book. In such a case, the class implementation would store a reference to the root, a comparator, and the size of the set as data members. The hard part is implementing the Iterator interface, which allows you to advance through the Set in sorted order. The reason this is difficult is that it is hard to get from one node to the next. There are several plausible solutions, some of which are listed here:
  1. When the iterator is constructed, have each iterator store as its data an array containing the set items. This makes it trivial to traverse the collection, but it makes each iterator large. Cosmetically, it is a bad plan because the point of using an iterator is to avoid using toArray, and this implementation in effect uses toArray behind the scenes.
  2. Have the iterator maintain a stack storing nodes on the path to the current node. With this information, one can deduce the next node. This uses less space, but makes the iterator code clumsy.
  3. Have each node in the search tree store its parent in addition to the children. The code to iterate is still clumsy.
  4. Have each node maintain extra links: one to the next smaller, and one to the next larger node. This takes space, but the iteration is very simple to do.
In this assignment you must use the third option, keeping a pointer to the parent for every node in the tree.

In TreeSet, first observe that each node stores three links. Operations that update the tree must be rewritten to ensure that parent nodes are correctly maintained, while other tree operations that only access the tree are essentially unchanged.

When performing iteration, the iterator maintains a reference to the next node to be viewed. The hard part is advancing. If the current node has a right child, then you advance to the leftmost node in the current node's right subtree. Otherwise, you go up the tree to find the next node.

Notes

From the basic BinarySearchTree code in Chapter 19,
  1. Make the Node class nested
  2. Add a comparator, and appropriate constructor
  3. Maintain the size as a data field, updating it during add and remove.
  4. Change basic method names, and contracts (i.e. insert no longer throws an exception).
  5. Public add can check if the size changed to decide if it returns true or false
  6. Add a toString, which can use the iterator to step through the Set and make sure you use a StringBuffer
  7. Add an iterator method, and an implementation of java.util.Iterator as an inner class.

Submission Procedure

Submit all your source code, and the results of running the test program. Your source code should include a signed disclaimer that states the work is your own. Your submission must be stapled or otherwise bound together. Failure to follow these instructions will adversely affect your grade for the assignment.