Avl tre problem code

package DataStructures;

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x (unimplemented)
// Comparable find( x ) --> Return item that matches x
// 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

/**
* Implements an AVL tree.
* Note that all "matching" is based on the compareTo method.
* @author Mark Allen Weiss
*/
package org.apache.commons.collections.list;

import java.util.AbstractList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;

import org.apache.commons.collections.OrderedIterator;
public class avl{

/**
* A List implementation that is optimised for fast insertions and
* removals at any index in the list.
*
* This list implementation utilises a tree structure internally to ensure that
* all insertions and removals are O(log n). This provides much faster performance
* than both an ArrayList and a LinkedList where elements
* are inserted and removed repeatedly from anywhere in the list.
* public class TreeList extends AbstractList {
// add; toArray; iterator; insert; get; indexOf; remove
// TreeList = 1260;7360;3080; 160; 170;3400; 170;
// ArrayList = 220;1480;1760; 6870; 50;1540; 7200;
// LinkedList = 270;7360;3350;55860;290720;2910;55200;

/** The root node in the AVL tree */
private AVLNode root;

/** The current size of the list */
private int size;

//-----------------------------------------------------------------------
/**
* Constructs a new empty list.
*/
public TreeList() {
super();

}

/**
* Constructs a new empty list that copies the specified list.
*
* @param coll the collection to copy
* @throws NullPointerException if the collection is null
*/
public TreeList(Collection coll) {
super();
addAll(coll);
}

//-----------------------------------------------------------------------
/**
* Gets the element at the specified index.
*
* @param index the index to retrieve
* @return the element at the specified index
*/
public Object get(int index) {
checkInterval(index, 0, size() - 1);
return root.get(index).getValue();
}

/**
* Gets the current size of the list.
*
* @return the current size
*/
public int size() {
return size;
}

/**
* Gets an iterator over the list.
*
* @return an iterator over the list
*/
public Iterator iterator() {
// override to go 75% faster
return listIterator(0);
}

/**
* Gets a ListIterator over the list.
*
* @return the new iterator
*/
public ListIterator listIterator() {
// override to go 75% faster
return listIterator(0);
}

/**
* Gets a ListIterator over the list.
*
* @param fromIndex the index to start from
* @return the new iterator
*/
public ListIterator listIterator(int fromIndex) {
// override to go 75% faster
// cannot use EmptyIterator as iterator.add() must work
checkInterval(fromIndex, 0, size());
return new TreeListIterator(this, fromIndex);
}

/**
* Searches for the index of an object in the list.
*
* @return the index of the object, -1 if not found
*/
public int indexOf(Object object) {
// override to go 75% faster
if (root == null) {
return -1;
}
return root.indexOf(object, root.relativePosition);
}

/**
* Searches for the presence of an object in the list.
*
* @return true if the object is found
*/
public boolean contains(Object object) {
return (indexOf(object) >= 0);
}

/**
* Converts the list into an array.
*
* @return the list as an array
*/
public Object[] toArray() {
// override to go 20% faster
Object[] array = new Object[size()];
if (root != null) {
root.toArray(array, root.relativePosition);
}
return array;
}

//-----------------------------------------------------------------------
/**
* Adds a new element to the list.
*
* @param index the index to add before
* @param obj the element to add
*/
public void add(int index, Object obj) {
modCount++;
checkInterval(index, 0, size());
if (root == null) {
root = new AVLNode(index, obj, null, null);
} else {
root = root.insert(index, obj);
}
size++;
}

/**
* Sets the element at the specified index.
*
* @param index the index to set
* @param obj the object to store at the specified index
* @return the previous object at that index
* @throws IndexOutOfBoundsException if the index is invalid
*/
public Object set(int index, Object obj) {
checkInterval(index, 0, size() - 1);
AVLNode node = root.get(index);
Object result = node.value;
node.setValue(obj);
return result;
}

/**
* Removes the element at the specified index.
*
* @param index the index to remove
* @return the previous object at that index
*/
public Object remove(int index) {
modCount++;
checkInterval(index, 0, size() - 1);
Object result = get(index);
root = root.remove(index);
size--;
return result;
}

/**
* Clears the list, removing all entries.
*/
public void clear() {
modCount++;
root = null;
size = 0;
}

//-----------------------------------------------------------------------
/**
* Checks whether the index is valid.
*
* @param index the index to check
* @param startIndex the first allowed index
* @param endIndex the last allowed index
* @throws IndexOutOfBoundsException if the index is invalid
*/
private void checkInterval(int index, int startIndex, int endIndex) {
if (index < startIndex || index > endIndex) {
throw new IndexOutOfBoundsException("Invalid index:" + index + ", size=" + size());
}
}
}

public class AvlTree

{
private AvlTree t;
/**
* Construct the tree.
*/
public AvlTree( )
{
root = null;
}

/**
* Insert into the tree; duplicates are ignored.
* @param x the item to insert.
*/
public void insert( Comparable 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( Comparable x )
{
System.out.println( "Sorry, remove unimplemented" );
}

/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin( )
{
return elementAt( findMin( root ) );
}

/**
* Find the largest item in the tree.
* @return the largest item of null if empty.
*/
public Comparable findMax( )
{
return elementAt( findMax( root ) );
}

/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x )
{
return elementAt( find( 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 get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( AvlNode t )
{
return t == null ? null : t.element;
}

/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
*/
private AvlNode insert( Comparable x, AvlNode t )
{
if( t == null )
t = new AvlNode( x, null, null );
else if( x.compareTo( t.element ) < 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( x.compareTo( t.element ) > 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 = 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 node containing the matched item.
*/
private AvlNode find( Comparable x, AvlNode t )
{
while( t != null )
if( x.compareTo( t.element ) < 0 )
t = t.left;
else if( x.compareTo( t.element ) > 0 )
t = t.right;
else
return t; // Match

return null; // 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 static int height( AvlNode t )
{
return t == null ? -1 : t.height;
}

/**
* Return maximum of lhs and rhs.
*/
private static int max( int lhs, int rhs )
{
return lhs > rhs ? lhs : rhs;
}

/**
* 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 static AvlNode rotateWithLeftChild( AvlNode k2 )
{
AvlNode k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = max( height( k2.left ), height( k2.right ) ) + 1;
k1.height = 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 static AvlNode rotateWithRightChild( AvlNode k1 )
{
AvlNode k2 = k1.right;
k1.right = k2.left;
k2.left = k1;
k1.height = max( height( k1.left ), height( k1.right ) ) + 1;
k2.height = 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 static 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 static AvlNode doubleWithRightChild( AvlNode k1 )
{
k1.right = rotateWithLeftChild( k1.right );
return rotateWithRightChild( k1 );
}

/** 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( new MyInteger( i ) );

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

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