Assignment #3: Balanced Binary Search Trees

Due: Oct 24 before class

The Problem

In this assignment you will provide modified implementations of a Balanced Binary Search Tree, whose interface is specified as shown below.

package cop3530;
public interface BalancedBST<AnyType> { 
    void insert (AnyType x); 
    void remove (AnyType x); 
    boolean contains (AnyType x); 
    boolean isEmpty ( ); 
    void makeEmpty ( );
    void printTree ( );
    int rank (AnyType x);
}

Duplicates should not be inserted. Inserting a duplicate should result in an error message before moving on to the next command. If the remove operation is invoked on an empty BalancedBST, then you should simply print an error message and move on to the next command. If the contains method is invoked on an empty BalancedBST, then you should simply return false. The printTree method must print the tree in sorted order (one item per line) in LINEAR TIME. The output format must be similar to the tree shown in Figure 4.7 (reproduced here from p105 in your text book). As in that figure, the output needs to be tabbed according to the level of the node. The difference is that Figure 4.7 is shown in preorder, but printTree must print in sorted order.

The method rank(AnyType x) must return the rank of the item x. Note that the "rank" of an item in a list is its position in the sorted order. Thus the smallest item must have rank 1, and the largest item must have rank equal to the size of the entire tree.

As in the previous assignment, the test program will be provided as a .class file, without any Java source, so it is important that you write sufficient test cases on your own to convince yourself that your logic works.

Implementation Details

The implementation must use a modified AvlTree. The main modification is that each AvlTree node includes an extra field called size, which is the size of the subtree rooted at that node. You may not add any other fields to the tree node. A sketch of the private representation of a node looks something like this:

     private static class AvlNode<AnyType> {
        AvlNode<AnyType> left;
        AvlNode<AnyType> right;
        AnyType element;
        int height;
        int size;
    }

The methods insert and remove that are given in your text (p134 and p136) need to be modified so that it updates the size value stored in the nodes of the tree. Similarly, the balancing procedures, rotateWithLeftChild and doubleWithLeftChild, which are integral to the implementation of rebalancing in AVL Trees, must be modified so that the size values stored in the nodes are correct after the rotation.

The public method rank (AnyType x) should call a private (recursive) method rank (AnyType x, AvlNode t), which returns the rank of x in the subtree rooted at node t. It may be useful for you to understand that if x is equal to t.element, then rank (AnyType x, AvlNode t) must return the integer t.left.size + 1. Else, it needs to make a recursive call.

Your implementation class must be cop3530.AvlTree.

What to Submit

Submit your source code and the result of running the class file that I provide.

Extra Credit

Add the method select(k) that returns the item with rank k

      AnyType select(int k);