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:
  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 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.