#
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);