13、AVL 树 - 《数据结构》

一：什么是 AVL 树？
二：AVL 树的实现
三：AVL 树与二分搜索树的性能测试
四：总结

【数据结构与算法基础】代码仓库：https://github.com/jinrunheng/datastructure-and-algorithm

一：什么是 AVL 树？

在我的上一篇文章《二分搜索树与二分查找法》中，详细介绍了二分搜索树这种数据结构。二分搜索树最大的问题就是它并非是一棵平衡二叉树。

在给定的数据比较极端的情况下，譬如将一个递增数组中的元素依次添加到二分搜索树中，此时的二分搜素树就会退化为一个链表。

为了解决二分搜索树的这个问题，两位前苏联的计算机科学家 Georgy Adelson-Velsky 与 Evgenii Landis 发明了一种可以自平衡的二叉查找树，这种数据结构以两位科学家的名字的首字母命名，即：AVL 树。

13、AVL 树 - 图1

我们再来回顾一下什么是平衡二叉树？

首先，平衡二叉树必须是一棵二分搜索树。它或者是一颗空树，或它的左子树与右子树的高度之差（左子树的高度 - 右子树的高度，其别名叫平衡因子：balance factor）的绝对值不超过 1，且一棵平衡二叉树的左右子树均是一棵平衡二叉树。

13、AVL 树 - 图2

接下来，我们就一起探究一下 AVL 树这种数据结构是如何在二分搜索树的基础上做到可以自平衡的。

二：AVL 树的实现

1. 节点高度与平衡因子

AVL 树是如何实现自平衡的？

AVL 想要满足平衡二叉树的这个特性，就要保证所有节点的平衡因子的绝对值不超过 1。所以，AVL 树能够做到维持自平衡，实际上就是在树的结构发生变化时（向 AVL 中添加节点或删除节点），通过检测节点的平衡因子来调整树的结构。

AVL 树的节点除了存储左孩子与右孩子的引用以及自身的 value 值以外，还需要能够表示出当前节点的高度。

所以，AVL 树的节点类 Node 设计如下：

public class Node<E extends Comparable<E>> {
    public E e;
    public Node left;
    public Node right;
    public int height;
    public Node(E e) {
        this.e = e;
        left = null;
        right = null;
        height = 1;
    }
}

那么，在我们的 AVLTree 这个类中，就可以设计出两个方法。

第一个是获取当前节点的高度的方法：getHeight:

/**
 * 返回 node 节点的高度
 *
 * @param node
 * @return
 */
private int getHeight(Node node) {
    if (node == null)
        return 0;
    return node.height;
}

第二个是获取当前节点的平衡因子：getBalanceFactor:

/**
 * 获得节点 node 的平衡因子
 *
 * @param node
 * @return
 */
 private int getBalanceFactor(Node node) {
    if (node == null)
        return 0;
    return getHeight(node.left) - getHeight(node.right);
}

2. 向 AVL 树中添加元素

我们先来回顾一下向二分搜索树中添加元素的逻辑：

如果当前二分搜索树的根节点为空，那么新插入的节点就会成为根节点。

如果当前二分搜索树的根节点不为空，就让根作为当前比较的节点：新插入的节点与当前节点进行比较；如果值比当前节点小就要“向左走”，如果值比当前节点大就要“向右走”，然后让下一层的节点继续作为当前比较的节点，直至走到应该插入的位置。

下图为在向当前的二分搜索树中添加节点“28”的流程：

13、AVL 树 - 图3

Java 代码如下：

/**
 * @param e 向二分搜索树中添加新的元素
 */
public void add(E e) {
    root = add(e, root);
}
/**
 * @param e    向二分搜索树中新插入的节点
 * @param node 当前比较的节点
 * @return 返回二分搜索树的根节点
 */
private Node add(E e, Node node) {
    if (node == null) {
        size++;
        return new Node(e);
    }
    if (e.compareTo((E) node.e) < 0) {
        node.left = add(e, node.left);
    } else if (e.compareTo((E) node.e) > 0) {
        node.right = add(e, node.right);
    }
    return node;
}

而向 AVL 树中添加元素就不是这么简单了。

对于向 AVL 树中添加一个节点，我们除了要保证二分搜索树的特性（二分搜索树的每个节点的值都要大于其左子树的所有节点的值，且小于其右子树的所有节点的值）外，还要保证维持平衡二叉树的特性。

我们思考一下，如果当前的 AVL 树是平衡的，那么哪些情况会使得 AVL 树变得不平衡呢？其实无非就是以下这四种：

第一种情况：插入的元素在不平衡节点的左子树的左侧

13、AVL 树 - 图4

我们向当前的 AVL 树中插入元素“4”，导致节点“12”的平衡因子变为了 2，出现了不平衡。

这种情况发生的条件为当前节点（“12”）的平衡因子大于 1，且当前节点的左子树的平衡因子大于等于 0，表达式表示为：

getBalanceFactor(node) > 1 && getBalanceFactor(node.left) >= 0

第二种情况：插入的元素在不平衡节点的右子树的右侧

13、AVL 树 - 图5

我们向当前的 AVL 树中插入元素“18”，导致节点“12”的平衡因子变为了 -2，出现了不平衡。

这种情况发生的条件为当前节点（“12”）的平衡因子小于 -1，且当前节点的右子树的平衡因子小于等于 0，表达式表示为：

getBalanceFactor(node) < -1 && getBalanceFactor(node.right) <= 0

第三种情况：插入的元素在不平衡节点的左子树的右侧

13、AVL 树 - 图6

我们向当前的 AVL 树中插入元素“10”，导致节点“12”的平衡因子变为了 2，出现了不平衡。

这种情况发生的条件为当前节点（“12”）的平衡因子大于 1，且当前节点的左子树的平衡因子小于 0，表达式表示为：

getBalanceFactor(node) > 1 && getBalanceFactor(node.left) < 0

第四种情况：插入的元素在不平衡节点的右子树的左侧

13、AVL 树 - 图7

我们向当前的 AVL 树中插入元素“14”，导致节点“12”的平衡因子变为了 -2，出现了不平衡。

这种情况发生的条件为当前节点（“12”）的平衡因子小于 -1，且当前节点的右子树的平衡因子大于 0，表达式表示为：

getBalanceFactor(node) < -1 && getBalanceFactor(node.right) > 0

左旋与右旋

我们已经知道，向 AVL 树中添加元素时，以上的四种情况会导致出现不平衡，那么如何让当前的树的结构变得平衡呢？

对于第一种情况，我们需要用到右旋的操作：

13、AVL 树 - 图8

右旋操作如上图所示。所谓的右旋指的是，将不平衡的节点 “y” 顺时针旋转，使得上图中左侧的结构变为右侧的结构，此时，右侧的这棵树既满足二分搜索树的特性，也满足平衡二叉树的特性。

证明如下：

左侧的结构是一棵二分搜索树，满足： $13、AVL 树 - 图9$ ，变为右侧的结构之后，仍然有： $13、AVL 树 - 图10$ ，所以右侧的结构也是一棵二分搜索树。

设 $13、AVL 树 - 图11$ 与 $13、AVL 树 - 图12$ 中，最大高度为 $13、AVL 树 - 图13$ ，所以节点 $13、AVL 树 - 图14$ 的高度为 $13、AVL 树 - 图15$ ；节点 $13、AVL 树 - 图16$ 也是平衡的，其平衡因子大于等于 0 且小于等于 1；所以， $13、AVL 树 - 图17$ 的高度不是 $13、AVL 树 - 图18$ 就是 $13、AVL 树 - 图19$ ， $13、AVL 树 - 图20$ 的高度表示为 $13、AVL 树 - 图21$ ； $13、AVL 树 - 图22$ 节点是不平衡的，它的平衡因子一定是 2，所以， $13、AVL 树 - 图23$ 的高度为 $13、AVL 树 - 图24$ 。

13、AVL 树 - 图25

那么，左侧的结构通过右旋操作变为了右侧的结构之后， $13、AVL 树 - 图26$ 的高度为 $13、AVL 树 - 图27$ ， $13、AVL 树 - 图28$ 的高度为 $13、AVL 树 - 图29$ ， $13、AVL 树 - 图30$ 的左右子树的高度差为 1，所以可证明，通过右旋，使得右侧的结构不仅是一棵二分搜索树，也是一棵平衡二叉树。

右旋操作的 Java 代码如下：

/**
 * 右旋:
 *
 *            y                           x
 *          /  \                       /     \
 *        x     T4                    z        y
 *      /  \         ========>     /  \      /  \
 *    z     T3                   T1   T2   T3   T4
 *  /  \
 * T1  T2
 */
private Node rightRotate(Node y){
    Node x = y.left;
    Node T3 = x.right;
    x.right = y;
    y.left = T3;
    // 更新 height
    y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
    return x;
}

类似地，对于第二种情况，我们需要用到左旋的操作：

13、AVL 树 - 图31

左旋操作如上图所示。所谓的左旋指的是，将不平衡的节点 “y” 逆时针旋转，使得上图中左侧的结构变为右侧的结构，此时，右侧的这棵树既满足二分搜索树的特性，也满足平衡二叉树的特性。

左旋的正确性证明和右旋是一样的，我就不再赘述了。

左旋的 Java 代码如下：

/**
 * 左旋:
 *
 *            y                           x
 *          /  \                       /     \
 *        T4    x                    y         z
 *             /  \    ========>   /  \      /  \
 *            T3   z             T4   T3   T1   T2
 *               /  \
 *              T1  T2
 */
private Node leftRotate(Node y){
    Node x = y.right;
    Node T3 = x.left;
    x.left = y;
    y.right = T3;
    // 更新 height
    y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
    return x;
}

对于第三种情况，我们需要将不平衡节点 node 的左孩子先进行一次左旋，然后再对不平衡节点 node 进行右旋，这样就使得整棵树的结构既满足二分搜索树的特性，也满足平衡二叉树的特性了：

13、AVL 树 - 图32

同理，对于第四种情况，我们需要将不平衡节点 node 的右孩子先进行一次右旋，然后再对不平衡节点 node 进行左旋，示意图如下：
13、AVL 树 - 图33

向 AVL 树中添加元素的完整代码

通过上文的分析，我们已经知道了向 AVL 树中添加元素时，哪些情况会出现使得 AVL 树出现不平衡，以及这些不平衡的情况该如何解决。

向 AVL 树中添加元素的 Java 代码如下：

/**
 * @param e 向 AVL 中添加新的元素
 */
 public void add(E e) {
    root = add(e, root);
 }
/**
 * @param e    向 AVL 中新插入的节点
 * @param node 当前比较的节点
 * @return 返回 AVL 的根节点
 */
private Node add(E e, Node node) {
    if (node == null) {
        size++;
        return new Node(e);
    }
    if (e.compareTo((E) node.e) < 0) {
        node.left = add(e, node.left);
    } else if (e.compareTo((E) node.e) > 0) {
        node.right = add(e, node.right);
    }
    // 更新 height
    node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
    // 计算平衡因子
    int balanceFactor = getBalanceFactor(node);
    // 平衡的维护
    // LL
    if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
        return rightRotate(node);
    // RR
    if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
        return leftRotate(node);
    // LR
    if(balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    // RL
    if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}

3. 向 AVL 树中删除元素

除了向 AVL 树中添加元素会导致树的结构发生变化以外，删除元素也会使得 AVL 树的结构发生变化，只要是树的结构发生变化，就有可能出现不平衡的节点，所以在二分搜索树中删除节点的代码的基础上，我们也要做可以实现自平衡性的修改。

我们先来回顾一下，向二分搜索树中删除节点的操作：

在二分搜索树中删除元素分为以下几种情况：

第一种情况为，我们删除的节点只有左子树没有右子树。

13、AVL 树 - 图34

那么我们只需要让删除的节点的左孩子取代删除节点的位置即可。

第二种情况为，我们删除的节点只有右子树没有左子树。

13、AVL 树 - 图35

我们只需要让删除节点的右孩子取代删除节点的位置即可。

第三种情况为，我们删除的节点既有左子树也有右子树。

对于这种情况，我们使用 Hibbard Deletion 算法。如果我们要删除一个既有左子树也有右子树的节点，首先需要找到待删除节点的后继节点（successor）。

对于二分搜索树而言，待删除节点的后继节点就是该节点右子树“最左的”那个节点，将后继节点替换待删除的节点就完成了删除操作。

13、AVL 树 - 图36

13、AVL 树 - 图37

在二分搜索树中删除一个元素的完整 Java 代码如下：

public void remove(E e) {
    root = remove(e, root);
}
private Node remove(E e, Node node) {
    if (node == null) {
        return null;
    }
    if (e.compareTo((E) node.e) < 0) {
        node.left = remove(e, node.left);
        return node;
    } else if (e.compareTo((E) node.e) > 0) {
        node.right = remove(e, node.right);
        return node;
    } else {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        // Hibbard Deletion
        Node successor = minimum(node.right);
        Node right = removeMin(node.right);
        Node left = node.left;
        successor.left = left;
        successor.right = right;
        node.left = null;
        node.right = null;
        return successor;
    }
}

对于 AVL 树的删除节点的方法，我们只需要在二分搜索树中删除节点的方法之上，加入维护自平衡的部分即可。这个部分实际上和向 AVL 树中添加元素维护自平衡的原理是一样的。

向 AVL 树中删除节点的 Java 代码如下：

public void remove(E e) {
    root = remove(e, root);
}
private Node remove(E e, Node node) {
    if (node == null)
        return null;
    Node retNode;
    if (e.compareTo((E) node.e) < 0) {
        node.left = remove(e, node.left);
        retNode = node;
    } else if (e.compareTo((E) node.e) > 0) {
        node.right = remove(e, node.right);
        retNode = node;
    } else {
        // 待删除节点的左子树为空
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            retNode = rightNode;
        }
        // 待删除的节点右子树为空时
        else if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            retNode = leftNode;
        }
        // 待删除的节点左右子树均不为空
        else {// Hibbard Deletion
            Node successor = minimum(node.right);
            Node right = remove((E) node.right, successor);
            Node left = node.left;
            successor.left = left;
            successor.right = right;
            node.left = null;
            node.right = null;
            retNode = successor;
        }
    }
    if(retNode == null)
        return null;
    // 更新 height
    retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
    // 计算平衡因子
    int balanceFactor = getBalanceFactor(retNode);
    // 平衡的维护
    // LL
    if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
        return rightRotate(retNode);
    // RR
    if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
        return leftRotate(retNode);
    // LR
    if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
        retNode.left = leftRotate(retNode.left);
        return rightRotate(retNode);
    }
    // RL
    if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
        retNode.right = rightRotate(retNode.right);
        return leftRotate(retNode);
    }
    return retNode;
}

三：AVL 树与二分搜索树的性能测试

在完成 AVL 树的性能测试前，我们需要两个验证方法，第一个是验证当前的 AVL 树满足二分搜索树的特性，第二个是验证当前的 AVL 树是一棵平衡二叉树。

这两个方法的实现也非常简单：

/**
 * 验证当前的 AVL 树是否满足二分搜索树的特性
 *
 * @return
 */
public boolean isBST() {
    ArrayList<E> list = new ArrayList<>();
    inOrder(root, list);
    for (int i = 1; i < list.size(); i++)
        if (list.get(i - 1).compareTo(list.get(i)) > 0)
            return false;
    return true;
}
/**
 * @param node 中序遍历以 node 为 根的 AVL
 */
private void inOrder(Node node, List<E> list) {
    if (node == null) {
        return;
    }
    inOrder(node.left, list);
    list.add((E) node.e);
    inOrder(node.right, list);
}
/**
 * 验证当前的二叉树是否是一棵平衡的二叉树
 *
 * @return
 */
public boolean isBalanced() {
    return isBalanced(root);
}
/**
 * 验证当前的二叉树是否是一棵平衡的二叉树
 *
 * @param node
 * @return
 */
private boolean isBalanced(Node node) {
    if (node == null)
        return true;
    int balanceFactor = getBalanceFactor(node);
    if (Math.abs(balanceFactor) > 1)
        return false;
    return isBalanced(node.left) && isBalanced(node.right);
}

我们的性能测试代码如下：

class AVLTreeTest {
    @Test
    void AVLAndBSTPerformanceTest() {
        int[] testArr = new int[20000];
        for (int i = 0; i < testArr.length; i++)
            testArr[i] = i;
        testBst(testArr);
        testAvl(testArr);
    }
    @Test
    void AVLTest(){
        AVLTree<Integer> avl = new AVLTree<>();
        for (int i = 0; i < 1000; i++){
            avl.add(i);
            if(!avl.isBalanced() || !avl.isBST())
                throw new RuntimeException("error!");
        }
        for(int i = 0; i < 1000; i++){
            avl.remove(i);
            if(!avl.isBalanced() || !avl.isBST())
                throw new RuntimeException("error!");
        }
        System.out.println("correct!");
    }
    private void testBst(int[] testArr) {
        BST<Integer> bst = new BST<>();
        long start = System.nanoTime();
        for (int i = 0; i < testArr.length; i++)
            bst.add(i);
        for (int i = 0; i < testArr.length; i++)
            if (!bst.contains(i)) throw new RuntimeException("error");
        long end = System.nanoTime();
        System.out.println("BST : " + (end - start) / 1000000000.0 + " s");
    }
    private void testAvl(int[] testArr) {
        AVLTree<Integer> avl = new AVLTree<>();
        long start = System.nanoTime();
        for (int i = 0; i < testArr.length; i++)
            avl.add(i);
        for (int i = 0; i < testArr.length; i++)
            if (!avl.contains(i)) throw new RuntimeException("error");
        long end = System.nanoTime();
        System.out.println("AVL : " + (end - start) / 1000000000.0 + " s");
    }
}

我们的性能测试非常简单，首先初始化一个容量为 20000 的单调递增的数组，然后将数组所有的元素依次添加到二分搜索树与 AVL 树这两种数据结构中，并在所有元素添加完毕后，依次执行查询操作。

由于数组是单调递增的，我们的二分搜索树会退化为一个链表，添加和查询元素的时间复杂度均为 $13、AVL 树 - 图38$ #card=math&code=O%28N%5E2%29&id=nu5us)；而 AVL 树则因为其自平衡的特性使得添加和查找元素的复杂度为 $13、AVL 树 - 图39$ #card=math&code=O%28logN%29&id=gwfZR)。

在我的计算机上，AVLAndBSTPerformanceTest 这个单元测试的执行结果为：

BST : 1.935773389 s
AVL : 0.018965793 s

我们可以看到，二者的差异是巨大的。

四：总结

在这一篇文章中，我介绍了 AVL 树这种数据结构以及 AVL 树是如何通过左旋和右旋来实现自平衡的。并且，我们通过一个小的测试来验证在数据极端的情况下，AVL 树和二分搜索树的性能差异。

AVL 树是计算机科学中，最早被发明的自平衡二叉查找树，除了 AVL 外，还有很多优秀的平衡二叉查找树这种数据结构，期待在后面的文章中，我可以与你一同研究与学习。

本文中使用的代码均在：

https://github.com/jinrunheng/datastructure-and-algorithm/

好啦，至此为止，这一篇文章我就介绍完毕了～欢迎大家关注我的公众号【kim_talk】，在这里希望你可以收获更多的知识，我们下一期再见！

13、AVL 树 - 图40