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:
- 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.
- 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.
- Have each node in the search tree store its parent in addition to
the children. The code to iterate is still clumsy.
- 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,
- Make the Node class nested
- Add a comparator, and appropriate constructor
- Maintain the size as a data field, updating it during add
and remove.
- Change basic method names, and contracts (i.e. insert
no longer throws an exception).
- Public add can check if the size changed to decide if
it returns true or false
- Add a toString, which can use the iterator to step through
the Set and make sure you use a StringBuffer
- 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.