数据结构进阶(一):AVL树

这篇具有很好参考价值的文章主要介绍了数据结构进阶(一):AVL树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

所谓的AVL树也叫做高度平衡的二叉搜索树。

啥是高度平衡的二叉搜索树?

高度平衡的二叉搜索树:意味着左右子树的高度最大不超过一

我们先来回顾一下二叉搜索树的概念:

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

它或许是个完全二叉树:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

在极端情况下又是个单分支的树:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

一个二叉搜索树的时间复杂度为:O(N), 极端情况下,例如上图(左右单支)的情况,树的高度很高,那么就会导致搜索的效率很低,如果此时有N个树,树的高度就为N。

所以我们需要一颗更高效的树,这就是高度平衡的二叉搜索树,这也就是为什么需要高度平衡的原因。

AVL树的概念

二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。

一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如图:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

 每个结点旁的数字代表着其平衡高度,左子树存在一个为 -1,右子树存在一个即为1,不存在则为0。

其中,3 结点上,左子树的高度为2,所以左子树的平衡因子应该为 -2,右子树的高度为1,所以右子树的平衡因子为1,二者相结合的平衡因子应该为:-1。

如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在              O( logN),搜索时间复杂度O( logN)。

实现AVL树的相关代码

AVL树节点的定义

AVL树结点的定义其实很简单:

static class TreeNode {
    public TreeNode left; // 节点的左孩子
    public TreeNode right; // 节点的右孩子
    public TreeNode parent ; // 节点的双亲
    public int val = 0;
    public int bf = 0; // 当前节点的平衡因子=右子树高度-左子树的高度
    public TreeNode(int val) {
        this.val = val;
    }
}

注意:
当前节点的平衡因子=右子树高度-左子树的高度。但是,不是每棵树,都必须有平衡因子,这只是其中的一种实现方式。

AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步:

  1. 按照二叉搜索树的方式插入新结点
  2. 调节结点的平衡因子

这里我们画图一步步来讲解。

我们先来随便画棵树:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

现在我们有这样一棵AVL树,我们给它插入一个 5 的结点。

还是和二叉搜索树一样去寻找,从根节点开始,大于根结点的值向右走,小于根节点的向左走,以此类推。

数据结构进阶(一):AVL树,数据结构高阶,数据结构

此时,我们需要重新调节平衡因子:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

此时就需要对整棵树进行一个旋转。

树的旋转

右单旋

 既然它不平衡,那就需要想办法让他平衡。

数据结构进阶(一):AVL树,数据结构高阶,数据结构

  这里只是其中一种旋转,我们再来看看其他情况:

左单旋

我们现在有这样一棵树:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

 我们新插入一个50:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

此时,25 的结点就不平衡了,我们也需要旋转:

旋转过后:

数据结构进阶(一):AVL树,数据结构高阶,数据结构 由上述的两种旋转我们看到一个细节:

 数据结构进阶(一):AVL树,数据结构高阶,数据结构

数据结构进阶(一):AVL树,数据结构高阶,数据结构  

  • 不平衡时,该不平衡的结点和其子节点的平衡因子必然同号,此时我们只需要单旋即可。
  • 并且,平衡因子为负数需要发送右旋,平衡因子为正数需要发生左旋
  • 如若,异号则需要发生双旋

左右双旋

我们还是以发生右单旋的图为基础,我们现在不插入5,而是插入 28 ;

如图:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

 我们可以看出来:30 这个节点上的平衡因子和 20 这个节点上的平衡因子异号了。

无论是左单旋还是右单旋都无济于事。不信可以自己去画画图;

最终结果如图所示:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

 右左双旋

 我们在左单旋的基础上,插入一个值为 26 的结点,如下图:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

同样的,无法用单旋来解决问题。

我们需要先右单旋在左单旋;如下图:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

ok,上面只是介绍了单旋是怎么旋转的,接下来要开始讲解代码了。

代码实现

插入方法代码

首先,我们要将这个方法设置为布尔值类型,因为这个方法是有可能无法执行的。

AVL树是基于二叉搜索树衍生的,二叉搜索树中是无法实现插入相同的值。

所以这里的插入方法可以参考参考二叉搜索树。

第一步,需要判断根节点是否为空,为空那么这个需要插入的 val 就直接为根结点就行了。

数据结构进阶(一):AVL树,数据结构高阶,数据结构

第二步,开始遍历,设置 一个 cur ,一个 parent ,两个TreeNode ,去找目标 val 应该要插入的位置。

数据结构进阶(一):AVL树,数据结构高阶,数据结构

ok,目前为止与二叉搜索树没有太大差别,我们到这里已经找到了目标 val 应该插入的为止,还需要解决 平衡因子和转换后各个结点的关系。

此时的 node 已经是叶子节点了

数据结构进阶(一):AVL树,数据结构高阶,数据结构

数据结构进阶(一):AVL树,数据结构高阶,数据结构为啥这里的循环条件是parent != null,我们来看张旋转图:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

我们图中,30 是个根节点吗?

它也可以是某个结点的子节点(故此,我们还需要向上平衡);直到调节到根结点才算调整完毕。 

数据结构进阶(一):AVL树,数据结构高阶,数据结构

 数据结构进阶(一):AVL树,数据结构高阶,数据结构

两两对比,就能总结出规律了。 

public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        // 根节点为空
        if (root == null) {
            root = node;
            return true;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val < val){
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        // cur == null
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }

        // 当前只是解决了 left 和 right ,还没有处理 node 的 parent
        node.parent = parent;
        cur = node;

        // 调节平衡因子
        while (parent != null) {
            // 先看 cur 是 parent 的左还是右;此时决定了平衡因子是 ++ 还是 --
            if (cur == parent.right) {
                parent.bf++;
            } else{
                parent.bf--;
            }
            //检查当前平衡因子是否绝对值 <= 1
            if (parent.bf == 0) {
                // 记住一个结论: cur 的 parent 的平衡因子为 0 ,
                // 那么它插入一个结点一定平衡,此时无论插入右子树还是右子树都无所谓,就不用往上继续调节

                // 此时已经平衡了
                break;
            } else if (parent.bf == 1 || parent.bf == -1) {
                // 此时插入一个结点,其父节点未必平衡,需要继续向上调节
                cur = parent;
                parent = parent.parent;
            } else {
                if (parent.bf == 2) {
                    // 此时说明右树高,需要先左旋,再右旋
                    if (cur.bf == 1) {
                        rotateLeft(parent);
                    } else {
                        // cur.bf == -1
                        rotateRL(parent);
                    }
                } else {
                    // cur.bf == -2 ;左树高,需要降低左树的高度
                    // 同样也分平衡因子为 1 和 -1 两种情况
                    if (cur.bf == -1) {
                        // 右旋
                        rotateRight(parent);
                    } else {
                        // cur.bf == 1
                        rotateLR(parent);
                    }
                }
                break;
            }
        }
        return true;
    }

右单旋

还是需要借助上述的案例来进行讲解:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

/**
     * 右单旋
     * @param parent
     */
    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;

        // 旋转关系 (需要画图)
        parent.right = subRL;
        subR.left = parent;
        if (subRL != null) { // subRL 可能为空
            subRL.parent = parent;
        }
        // 与左单旋一样,需要判断parent 所在的位置是根节点还是某个子树
        TreeNode pParent = parent.parent;
        parent.parent = subR;

        // 为根节点的情况
        if (root == parent) {
            root = subR;
            root.parent = null;
        } else {
            // 不为根节点的情况
            if (pParent.left == parent) {
                pParent.left = subR;
            } else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        // 调节平衡因子
        subR.bf = parent.bf = 0;
    }

这里的parent 是需要插入的叶子结点的父节点。

我们首先需要保存一下需要调整位置的几个结点:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

第一步:先断开parent 和 subR 之间的关系,建立subRL 和 parent 之间的关系:

数据结构进阶(一):AVL树,数据结构高阶,数据结构 

第二步:断开subR 和 subRL 之间的关系,建立subR 和 parent 之间的关系:

数据结构进阶(一):AVL树,数据结构高阶,数据结构 

当然啦,subRL并非一定存在,它也可以不存在啊,不存在的情况需要特殊处理一下:

数据结构进阶(一):AVL树,数据结构高阶,数据结构 

当然,我们目前只确定了彼此之间的left 和 right ,别忘了我们TreeNode 还定义了 parent,所以目前我们还需要处理一下父节点的问题。

数据结构进阶(一):AVL树,数据结构高阶,数据结构

数据结构进阶(一):AVL树,数据结构高阶,数据结构 

如上图,我们需要确定parent 这个结点的位置是否为 根节点,如果是根结点那么 subR 的父节点就是null,如果不是则需要确定具体是 pParent 哪边:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

ok,这里就是右单旋的代码,接下来看看左单旋;

左单旋

具体代码:

    /**
     * 左单旋
     * @param parent
     */
    private void rotateRight(TreeNode parent) {
        // 处理旋转之后几个节点的关系
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        parent.left = subLR;
        subL.right = parent;
        // subLR 是可能为空的,为空还进行就会报错!
        if (subLR != null) {
            subLR.parent = parent;
        }
        // 必须先记录父节点的父节点(这一段画图理解)
        TreeNode pParent = parent.parent;

        parent.parent = subL;
        // 判断 parent 是否为 根节点
        if(parent == root) {
            root = subL;
            root.parent = null;
        } else {
            // 不是根结点,就判断这棵树是左子树还是右子树
            if (pParent.left == parent) {
                pParent.left = subL;
            } else {
                pParent.right = subL;
            }
        }
        // 全部调整完毕,还需要调节 平衡因子
        subL.bf = 0;
        parent.bf = 0;
    }

同样的,我们得先保存几个需要调整位置的结点,如下图:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

  我们先调整 几个结点之间的left 和 right 的关系;

第一步,断开parent 和 subL 之间的关系,连接 parent 和 subLR 的关系:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

 第二步:断开subL 和 subLR 的关系,连接 subL 和 parent 的关系:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

同样的,subLR并非一定存在,它也可以不存在啊,不存在的情况需要特殊处理一下:

 数据结构进阶(一):AVL树,数据结构高阶,数据结构

 数据结构进阶(一):AVL树,数据结构高阶,数据结构

接下来的操作都一样:

数据结构进阶(一):AVL树,数据结构高阶,数据结构 

 数据结构进阶(一):AVL树,数据结构高阶,数据结构

右左双旋

确实双旋比单旋难不了多少,双旋是建立在单旋的基础上的,只需要单旋两次即可。

先看示意图:

数据结构进阶(一):AVL树,数据结构高阶,数据结构 

    /**
     * 右左双旋
     * @param parent
     */
    private void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf;
        rotateLeft(parent.left);
        rotateRight(parent);

        if (bf == -1) {
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        } else {
            // bf == 1
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
    }

数据结构进阶(一):AVL树,数据结构高阶,数据结构

 我们来看看这两种情况:

数据结构进阶(一):AVL树,数据结构高阶,数据结构

于是就变成了这样:

数据结构进阶(一):AVL树,数据结构高阶,数据结构 

此时的subLR 的平衡因子就是 -1 了,所以需要保留一下sunLR的平衡因子;

旋转还是一样的旋转,只是旋转以后需要改变不同的平衡因子:

数据结构进阶(一):AVL树,数据结构高阶,数据结构 

同样的, 左右双旋也是同理。

这里就不单独介绍左右双旋,可以自己画个图,然后参考上面右左双旋的做法。

此外还有一个删除没有了解,过后我在此处补齐。

完整代码:

AVLTree/src/AVLTree.java · wjm的码云/Projects - 码云 - 开源中国 (gitee.com)文章来源地址https://www.toymoban.com/news/detail-529145.html

到了这里,关于数据结构进阶(一):AVL树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之进阶二叉树(二叉搜索树和AVL树、红黑树的实现)超详细解析,附实操图和搜索二叉树的实现过程图

    绪论​ “生命有如铁砧,愈被敲打,愈能发出火花。——伽利略”;本章主要是数据结构 二叉树的进阶知识,若之前没学过二叉树建议看看这篇文章一篇掌握二叉树,本章的知识从浅到深的 对搜索二叉树的使用进行了介绍和对其底层逻辑的实现进行了讲解 ,希望能对你有所

    2024年02月04日
    浏览(46)
  • [数据结构]-AVL树

    前言 作者:小蜗牛向前冲 名言:我可以接受失败,但我不能接受放弃   如果觉的博主的文章还不错的话,还请 点赞,收藏,关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录 一、AVL树基本知识 1、概念 2、节点定义 3、插入 二、AVL树的旋转 1、右单旋

    2024年02月04日
    浏览(32)
  • 【数据结构】AVL 树

    前面对 map / multimap / set / multiset 进行了简单的介绍【C++】map set,在其文档介绍中发现,这几个容器有个共同点是: 其底层都是按照二叉搜索树来实现的 ,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度

    2024年04月12日
    浏览(31)
  • 【数据结构】AVL树

    🐱作者:一只大喵咪1201 🐱专栏:《数据结构与算法》 🔥格言: 你只管努力,剩下的交给时间! 我们知道,二叉搜索树的搜索效率非常高,平均时间复杂度是O(log 2 N),但是当数据原本就有序时,插入二叉树中就会形成单支结构,此时搜索的时间复杂度就是O(N)。 为了避免

    2023年04月18日
    浏览(32)
  • 【数据结构】AVL树/红黑树

    目录 1.AVL树(高度平衡二叉搜索树) 10.1.基本概念 10.2.实现 10.2.1.AVL树节点的定义 10.2.2.AVL树的插入 10.2.3.AVL树的旋转 1.新节点插入较高左子树的左侧---左左:右单旋 2.新节点插入较高右子树的右侧---右右:左单旋 3.新节点插入较高左子树的右侧---左右:先左单旋再右单旋(左

    2024年02月15日
    浏览(46)
  • C++&&数据结构——AVL树

    根据前面对二叉搜索树的学习我们可以了解到二叉搜索树可以提高查找的效率,但是如果数据本身有序,搜索树将退化成单支树,查找时相当于顺序表查找,效率低下,如下图: 为了解决上面的问题,来自俄罗斯的两位天才数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种方

    2024年01月19日
    浏览(65)
  • 数据结构:AVL树讲解(C++)

    普通二叉搜索树: 二叉搜索树 二叉搜索树虽可以缩短查找的效率,但如果 数据有序或接近有序普通的二叉搜索树将退化为单支树 ,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法

    2024年02月04日
    浏览(40)
  • 【1++的数据结构】之AVL树

    👍作者主页:进击的1++ 🤩 专栏链接:【1++的数据结构】 在说AVL树之前我们先来说说为什么会出现AVL树。在前面的文章中我们讲过二叉搜索树,虽然查找,插入效率比较高,但其有个缺陷:在某些情况下其可能会成为一颗单支树或其他高度较高的树,这时我们的效率就比较

    2024年02月11日
    浏览(34)
  • 【数据结构】—AVL树(C++实现)

                                                            🎬慕斯主页 : 修仙—别有洞天                                                  💜 本文前置知识:  搜索二叉树                                                       ♈️ 今日夜电波

    2024年02月05日
    浏览(49)
  • 数据结构与算法——18.avl树

    这篇文章我们来看一下avl树 目录 1.概述 2.AVL树的实现 我们前面讲了二叉搜索树,它是有一个key值,然后比父节点key值大的在左边,小的在右边。这样设计是为了便于查找。但是有一种极端的情况,就是所有的结点都在一边,那查找的时间复杂度和在链表的查找时间复杂度就

    2024年02月07日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包