目录开头一.AVL 树的核心概念二. AVL树的实现1AVL树的结构2AVL树的插入1.平衡因子2.插入节点以及更新平衡因子的代码实现3. 旋转a. 右单旋b. 左单旋c.左右单旋d.右左双旋4.完整代码3AVL的查找4AVL树平衡检测结尾往期回顾开头ok了正如标题所见今天我们这一期学习的是让很多同学都望而生畏的AVL树大家肯定是听过诸如“左旋”“右旋”“左右双旋” 这种的一些名词看上去挺唬人的今天就和同学们一起看图搞懂并实现 AVL树在学习 AVL树前防止有些同学之前没有了解过这里我们先来看看前置知识——二叉搜索树BST)二叉搜索树是一种特殊的二叉树它满足以下三个核心性质• 左子树所有节点的值 小于 根节点的值• 右子树所有节点的值 大于 根节点的值• 左右子树本身也都是二叉搜索树如上图一颗二叉搜索树任意子树都满足左子树的节点都要小于根节点右子树的节点都要大于根节点核心特性对 BST 进行中序遍历会得到一个严格递增的有序序列。满足这样的特性有上面作用呢答案是这样的结构非常利于我们进行查找从根节点开始比较• 如果目标值 当前节点值去左子树查找• 如果目标值 当前节点值去右子树查找• 如果相等查找成功• 如果走到空节点查找失败这样最好的情况下时间复杂度就是 O(logN)但是有一种特殊情况在这种情况下时间复杂度会退化到 O(N)为了解决这种问题就有了这一期要讲的 AVL树一.AVL 树的核心概念AVL 树是一棵高度平衡的二叉搜索树它在 BST 的基础上增加了一个平衡约束任意节点的左右子树的高度差的绝对值不超过 1我们用平衡因子Balance Factor,BF 来量化节点的平衡状态平衡因子 右子树高度 - 左子树高度因此AVL 树中所有节点的平衡因子只能是-1、0或1。如上图对于每一个节点它的左右子树的高度差都不会超过 1即每一个节点的平衡因子都只能是 -1 0 1如图对于 10 这个节点来说它的平衡因子 bf 2(右子树的高度) - 0 (左子树的高度 2就不满足AVL树的特性了这就需要我们下面要讲的旋转来处理这种不平衡问题二. AVL树的实现1AVL树的结构AVL 树的节点需要比普通 BST 多个成员平衡因子_bf记录当前节点的平衡状态2AVL树的插入AVL 树的插入分为三个核心步骤插⼊⼀个值按⼆叉搜索树规则进⾏插⼊新增结点以后只会影响祖先结点的⾼度也就是可能会影响部分祖先结点的平衡因⼦所以更新从新增结点-根结点路径上的平衡因⼦更新平衡因⼦过程中没有出现问题则插⼊结束更新平衡因⼦过程中出现不平衡对不平衡⼦树进行旋转处理1.平衡因子平衡因⼦ 右⼦树⾼度 - 左⼦树⾼度只有子树的高度发生变化才会影响当前节点的平衡因子对于插入一个节点会增加⾼度所以新增结点在parent的右⼦树parent的平衡因⼦新增结点在parent的左⼦树parent平衡因⼦–这时就会有三种情况父节点平衡因子变为0说明插入前父节点一边高一边低新节点插在了低的那边插入后父节点所在子树的高度不变不会影响更上层的祖先更新结束父节点平衡因子变为 1 或 - 1: 这种情况下父节点的平衡因子只能是 0- 1 或者 0- -1,说明更新前parent⼦树两边⼀样⾼新增的插⼊结点后parent所在的⼦树⼀边⾼⼀边低parent所在的⼦树符合平衡要求但是⾼度增加了1会影响parent的⽗亲结点的平衡因⼦所以要继续向上更新如上图更新到10结点平衡因⼦为210所在的⼦树已经不平衡需要旋转处理更新到中间结点3为根的⼦树⾼度不变不会影响上⼀层更新结束最坏更新到根停⽌父节点平衡因子变为 2 或 - 2这种情况下父节点的平衡因子只能是 1- 2 或者 -1- -2说明更新前parent⼦树⼀边⾼⼀边低新增的插⼊结点在⾼的那边parent所在的⼦树⾼的那边更⾼了破坏了平衡parent所在的⼦树不符合平衡要求需要旋转处理2.插入节点以及更新平衡因子的代码实现如上图要插入一个节点首先我们就是用二叉搜索树的性质来找到新节点要在的位置小于节点的到左边大于节点的到右边当 cur 走到空的时候就到了目标位置就判断新节点是要插入到 parent 的左边还是右边接下来就是要更新平衡因子了就按照上面的三点• 平衡因子为 bf 0更新结束• bf -1 || bf 1继续向上更新• bf 2 || bf -2 要进行旋转3. 旋转当某个节点的平衡因子变为 2 或 - 2 时说明该节点所在的子树已经不平衡需要通过旋转来调整结构恢复平衡旋转的两个核心原则保持二叉搜索树的性质左子树 根 右子树让旋转过后的树变平衡其次降低旋转树的⾼度AVL 树共有四种旋转方式对应四种不平衡情况接下来我们一个一个的画图讲解a. 右单旋如上图当子树 a 的高度因为插入了一个节点而增加 1 对于 a 来说这时父节点的 bf 变为 -1 祖父的 bf 变为 -2说明因为 subL 这个节点的左子树高度增加了 1 个导致了 subL 的左边高了一个parent 的左边也高了一个这时就要进行右旋这里很多同学肯定会有疑惑为什么 ab, c 这三颗子树一开始的高度 h 是一样的你画的这个图是不是特殊情况下的其实a, bc 这三颗子树的高度 h 一定是一样的 为什么首先对于 5 这个节点来说一开始的 bf 就一定是 0 a,b 子树高度一致如果不是 0 是 1右边高或者 -1 左边高这时候在 a 树中插入一个节点使得 a 的高度增加 1就会导致 5 这个节点要么 bf 变为 0右边高的情况这种情况下就不会向上更新要么就会变成 -2 左边高的情况这种情况下就会在以 5 这个为节点就会进行旋转处理就不会等到在这里处理对于 c 树如果高度变为 h-1 那么 10 这个节点的 bf -2就会进行旋转 如果 c 的高度变成 h1那么在 a 中插入一个节点10 最终 bf -1不会进行旋转更不用说 c 为其他值综上ab , c 的高度一定是一样的我们来看右旋的具体情况;a,b,c 的高度为 0这里完成了什么对于右旋来说实际上就是把 subL 的右节点指向 parent然后将 subL 的右节点指向 parent对于 subLR 节点为空的情况有点难理解下面我们来看别的情况a , b ,c 的高度为 1如上图右旋先将 b 指向 10 再将 5 的右指针指向 10 这样就变平衡了接下来我们来看看代码实现b. 左单旋如上图当子树 a 的高度因为插入了一个节点而增加 1 对于 a 来说这时父节点的 bf 变为 1 祖父的 bf 变为 2说明因为 subR 这个节点的右子树高度增加了 1 个导致了 subR 的右边高了一个parent 的右边也高了一个这时就要进行左旋这里类比于右单旋左单旋就是将 subR 的左子树指向 parent 然后将 subR 的左子树指向 parent我们直接上代码c.左右单旋如上图由于 5 节点的右子树增加了 1 所以 bf -1 ,而 parent 由于左子树增加 1 bf -2这时候进行左右双旋对于 b 子树来说分为三种情况:1.插在 b 中的左子树中如上图先对 subL 进行左旋然后再对 parent 进行右旋2.插在 b 中的右子树中如上图先对 subL 进行左旋然后再对 parent 进行右旋b 树的两个子树为空这个我就不写具体的过程了大家可以自己推导下这三种情况都是要进行左右双旋区别在于最后如何更新平衡因子代码实现;d.右左双旋如上图由于 15 节点的左子树增加了 1 所以 bf -1 ,而 parent 由于右子树增加 1 bf 2这时候进行右左双旋对于b树依旧可以分为3种情况1.插在 b 中的左子树中先对 subR 进行右旋然后对parent进行左旋2.插在 b 中的右子树中3. b 树的两个子树为空代码实现4.完整代码3AVL的查找查找就很简单了直接展示代码4AVL树平衡检测对于AVL树是否平衡的判断主要是通过判断每一个节点右左子树的高度差平衡因子这里使用了一个小技巧因为 _root 是私有成员变量在类外访问不到但是想要调用判断是否平衡的这个函数又必须要 _root 这个参数为了解决这个矛盾就可以这样写结尾这一期对AVL树的学习就结束了大家下来一定要自己画图通过图来想想代码如何写。如果本文对你有帮助欢迎点赞、收藏、关注如果有任何问题也欢迎在评论区留言交流。我会持续更新更多的C技术文章敬请期待我主页里有更好康的呦往期回顾一文彻底搞懂Linux权限知识C模板教你白嫖6个月的阿里云服务器 Linux 常用指令学习