Loading...
墨滴

jrh

2021/09/14  阅读:41  主题:橙心

AVL 树

一:什么是 AVL 树?

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

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

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

Adelson-Velsky and Evgenii Landis
Adelson-Velsky and Evgenii Landis

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

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

接下来,我们就一起探究一下 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”的流程:

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 树变得不平衡呢?其实无非就是以下这四种:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

左旋与右旋

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

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

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

证明如下:

左侧的结构是一棵二分搜索树,满足: ,变为右侧的结构之后,仍然有: ,所以右侧的结构也是一棵二分搜索树。

中,最大高度为 ,所以节点 的高度为 ;节点 也是平衡的,其平衡因子大于等于 0 且小于等于 1;所以, 的高度不是 就是 的高度表示为 节点是不平衡的,它的平衡因子一定是 2,所以, 的高度为

那么,左侧的结构通过右旋操作变为了右侧的结构之后, 的高度为 的高度为 的左右子树的高度差为 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;
}

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

左旋操作如上图所示。所谓的左旋指的是,将不平衡的节点 “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 进行右旋,这样就使得整棵树的结构既满足二分搜索树的特性,也满足平衡二叉树的特性了:

同理,对于第四种情况,我们需要将不平衡节点 node 的右孩子先进行一次右旋,然后再对不平衡节点 node 进行左旋,示意图如下:

向 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 树的结构发生变化,只要是树的结构发生变化,就有可能出现不平衡的节点,所以在二分搜索树中删除节点的代码的基础上,我们也要做可以实现自平衡性的修改。

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

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

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

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

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

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

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

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

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

在二分搜索树中删除一个元素的完整 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 树这两种数据结构中,并在所有元素添加完毕后,依次执行查询操作。

由于数组是单调递增的,我们的二分搜索树会退化为一个链表,添加和查询元素的时间复杂度均为 ;而 AVL 树则因为其自平衡的特性使得添加和查找元素的复杂度为

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

BST : 1.935773389 s
AVL : 0.018965793 s

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

四:总结

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

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

本文中使用的代码均在:

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

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

jrh

2021/09/14  阅读:41  主题:橙心

作者介绍

jrh