AVL树

定义

AVL树（Adelson-Velskii 和 Landis）是一种带有平衡条件的二叉查找树。它的平衡条件是：一颗AVL树的每个节点的左子树和右子树的高度最多差1。如下图所示。

可以证明AVL树实际上的高度只略大于log(N)，因此对于所有的树操作，除去可能的插入（假设懒惰删除），都可以以时间O(logN)执行。而插入操作的困难在于，插入一个节点可能会破坏AVL树的平衡条件，比如在上图的AVL树中插入节点6，将会破坏节点8处的平衡条件（8的左子树高度将为2，右子树高度为0）。对于这种情况，我们将采用旋转操作来进行修正。

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

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

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

AVL树的节点定义相比一般的二叉查找树，多了一个记录节点高度的字段。

旋转

假设必须重新平衡的节点叫做，那么的两颗子树的高度相差2。容易看出，这种不平衡可能出现在下面四种情况中：

1. 对的左儿子的左子树进行一次插入
2. 对的左儿子的右子树进行一次插入
3. 对的右儿子的左子树进行一次插入
4. 对的右儿子的右子树进行一次插入

第一种和第四种情况，属于同一种，是插入发生在“外边”的情况，该情况通过对树的一次单旋转可以完成调整。第二种和第三种情况，属于同一种，是插入发生在“内部”的情况，该情况通过双旋转可以完成调整。这两种旋转操作，都是对树的基本操作，在很多树的数据结构中都会用到。

单旋转

对于情形1，如上图所示，k2是必须重新平衡的节点。我们的做法，抽象地形容就是：把树看成是柔软灵活的，抓住子节点k1，使劲摇动它，在重力作用下，k1就变成了新的根，k2变成了k1的右儿子，子树X和Z仍然分别是k1的左子树和k2的右子树。子树Y在原树中介于k1和k2之间，在新树中成为k2的左子树，仍然介于k1和k2之间。这样一来，整个树的新高度恰恰与插入前原树的高度相同，而插入操作使得子树X长高了。
可以将这种旋转记为右旋转（rotateWithLeftChild），使左儿子代替自己成为子树新根。代码实现如下。

    /**
     * Return the height of node t, or -1, if null.
     */
    private int height( AvlNode<AnyType> 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<AnyType> rotateWithLeftChild( AvlNode<AnyType> k2 )
    {
        AvlNode<AnyType> 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;
    }

对于情形4，如上图所示。与情形1是镜像对称的，也可以通过单旋转完成。
可以将这种旋转记为左旋转（rotateWithRightChild），使右儿子代替自己成为子树新根。代码实现如下。

/**
     * 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<AnyType> rotateWithRightChild( AvlNode<AnyType> k1 )
    {
        AvlNode<AnyType> 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;
    }

双旋转

上面单旋转的算法无法解决情形2和3，如下图所示。单旋转之后的情形，仍然是不平衡的，情形2通过单旋转恰巧成了情形3，情形3通过单旋转恰巧成了情形2。

对于情形2和情形3这种插入发生在“内部”的情况，需要通过双旋转来调整。所谓的双旋转只不过是通过连续的两次单旋转实现。如下图所示。

图中的B和C子树只需任意一颗子树比D深2层即可；在这两种情况下，都是先在的儿子和孙子之间旋转，然后再在和它的新儿子之间旋转完成调整。具体的例子如下图所示。

  /**
     * 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<AnyType> doubleWithLeftChild( AvlNode<AnyType> 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<AnyType> doubleWithRightChild( AvlNode<AnyType> k1 )
    {
        k1.right = rotateWithLeftChild( k1.right );
        return rotateWithRightChild( k1 );
    }

AVL树的插入操作

为了将X插入到一颗AVL树T中去，我们递归地将X插入到T的相应子树（称为）中。如果的高度不变，那么插入完成。否则，如果在T中出现高度不平衡的节点，通过做适当的单旋转或者双旋转，调整更新这些高度，从而完成插入。代码如下所示。

    /**
     * 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<AnyType> insert( AnyType x, AvlNode<AnyType> t )
    {
        if( t == null )
            return new AvlNode<AnyType>( x, null, null );
        
        int compareResult = x.compareTo( t.element );
        
        if( compareResult < 0 )
            t.left = insert( x, t.left );
        else if( compareResult > 0 )
            t.right = insert( x, t.right );
        else
            ;  // Duplicate; do nothing
        return balance( t );
    }

private AvlNode<AnyType> balance( AvlNode<AnyType> t )
    {
        if( t == null )
            return t;
        
        if( height( t.left ) - height( t.right ) > ALLOWED_IMBALANCE )
            if( height( t.left.left ) >= height( t.left.right ) )
                t = rotateWithLeftChild( t );
            else
                t = doubleWithLeftChild( t );
        else
        if( height( t.right ) - height( t.left ) > ALLOWED_IMBALANCE )
            if( height( t.right.right ) >= height( t.right.left ) )
                t = rotateWithRightChild( t );
            else
                t = doubleWithRightChild( t );

        t.height = Math.max( height( t.left ), height( t.right ) ) + 1;
        return t;
    }