AVL Tree using Java

// AvlTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x (unimplemented)
// boolean contains( x ) --> Return true if x is present
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
// void printTree( ) --> Print tree in sorted order
// ******************ERRORS********************************
// Throws UnderflowException as appropriate

/**
* Implements an AVL tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
public class AvlTree>
{
/**
* Construct the tree.
*/
public AvlTree( )
{
root = null;
}

/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( AnyType x )
{
root = insert( x, root );
}

/**
* Remove from the tree. Nothing is done if x is not found.
* @param x the item to remove.
*/
public void remove( AnyType x )
{
System.out.println( "Sorry, remove unimplemented" );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public AnyType findMin( )
{
if( isEmpty( ) )
throw new UnderflowException( );
return findMin( root ).element;
}

/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public AnyType findMax( )
{
if( isEmpty( ) )
throw new UnderflowException( );
return findMax( root ).element;
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return true if x is found.
*/
public boolean contains( AnyType x )
{
return contains( x, root );
}

/**
* Make the tree logically empty.
*/
public void makeEmpty( )
{
root = null;
}

/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return root == null;
}

/**
* Print the tree contents in sorted order.
*/
public void printTree( )
{
if( isEmpty( ) )
System.out.println( "Empty tree" );
else
printTree( root );
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the subtree.
* @return the new root of the subtree.
*/
private AvlNode insert( AnyType x, AvlNode t )
{
if( t == null )
return new AvlNode( x, null, null );

int compareResult = x.compareTo( t.element );

if( compareResult < 0 )
{
t.left = insert( x, t.left );
if( height( t.left ) - height( t.right ) == 2 )
if( x.compareTo( t.left.element ) < 0 )
t = rotateWithLeftChild( t );
else
t = doubleWithLeftChild( t );
}
else if( compareResult > 0 )
{
t.right = insert( x, t.right );
if( height( t.right ) - height( t.left ) == 2 )
if( x.compareTo( t.right.element ) > 0 )
t = rotateWithRightChild( t );
else
t = doubleWithRightChild( t );
}
else
; // Duplicate; do nothing
t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
return t;
}

/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
private AvlNode findMin( AvlNode t )
{
if( t == null )
return t;

while( t.left != null )
t = t.left;
return t;
}

/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private AvlNode findMax( AvlNode t )
{
if( t == null )
return t;

while( t.right != null )
t = t.right;
return t;
}

/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return true if x is found in subtree.
*/
private boolean contains( AnyType x, AvlNode t )
{
while( t != null )
{
int compareResult = x.compareTo( t.element );

if( compareResult < 0 )
t = t.left;
else if( compareResult > 0 )
t = t.right;
else
return true; // Match
}

return false; // No match
}

/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree( AvlNode t )
{
if( t != null )
{
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}

/**
* Return the height of node t, or -1, if null.
*/
private int height( AvlNode t )
{
return t == null ? -1 : t.height;
}

/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then return new root.
*/
private AvlNode rotateWithLeftChild( AvlNode k2 )
{
AvlNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = Math.max( height( k1.left ), k2.height ) + 1;
return k1;
}

/**
* Rotate binary tree node with right child.
* For AVL trees, this is a single rotation for case 4.
* Update heights, then return new root.
*/
private AvlNode rotateWithRightChild( AvlNode k1 )
{
AvlNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = Math.max( height( k2.right ), k1.height ) + 1;
return k2;
}

/**
* Double rotate binary tree node: first left child
* with its right child; then node k3 with new left child.
* For AVL trees, this is a double rotation for case 2.
* Update heights, then return new root.
*/
private AvlNode doubleWithLeftChild( AvlNode k3 )
{
k3.left = rotateWithRightChild( k3.left );
return rotateWithLeftChild( k3 );
}

/**
* Double rotate binary tree node: first right child
* with its left child; then node k1 with new right child.
* For AVL trees, this is a double rotation for case 3.
* Update heights, then return new root.
*/
private AvlNode doubleWithRightChild( AvlNode k1 )
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}

private static class AvlNode
{
// Constructors
AvlNode( AnyType theElement )
{
this( theElement, null, null );
}

AvlNode( AnyType theElement, AvlNode lt, AvlNode rt )
{
element = theElement;
left = lt;
right = rt;
height = 0;
}

AnyType element; // The data in the node
AvlNode left; // Left child
AvlNode right; // Right child
int height; // Height
}

/** The tree root. */
private AvlNode root;


// Test program
public static void main( String [ ] args )
{
AvlTree t = new AvlTree( );
final int NUMS = 4000;
final int GAP = 37;

System.out.println( "Checking... (no more output means success)" );

for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( i );

if( NUMS < 40 )
t.printTree( );
if( t.findMin( ) != 1 || t.findMax( ) != NUMS - 1 )
System.out.println( "FindMin or FindMax error!" );

for( int i = 1; i < NUMS; i++ )
if( !t.contains( i ) )
System.out.println( "Find error1!" );
}
}