一种简单的平衡树-AVL树

AVL 树

AVL树（Adelson-Velskii 和 Laandis） 树是 带有平衡条件（balance condition） 的二叉查找树。这个平衡条件必须要容易保持，而且他保证树的深度必须是 O(log N)。最简单的想法是要求左右子树具有相同的高度。

另一种平衡条件是要求每个节点都必须有相同高度的左子树和右子树。如果空子树的高度定义为 -1，那么只有具有 2 ^k -1 个节点的理想平衡树（perfectly balanced tree）满足这个条件。因此，虽然这种平衡条件保证了树的深度小，但是太严格难以使用。

AVL 树是其每个节点的左子树和右子树的高度最多差 1 的二叉查找树（空树的高度定义为 -1）。

下图是一棵具有最少节点（143）和高度为 9 的 AVL 树。这棵树的左子树是高度为 7 且大小最小的 AVL 树，右子树是高度为 8 且大小最小的 AVL 树。他告诉我们，在高度为 h 的 AVL 树种，最少节点数由

• S(h) = S(h - 1) + S(h - 2) + 1 给出

对于 h = 0，S(h) = 1;h = 1, S(h) = 2。函数 S(h) 与斐波那契数列密切相关。

• 在插入以后，只有那些从插入点到根节点的路径上的节点的平衡可能被改变，因为只有这些节点的子树可能发生变化。当我们沿着这条路径上行到根并更新平衡信息时，可以发现一个节点，它的新平衡破坏了 AVL 条件。我们将支出如何在第一个这样的节点（即最深的节点）重新平衡这棵树，并证明这一重新平衡保证整个树满足 AVL 性质。

我们把必须重新平衡的节点叫做 α。由于任意节点最多只有两个儿子，因此出现高度不平衡就需要 α 点的两颗子树的高度差 2。这可能出现在一下四中情况中：

1. 对 α 的左儿子的左子树进行一次插入；

2. 对 α 的左儿子的右子树进行一次插入；

3. 对 α 的右儿子的左子树进行一次插入；

4. 对 α 的右儿子的右子树进行一次插入。

情形 1 和 4 是关于 α 点的镜像对称，而 2 和 3 是关于 α 点的镜像对称。

第一种情况是插入发生在 "外边" 的情况（即左-左的情况或右-右的情况），该情况通过对树的一次 单旋转（single rotation） 而完成调整。第二种情况是插入发生在 "内部" 的情况（即左-右的情况或右-左的情况），该情况通过稍微复杂一些的 双旋转（double rotation） 实现。

情形可能如下所示：

    /**      * 考虑对如下的树中插入数字 2      *       *                 5      *               /   /      *             4      6      *           /   /      *         3       ?      *       *                  4      *               /     /      *             3        5      *           /        /   /      *         2        ?      6      *       * ? 代表可能存在也可能不存在，不会影响结果.并且，在这里，我们可以将 ? 当做 5 的左节点，也可以将       * ? 当做 3 的左节点      * @param k2      * @return      */

• k ₂ 不满足 AVL 平衡性质，因为他的左子树比右子树深 2 层（图中间的虚线表示树的各层）。该图所描述的情况是情形 1 的一种可能的情况，在插入之前 k ₂ 满足 AVL 性质，但是在插入之后，子树 X 长出一层，这使得他比子树 Z 深出 2 层。Y 不可能与新 X 在同一水平上，因为那样 k ₂ 在插入以前就已经失去平衡了；Y 也不可能与 Z 在同一层上，因为那样 k ₁ 就会是在通向根路径上破坏 AVL 平衡条件的第一个节点。

现在我们观察这棵树，我们会得到一些结论：

双旋转

    /**      * 对于情形 2 的一次双旋转      *       *                k3      *               /   /      *            k1      D      *           /   /      *         A       k2      *      * 插入节点 B 或 C，B 和 C 在插入任意一个的时候就已经破坏了 Avl 树的平衡条件      *      *                k3      *               /   /      *            k1       D      *           /   /      *         A       k2      *                / /      *              B    C      *       * k3.left = rotateWithRightChild(k3.left),以 k3.left 即 k1 为根节点进行一次右旋转      *       *                k3      *               /   /      *            k2      D      *           /   /      *         k1       C      *        / /               *      A      B          *       * rotateWithLeftChild(k3)      *       *                  k2      *               /      /      *            k1        k3      *           /   /       /  /      *         A      B    C      D      *       * @param k3      * @return      */

我们注意到，在上面的图中，k ₁ < k ₂ < k ₃ ，这迫使 k ₁ 是 k ₂ 的左儿子，k ₃ 是 k ₂ 的右儿子。于是，最后我们得到的结果就很明显了。

需要旋转的三个节点是：上行找到的第一个破坏 AVL 树的节点，新的节点插入后的父节点，连接第一个破坏 AVL 树的节点和新的节点的父节点 。

不论是单旋转还是双旋转，我们都需要将得到的新的 AVL 子树添加到原来的树中。

AVL 树的插入方法的实现

为了将项是 X 的一个新节点插入到一棵 AVL 树 T 种去，我们递归的将 X 插入到 T 相应的子树（称为 T _LR ）中。如果 T _LR 的高度不变，那么插入完成。否则，如果在 T 中出现高度不平衡，则根据 X 以及 T 和 T _LR 中的项左适当的单旋转或双旋转，更新这些高度（并解决好与树的其余部分的链接）从而完成插入。

package com.mosby.common.structure;  /**  * AVL 树  */ public class AvlTree <T extends Comparable<? super T>> {     private static  class AvlNode <T extends Comparable<? super T>>{         AvlNode(T element){             this(element, null, null);         }         AvlNode(T element, AvlNode<T> left, AvlNode<T> right){             this.element = element;             this.left = left;             this.right = right;             this.height = 0;         }         T element;         AvlNode<T> left;         AvlNode<T> right;         int height;         @Override         public String toString(){             return element.toString();         }     }     public AvlTree(){         root = null;     }     public void insert(T x){         root = insert(x, root);     }          public void remove(T x){         System.out.println("Sorry, remove unimplemented");     }          public T findMin(){         return elementAt(findMin(root));     }     public T findMax(){         return elementAt(findMax(root));     }     public T find(T x){         return elementAt(find(x, root));     }     public void makeEmpty(){         root = null;     }          public boolean isEmpty(){         return root == null;     }     private T elementAt(AvlNode<T> t){         return t == null ? null : t.element;     }     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 AvlNode<T> find(T x, AvlNode<T> 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;             }         }         return null;     }     /**      * 插入方法      * @param x      * @param t      * @return      */     private AvlNode<T> insert(T x, AvlNode<T> t){         if(t == null){             return new AvlNode<T>(x);         }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;     }          /**      * 插入相关操作      */     private static <T extends Comparable<? super T>> int height(AvlNode<T> t){         return t == null ? -1 : t.height;     }     private static int max(int lhs, int rhs){         return lhs > rhs ? lhs : rhs;     }     /**      * 对于情形 1 的一次旋转      *       *                 5      *               /   /      *             4      6      *           /   /      *         3        ?      *       *                  4      *               /      /      *             3         5      *           /         /   /      *         2        ?        6      *       * ? 代表可能存在也可能不存在，不会影响结果      * @param k2      * @return      */     private static <T extends Comparable<? super T>> AvlNode<T> rotateWithLeftChild(AvlNode<T> k2){         //k2 是节点 5，k1 是节点 4         AvlNode<T> k1 = k2.left;         k2.left = k1.right;         k1.right = k2;         /**          * 我们可以看到，节点中有三个节点的高度改变了：3,4,5.          * 而我们在最后插入时的函数栈如下所示：          * 2, null          * ------          * 2,    3          * ------          * 2,    4          * ------          * 2,    5          */         k2.height = max(height(k2.left), height(k2.right)) + 1;         k1.height = max(height(k1.left), height(k1.right)) + 1;         return k1;     }     /**      * 对于情形 4 的一次旋转      *       *                 5      *               /   /      *             4        6      *                    /  /      *                  ?      7      *       *       *                  6      *               /   /      *             5        7      *           /   /       /      *         4        ?     8      *       * @param k1      * @return      */     private static<T extends Comparable<? super T>> AvlNode<T> rotateWithRightChild(AvlNode<T> k1){         //k1 是节点 5，k2 是节点 6         AvlNode<T> k2 = k1.right;         k1.right = k2.left;         k2.left = k1;         /**          * 节点中有 3 个节点的高度改变了：5,6,7          * 在最后插入时的函数栈如下所示：          * 8, null          * ------          * 8,   7          * ------          * 8,   6          * ------          * 8,   5          */         k1.height = max(height(k1.left), height(k1.right)) + 1;         k2.height = max(height(k2.left), height(k2.right)) + 1;         return k2;     }          /**      * 对于情形 2 的一次双旋转      *       *                k3      *               /  /      *            k1     D      *           /   /      *         A       k2      *      * 插入节点 B 或 C，B 和 C 在插入任意一个的时候就已经破坏了 Avl 树的平衡条件      *      *                k3      *               /  /      *            k1     D      *           /   /      *         A       k2      *                / /      *              B       C      *       * k3.left = rotateWithRightChild(k3.left),以 k3.left 即 k1 为根节点进行一次右旋转      *       *                k3      *               /  /      *            k2     D      *           /   /      *         k1       C      *        / /               *      A      B          *       * rotateWithLeftChild(k3)      *       *                  k2      *               /      /      *            k1         k3      *           /   /      /  /      *         A      B   C     D      *       * @param k3      * @return      */     private static <T extends Comparable<? super T>> AvlNode<T> doubleWithLeftChild(AvlNode<T> k3){         /**          * k1 是节点 4，k2 是节点 5，k3 是节点 7          * 我们看到，在第一次旋转中，有几个节点的高度改变了：k2、k3          * 在插入的时候，函数栈应该如下所示：          * B|C  null          * --------          * B|C   k2          * --------          * B|C   k1          * --------          * B|C   k3          */         k3.left = rotateWithRightChild(k3.left);         return rotateWithLeftChild(k3);     }     private static <T extends Comparable<? super T>> AvlNode<T> doubleWithRightChild(AvlNode<T> k1){         k1.right = rotateWithLeftChild(k1.right);         return rotateWithRightChild(k1);     }     private AvlNode<T> root;          public static void main(String[] args) {         AvlTree<Integer> avl = new AvlTree<Integer>();         avl.insert(5);         avl.insert(4);         avl.insert(3);         avl.insert(2);         avl.insert(1);         avl.insert(0);     } }