AVL树及JAVA实现

  一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。

  在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。这样就可以得到AVL 树。



平衡调整的4种基本类型：


AVL树及JAVA实现

public class AvlTree<T extends Comparable<? super T>>
{

     private static class AvlNode<T>{//avl树节点
        
        AvlNode( T theElement )
        {
            this( theElement, null, null );
        }

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

        T           element;      // 节点中的数据
        AvlNode<T>  left;         // 左儿子
        AvlNode<T>  right;        // 右儿子
        int         height;       // 节点的高度
    }

     
    private AvlNode<T> root;//avl树根
   
    public AvlTree( )
    {
        root = null;
    }

   //在avl树中插入数据，重复数据复略
    public void insert( T x )
    {
        root = insert( x, root );
    }
   
    //在avl中删除数据,没有实现
    public void remove( T x )
    {
        System.out.println( "Sorry, remove unimplemented" );
    }

  
     //在avl树中找最小的数据
    public T findMin( )
    {
        if( isEmpty( ) )
            throw new UnderflowException( );
        return findMin( root ).element;
    }

    //在avl树中找最大的数据
    public T findMax( )
    {
        if( isEmpty( ) )
            throw new UnderflowException( );
        return findMax( root ).element;
    }

   //搜索
    public boolean contains( T x )
    {
        return contains( x, root );
    }

   
    public void makeEmpty( )
    {
        root = null;
    }

    
    public boolean isEmpty( )
    {
        return root == null;
    }

    //排序输出avl树
    public void printTree( )
    {
        if( isEmpty( ) )
            System.out.println( "Empty tree" );
        else
            printTree( root );
    }
    
   
    private AvlNode<T> insert( T x, AvlNode<T> t )
    {
        if( t == null )
            return new AvlNode<T>( x, null, null );
        
        int compareResult = x.compareTo( t.element );
        
        if( compareResult < 0 )
        {
            t.left = insert( x, t.left );//将x插入左子树中
            if( height( t.left ) - height( t.right ) == 2 )//打破平衡
                if( x.compareTo( t.left.element ) < 0 )//LL型（左左型）
                    t = rotateWithLeftChild( t );
                else   //LR型（左右型）
                    t = doubleWithLeftChild( t );
        }
        else if( compareResult > 0 )
        {
            t.right = insert( x, t.right );//将x插入右子树中
            if( height( t.right ) - height( t.left ) == 2 )//打破平衡
                if( x.compareTo( t.right.element ) > 0 )//RR型（右右型）
                    t = rotateWithRightChild( t );
                else                           //RL型
                    t = doubleWithRightChild( t );
        }
        else
            ;  // 重复数据，什么也不做
        t.height = Math.max( height( t.left ), height( t.right ) ) + 1;//更新高度
        return t;
    }

   
     //找最小
    private AvlNode<T> findMin( AvlNode<T> t )
    {
        if( t == null )
            return t;

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

    //找最大
    private AvlNode<T> findMax( AvlNode<T> t )
    {
        if( t == null )
            return t;

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

    //搜索（查找）
    private boolean contains( T x, AvlNode<T> 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
    }

   //中序遍历avl树
    private void printTree( AvlNode<T> t )
    {
        if( t != null )
        {
            printTree( t.left );
            System.out.println( t.element );
            printTree( t.right );
        }
    }

  //求高度
    private int height( AvlNode<T> t )
    {
        return t == null ? -1 : t.height;
    }

    //带左子树旋转,适用于LL型
    private AvlNode<T> rotateWithLeftChild( AvlNode<T> k2 )
    {
        AvlNode<T> 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;
    }

    //带右子树旋转，适用于RR型
    private AvlNode<T> rotateWithRightChild( AvlNode<T> k1 )
    {
        AvlNode<T> 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;
    }

    //双旋转，适用于LR型
    private AvlNode<T> doubleWithLeftChild( AvlNode<T> k3 )
    {
        k3.left = rotateWithRightChild( k3.left );
        return rotateWithLeftChild( k3 );
    }

    //双旋转,适用于RL型
    private AvlNode<T> doubleWithRightChild( AvlNode<T> k1 )
    {
        k1.right = rotateWithLeftChild( k1.right );
        return rotateWithRightChild( k1 );
    }

  


        // Test program
    public static void main( String [ ] args )
    {
        AvlTree<Integer> t = new AvlTree<Integer>( );
        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!" );
    }
}

运行：
C:\java>java  AvlTree
Checking... (no more output means success)

源码：