首页 / 算法 / 算法与数据结构系列之[平衡二叉树-AVL树-上]

算法与数据结构系列之[平衡二叉树-AVL树-上]

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法与数据结构系列之[平衡二叉树-AVL树-上]，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6436字，纯文字阅读大概需要10分钟。

内容图文

1.问题概述

我们在介绍二分搜索树的时候提到时间复杂度为O(logn),但是这并不是绝对的，有些时候树可能退化为链表，时间复杂度回到O(n)级别，所以为了性能考虑，应尽量避免这种退化，这就用到了平衡树。

算法与数据结构系列之[平衡二叉树-AVL树-上] - 文章图片
2.什么是平衡二叉树

平衡二叉树的定义是，对于任意一个节点，左子树和右子树的高度差不能超过1，且平衡二叉树的高度和节点的数量之间的关系一是O(logn)的。我们前面介绍的满二叉树、完全二叉树和线段树都是平衡二叉树，如下图中的这棵二叉树看似不太像平衡二叉树，但它满足平衡二叉树的定义，根节点的左子树的高度3，有子树的高度2，高度差为1；8的左子树的高度为2，右子树的高度为1，高度差为1；5的左子树的高度为1，右子树高度为0，高度差为1；18的左子树高度为1，右子树高度为0，高度差为1；4,11,17都是叶子节点，其没有左子树和右子树，高度差为0，所以这棵树是一棵平衡二叉树。

算法与数据结构系列之[平衡二叉树-AVL树-上] - 文章图片
给上图这棵平衡二叉树插入两个元素2和7，则得到下图这棵二叉树(这里的二叉树是二叉排序树)，根据平衡二叉树的定义，显然得到的这棵二叉树不是平衡二叉树，因为8这个节点的左子树高度为3，右子树高度为1，高度差为2，超过了1，同理根节点12的左右子树高度差也是2，所以它不是一棵平衡二叉树。

算法与数据结构系列之[平衡二叉树-AVL树-上] - 文章图片
如果要想让一棵平衡二叉树添加节点后依然一棵平衡二叉树，那么不能只在左边添加，右边也需要添加相应的节点来维持整棵树的平衡关系。

那么如何判断一棵二叉树是否是平衡二叉树呢？就是比较左右子树的高度差是否大于1，大于1就不是平衡二叉树。这里涉及到一个概念叫做平衡因子，平衡因子其实就是左右子树的高度差。通过计算平衡因子就可以判断一棵树是否是平衡二叉树。

3.什么是AVL树

AVL树是自平衡的二分搜索树，是一种经典的平衡树的种类。要注意的是AVL树首先要是一棵二分搜索树，其次还得是一棵平衡树，也就是要求AVL树的任何节点的左右子树高度差的绝对值不超过1。

既然AVL是自平衡的，那么AVL树是如何来维持这种平衡的呢？答案是通过旋转，即左旋和右旋。在加入节点后，要沿着这个节点向上维护平衡性。

3.1、右旋转(LL)： 当插入的元素在不平衡节点的左侧的左侧时，进行右旋转，如图，将发生不平衡节点y的左子节点x的右子树变为以y为根的子树，再把 先前x的右子树T3连接到当前y的左子节点上，此时就变成了一棵以x为根节点的平衡二分搜索树。

算法与数据结构系列之[平衡二叉树-AVL树-上] - 文章图片
代码实现

private Node rightRotate(Node y){
    Node x = y.left;
    Node T3 = x.right;
    //向右旋转
    x.right = y;
    y.left = T3;
    //更新height值，旋转后只有x和y的高度值发生变化
    y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
    return x;
}

3.2、左旋转(RR)： 当插入的元素在不平衡节点的右侧的右侧时，进行左旋转，如图，将发生不平衡节点的右子节点x的左子树变为以y为根的子树，再把先前x的左子节点T3连接到当前y的右子节点上。此时变成了一棵以x根节点的二分搜索树。
算法与数据结构系列之[平衡二叉树-AVL树-上] - 文章图片
代码实现：

private Node leftRotate(Node y){
    Node x = y.right;
    Node T3 = x.left;
    //向左旋转
    x.left = y;
    y.right = T3;
    //更新height值，旋转后只有x和y的高度值发生变化
    y.height = Math.max(getHeight(y.left),getHeight(y.right)) + 1;
    x.height = Math.max(getHeight(x.left),getHeight(x.right)) + 1;
    return x;
}

3.3、LR: 当插入元素在不平衡节点的左侧的右侧时，需要先对x进行一次左旋转，再对y进行一次右旋转，如下图：
算法与数据结构系列之[平衡二叉树-AVL树-上] - 文章图片
代码实现：

private Node add(Node node, K key, V value){

    if(node == null){
        size ++;
        return new Node(key, value);
    }

    if(key.compareTo(node.key) < 0)
        node.left = add(node.left, key, value);
    else if(key.compareTo(node.key) > 0)
        node.right = add(node.right, key, value);
    else // key.compareTo(node.key) == 0
        node.value = value;
    //更新height
    node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
    //计算平衡因子
    int balanceFactor = getBalanceFactor(node);
    //平衡维护
    //LL
    if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
        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.4、RL：当插入元素在不平衡节点右侧的左侧时，需要先对x进行一次右旋转，再对y进行一次左旋转，如下图：

算法与数据结构系列之[平衡二叉树-AVL树-上] - 文章图片
代码实现：

private Node add(Node node, K key, V value){

    if(node == null){
        size ++;
        return new Node(key, value);
    }

    if(key.compareTo(node.key) < 0)
        node.left = add(node.left, key, value);
    else if(key.compareTo(node.key) > 0)
        node.right = add(node.right, key, value);
    else // key.compareTo(node.key) == 0
        node.value = value;
    //更新height
    node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));
    //计算平衡因子
    int balanceFactor = getBalanceFactor(node);
    //平衡维护
    //LL
    if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
        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;
}

上面我们介绍了添加元素时维护平衡性的方法和代码实现，其实在删除元素时也需要维护下平衡性，方法和添加类似。下面贴出删除元素的方法实现：

private Node remove(Node node, K key){

    if( node == null )
        return null;
    Node retNode; //要返回的node节点，
    if( key.compareTo(node.key) < 0 ){
        node.left = remove(node.left , key);
        retNode = node;
    }
    else if(key.compareTo(node.key) > 0 ){
        node.right = remove(node.right, key);
        retNode = node;
    }
    else{   // key.compareTo(node.key) == 0

        // 待删除节点左子树为空的情况
        if(node.left == null){
            Node rightNode = node.right;
            node.right = null;
            size --;
            retNode = node;
        }

        // 待删除节点右子树为空的情况
        else if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size --;
            retNode = node;
        }
        // 待删除节点左右子树均不为空的情况
        // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点
        // 用这个节点顶替待删除节点的位置
        else {
            Node successor = minimum(node.right);
            successor.right = remove(node.right, successor.key);
            successor.left = node.left;


            node.left = node.right = null;


            retNode = node;
        }
    }
    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)
        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;
}

4.总结：

这篇介绍了平衡树和AVL树的概述，在二分搜索树的基础上，重点实现了AVL树添加和删除元素后平衡性的维护，下篇将AVL树的实现代码贴出来。

内容总结

以上是互联网集市为您收集整理的算法与数据结构系列之[平衡二叉树-AVL树-上]全部内容，希望文章能够帮你解决算法与数据结构系列之[平衡二叉树-AVL树-上]所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/768784.html

来源：【匿名】