Assignment #4: Binary Search Trees and Linked Lists
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, linked lists, 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 Section19.1 of the text book. In such a case, the class
implementation would store a reference to the root 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
last option, keeping a dummy header and tail in the linked list
part of the nodes.
Here is the rough outline of the implementation:
package cop3530;
import java.util.Comparator;
import java.util.NoSuchElementException;
public class TreeSet<AnyType> implements Set<AnyType>
{
public TreeSet( )
{ this( null ); }
public TreeSet( Comparator<? super AnyType> c )
{ /* Implementation not shown */ }
public boolean isEmpty( )
{ /* Implementation not shown */ }
public int getSize( )
{ /* Implementation not shown */ }
public boolean add( AnyType x )
{
int oldSize = getSize( );
root = add( x, root,
beginMarker, endMarker );
return getSize( ) != oldSize;
}
// Precondition: x's position will be after low and
before high
// Postcondition: x is added to tree t if it is not
already there,
/
and resulting tree is returned
private Node<AnyType> add( AnyType x,
Node<AnyType> t, Node<AnyType> low, Node<AnyType>
high )
{ /* Implementation not shown */ }
public boolean remove( AnyType x )
{ /* Implementation not shown */ }
private Node<AnyType> remove( AnyType x,
Node<AnyType> t )
{ /* Implementation not shown */ }
private Node<AnyType> findMin(
Node<AnyType> t )
{ /* Implementation not shown */ }
private
Node<AnyType> removeMin( Node<AnyType> t )
{ /* Implementation not shown */ }
public boolean contains( AnyType x )
{ /* Implementation not shown */ }
private class LocalIterator implements
java.util.Iterator<AnyType>
{
public boolean hasNext( )
{ /* Implementation not
shown */ }
public AnyType next( )
{ /* Implementation not shown
*/ }
public void remove( )
{ /* Implementation not
shown */ }
private Node<AnyType>
current = beginMarker.next;
private boolean okToRemove =
false;
}
public java.util.Iterator<AnyType> iterator( )
{ return new LocalIterator( ); }
private int compare( AnyType lhs, AnyType rhs )
{
if( cmp != null )
return cmp.compare( lhs, rhs );
else
return ((Comparable)lhs).compareTo( rhs );
}
public String toString( )
{ /* Implementation not shown */ }
private static class Node<AnyType>
{
/* Constructor not shown */
AnyType data;
Node<AnyType> left;
Node<AnyType> right;
Node<AnyType> previous;
Node<AnyType> next;
}
private Node<AnyType> root = null;
private Node<AnyType> beginMarker;
private Node<AnyType> endMarker;
private
int theSize = 0;
private Comparator<? super AnyType> cmp;
}
In TreeSet,
first observe that each node stores four links. When performing contains,
only left and right are used. When performing iteration, only next is
used. Both recursive routines add and remove must
update theSize
when a node is created and removed, respectively. When a node is
created or removed in addition to the standard adjustments to left and
right, care must be taken to adjust next and previous of
the affected nodes. There are only a few lines of code needed to do
this, but needless to say it is trickier than it looks, because these
adjustments need to be made at the correct place in the code, and you
will have a hard time doing this if you do not draw some pictures.
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.