《C++》【AVL树】

1. 什么是AVL树AVL树是一种自平衡二叉搜索树由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年提出其名称来源于这两位发明者的名字缩写。AVL树是最早发明的自平衡二叉搜索树AVL树是在普通二叉搜索树的基础上增加了平衡条件确保树始终保持近似平衡状态AVL树要么是空树要么是满足以下性质的二叉搜索树其左、右子树也都是 AVL 树并且左、右子树的高度差的绝对值不超过 12. AVL树的基本性质怎么样核心特点高度近似平衡AVL 树通过不断调整树的结构保证树的左右子树高度差始终在允许范围内使得树的高度相对较低。例如在插入或删除节点后会通过旋转操作左旋、右旋、左右双旋、右左双旋来重新平衡树从而维持高度平衡。查找效率稳定由于 AVL 树高度平衡其高度近似于其中是节点数量这意味着在 AVL 树中进行查找操作时时间复杂度稳定在相比于普通二叉搜索树在最坏情况下可能退化为链表查找时间复杂度为其查找效率更高且稳定基本操作插入新节点插入后从插入节点开始向上检查祖先节点的平衡因子。如果发现某个节点的平衡因子绝对值超过 1就需要进行旋转操作来恢复平衡。例如插入节点后某节点左子树高度比右子树高度大 2且插入位置在该节点左子树的左子树上此时就需要进行右旋操作。删除删除节点后同样从删除节点的位置向上检查祖先节点的平衡因子。如果出现不平衡通过一系列的旋转操作和节点调整来重新平衡树。而且删除操作相对插入更复杂因为可能需要多次旋转来恢复平衡。查找和普通二叉搜索树查找方式相同从根节点开始根据比较节点值的大小决定向左子树或右子树继续查找直到找到目标节点或者确定目标节点不存在时间复杂度为优缺比较优点查找效率高且稳定时间复杂度为适用于对查找效率要求较高且插入和删除操作相对不太频繁的场景。缺点每次插入和删除操作都可能需要进行旋转来维持平衡这会增加额外的计算开销导致插入和删除操作的时间复杂度比普通二叉搜索树要高一些。3. 为什么AVL树不要求左右子树的高度为0呢思考与探究为什么 AVL 树要求左右子树的高度差不超过 1而非必须为 0 呢从平衡的理想状态看高度差为 0 确实更平衡但实际情况中部分树的结构无法满足这一要求。当树的节点数为 2、4 ……等特定数量时最优的高度差只能是 1无法强制达到 0这说明 AVL 树的平衡条件是在绝对平衡和实现可行性之间的权衡设计4. 什么是平衡因子通过前面关于 AVL 树的介绍博主相信小伙伴们已经对其有了一定认知在惊叹于它高效的数据查找能力之余。 我相信小伙伴们也一定会好奇AVL 树究竟是如何控制二叉搜索树的高度使其始终保持平衡状态的呢之所以AVL树可以始终保持平衡状态是因为在实现 AVL 树时我们引入了平衡因子balance factor的概念 每个节点都有一个平衡因子其值等于该节点右子树的高度减去左子树的高度因此任何节点的平衡因子只能是 0、1 或 - 1当然平衡因子并非 AVL 树的必需属性还有其他的方法使AVL树保持平衡状态但它如同一个 “风向标”能帮助我们直观观察树的平衡状态并高效控制树的平衡维护过程 —— 通过判断平衡因子是否超出 [-1, 1] 范围可快速定位需要调整的节点进而通过旋转操作恢复树的平衡------------基本操作------------一、查找操作1. 步骤查找操作的步骤定义进行遍历节点的指针使用while循环查找对应节点情况1当前遍历到的节点的键 要查找的键 — “继续向当前节点的右子树中查找”情况2当前遍历到的节点的键 要查找的键 — “继续向当前节点的左子树中查找”情况3当前遍历到的节点的键 要查找的键 — “找到了要查找的键”跳出了循环说明没有找到的键为key的节点2. 简述查找操作的简述初始化从根节点开始查找定义一个指针curr指向根节点_root比较与移动在while循环中不断将当前节点的键curr-_kv.first与要查找的键key进行比较如果curr-_kv.first key这意味着要查找的节点在当前节点的右子树中所以将curr更新为curr-_right继续在右子树中查找如果curr-_kv.first key说明要查找的节点在当前节点的左子树中将curr更新为curr-_left继续在左子树中查找如果curr-_kv.first key表示找到了要查找的节点直接返回当前节点的指针curr查找失败当while循环结束curr变为nullptr这表明在整个 AVL 树中没有找到键为key的节点此时返回nullptrAVL 树的高度是在查找过程中每次比较都会将查找范围缩小到树的一半类似二分查找 因此查找操作的时间复杂度为这意味着即使树中节点数量非常庞大查找操作也能在相对较短的时间内完成。二、插入操作1. 本质插入操作的本质是AVL 树的插入操作是在二叉搜索树插入逻辑基础上增加了平衡维护的关键步骤核心要解决 “插入新节点可能破坏树的平衡导致查询效率下降” 的问题。2. 简述插入操作的简述AVL 树插入二叉搜索树插入找位置、挂节点平衡修复更新平衡因子 旋转调整流程分 5 步空树处理树为空时新节点直接作为根查找插入位置从根出发按二叉搜索树规则小往左、大往右找到新节点的父节点parent确定挂左还是挂右挂载新节点创建新节点连接到parent的左 / 右子树并维护parent指针更新平衡因子从新节点的父节点开始向上更新路径上所有节点的平衡因子_bf反映子树高度变化平衡修复根据平衡因子判断是否失衡绝对值 ≥ 2若失衡则通过旋转操作单旋 / 双旋恢复平衡同时更新旋转后节点的平衡因子3. 步骤插入操作的步骤/----------------第一阶段准备阶段----------------/创建一个遍历树的当前节点指针创建当前遍历节点的父节点的指针/----------------第二阶段查找阶段----------------/ 循环查找插入位置情况1当前遍历到的节点的键 要插入的键 — “继续寻找”情况2当前遍历到的节点的键 要插入的键 — “继续寻找”情况3当前遍历到的节点的键 要插入的键 — “键已存在”— 查找插入位置失败/----------------第三阶段插入阶段----------------/创建要插入的节点将新节点连接到二叉搜索树中情况1新节点的键 父节点的键情况2新节点的键 父节点的键/----------------第四阶段连接阶段----------------/更新新插入节点的父节点核心操作第五阶段调整阶段while (parent)/-------------第一步更新新插入节点的父节点的平衡因子-------------/位置1新插入节点是左子节点 — 父节点的平衡因子 -1位置2新插入节点是右子节点 — 父节点的平衡因子 1/-------------第二步根据父节点的平衡因子做进一步的更新-------------/情况1父节点的平衡因子为 0 — 高度变化未影响上层结束更新情况2父节点的平衡因子为±1 — 高度变化需向上传递继续更新上层节点情况3父节点的平衡因子为±2 — 树失衡需要旋转调整失衡1左左失衡父子平衡因子都为“负” — 右单旋失衡2右右失衡父子平衡因子都为“正” — 左单旋失衡3左右失衡父为“负”子为“正” — 左右双旋失衡4右左失衡父为“正”子为“负” ---- 右左双旋特殊情况非法平衡因子 — 断言失败break情况4非法平衡因子 — 断言失败return true;4. 图示根据父节点的平衡因子做进一步的更新“图示1演示“情况1 情况3”在这里插入图片描述图示2演示“情况2”的最坏情况“一次插入不停的更新”AVL树进行插入的最坏情况从插入节点到根节点一路上父节点的平衡因子均为±1 不断向上更新上层节点直至更新到根节点。在这里插入图片描述三、删除操作哈哈下面咱先不着急搞 AVL 树的删除操作啦为啥呢因为这玩意儿的删除操作啊简直难出天际 —— 就像你本想轻松拆个小快递结果发现里面是个嵌套了十层的俄罗斯套娃每一步都得小心翼翼稍有不慎就把树的平衡给搞崩得不停地调整、旋转。 不过别慌等以后有机会了一定把这 “折磨人” 的 AVL 删除操作好好补上现阶段就让我们先略过吧------------旋转平衡------------AVL树通过下面的四种旋转操作维护平衡这些操作在插入或删除节点导致树失衡时自动触发。右单旋RR 旋转处理 LL 型失衡左单旋LL 旋转处理 RR 型失衡左右双旋RL 旋转处理 RL 型失衡右左双旋LR 旋转处理 LR 型失衡单旋一、右单旋1. 条件右单旋的触发条件当 AVL 树中某个节点的左子树高度比右子树高度大 2且失衡是由左子树的左子树插入节点导致的即左子树的左子树深度增加称为“LL 型失衡”此时需要通过右单旋来恢复平衡。2. 核心右单旋的核心操作旋转过程分为三步以节点parent为旋转中心提升左子节点将parent的左子节点subL提升为新的根节点。处理悬挂子树subL的右子树subLR需要重新挂接到parent的左子树。更新父子关系调整各节点的_parent指针维护三叉链结构。3. 步骤/---------------第一阶段准备阶段---------------/记录parent的左子节点的“指针记录parent的左子节点的右子节点的“指针记录parent的父节点的“指针/---------------第二阶段调整阶段---------------/调整parent和subLR的关系调整parent和subL的关系调整根节点或祖父节点的子树指向情况1parent节点是根节点 — 调整根节点情况2parent节点不是根节点 — 调整祖父节点的子树指向更新平衡因子 — 右单旋后subL和parent的平衡因子均为04. 图示图示1AVL树右单旋的原理图在这里插入图片描述上图展示的是以 10 为根的树结构其中 a、b、c 抽象为三棵高度为的子树且 a、b、c 各自均符合 AVL 树的平衡要求这里的 10既可能是整棵 AVL 树的根节点也可能是整棵树中某局部子树的根把 a、b、c 概括为高度 h 的子树是一种抽象表示它涵盖了所有右单旋场景的共性实际右单旋的具体形态多样下面的图示会展开详细呈现当在 a 子树中插入新节点后a 子树高度从 h 增长为 h 1随着平衡因子沿父节点向上更新传递10 节点的平衡因子从 -1 变为 -2使得以 10 为根的子树左右子树高度差超过 1违反 AVL 树的平衡规则呈现左子树过高的失衡状态此时需要对以 10 为根的子树执行右单旋操作调整子树结构来重新平衡右单旋的核心步骤逻辑由于遵循 “5 b 子树节点值 10” 的搜索树有序性规则旋转时把 b 子树调整为 10 节点的左子树让 10 节点成为 5 节点的右子树5 节点则升级为这棵子树新的根节点这样调整后既维持了二叉搜索树的有序性又使子树恢复平衡同时子树高度回到插入前的 h 2 符合 AVL 树旋转调整的原则若原本 10 所在子树是整棵树的局部子树完成这次旋转后上层节点的平衡状态不会再受影响本次插入操作的平衡调整流程就结束了图示2情况1 --- “插入前a/b/c 的高度h0”在这里插入图片描述图示3情况2 --- “插入前a/b/c 的高度h1”在这里插入图片描述图示4情况3 --- “插入前a/b/c 的高度h2”在这里插入图片描述结论当插入前a/b/c 的高度h2 时候总共有36中触发右单旋转的场景疑问这36中触发右单旋的场景是怎么计算出来的—3*3*436第一个3指的是b子树可以是高度为h2的AVL树x/y/z中的任意一种第二个3指的是c子树可以是高度为h2的AVL树x/y/z中的任意一种4指的是a子树中有4个位置可以再插入一个节点触发“右单旋”图示5情况4 --- “插入前a/b/c 的高度h3”在这里插入图片描述结论当插入前a/b/c 的高度h3 时候总共有5400中触发右单旋转的场景疑问这5400中触发右单旋的场景是怎么计算出来的—15*15*(84*4)5400一般计算触发旋转的场景数的计算公式就是b子树可能存在的情况数量 * c子树可能存在的情况数量 * a子树可以触发旋转的位置数量第一个15指的是b子树可以是高度为h3的AVL树1棵满AVL树 14棵叶子节点为任意1个/任意2个/任意3个的AVL树中的任意一种第二个15指的是c子树可以是高度为h3的15棵AVL树中的任意一种8指的是a子树为高度为h3的15棵AVL树中满二叉树时有8个位置可以再插入一个节点触发“右单旋”4*4指的是a子树为高度为h3的另外14棵AVL树中只有4棵是可以实现触发parent节点的有单旋并且这4棵AVL树中每棵AVL树中有4个位置可以再插入一个节点触发“右单旋”所以一共有4*4中触发“右单旋”的位置二、左单旋1. 条件左单旋的触发条件当 AVL 树中某个节点的右子树高度比左子树高度大 2且失衡是由右子树的右子树插入节点导致即右子树的右子树深度增加称为“RR 型失衡”时需要通过左单旋恢复平衡。2. 核心左单旋的核心操作旋转过程分为三步以节点parent为旋转中心提升右子节点将parent的右子节点subR提升为新的根节点。处理悬挂子树subR的左子树subRL需要重新挂接到parent的右子树。更新父子关系调整各节点的_parent指针维护三叉链结构。3. 步骤/---------------第一阶段准备阶段---------------/记录parent的右子节点的“指针记录parent的右子节点的左子节点的“指针”记录parent的父节点的“指针”/---------------第二阶段调整阶段---------------/调整parent和subRL的关系调整parent和subR的关系调整根节点或祖父节点的子树指向情况1parent节点是根节点 — 调整根节点情况2parent节点不是根节点 — 调整祖父节点的子树指向更新平衡因子 — 左单旋后subR和parent的平衡因子均为04. 图示在这里插入图片描述上面的图展示的是以 10 为根的树结构其中 a、b、c 被抽象为三棵高度为的子树且 a、b、c 各自均符合 AVL 树的平衡要求这里的 10既可能是整棵 AVL 树的根节点也可能是整棵树中某局部子树的根把 a、b、c 概括为高度 h 的子树是一种抽象表示它涵盖了所有左单旋场景的共性实际左单旋的具体形态多样和前文右单旋类似可参照理解 当在 a 子树中插入新节点后a 子树高度从 h 增长为 h 1随着平衡因子沿父节点向上更新传递10 节点的平衡因子从 1 变为 2使得以 10 为根的子树左右子树高度差超过 1违反 AVL 树的平衡规则呈现右子树过高的失衡状态,此时需要对以 10 为根的子树执行左单旋操作调整子树结构来重新平衡左单旋的核心步骤逻辑由于遵循 “10 b 子树节点值 15” 的搜索树有序性规则旋转时把 b 子树调整为 10 节点的右子树让 10 节点成为 15 节点的左子树15 节点则升级为这棵子树新的根节点这样调整后既维持了二叉搜索树的有序性又使子树恢复平衡同时子树高度回到插入前的 h 2 符合 AVL 树旋转调整的原则若原本 10 所在子树是整棵树的局部子树完成这次旋转后上层节点的平衡状态不会再受影响本次插入操作的平衡调整流程就结束了双旋看了上面关于单旋的介绍相信一部分小伙伴就已经觉得OK了右单旋转可以解决左失衡问题左单旋转可以解决右失衡问题那么凭借这两个旋转操作就可以应对AVL树中所有的平衡调整情况。 真的是这样吗我们还是用实际的案例来看一看吧图示1情况1 --- “插入前a/b/c 的高度h0”错误演示使用右单旋解决左右失衡问题在这里插入图片描述图示2情况2 --- “插入前a/b/c 的高度h1”错误演示使用右单旋解决左右失衡问题在这里插入图片描述通过上面的两个图可知当树呈现左子树高的状态时若新节点并非插入到 a 子树而是插入到 b 子树会使 b 子树的高度从 h 变为 h 1进而引发旋转操作。此时仅用右单旋无法解决失衡问题执行右单旋后树依旧处于不平衡状态 。 右单旋能处理 “单纯左子树高即失衡源于左子树的左子树插入节点” 的情况可这里因为新节点插入到了 b 子树以 10 为根的子树不再是简单的左高结构 从 10 的视角看是左子树高但从 5 的视角看5 的右子树更高属于 “左子树的右子树插入导致失衡”即 LR 型失衡 。这种复杂失衡需要两次旋转来解决先以 5 为旋转点执行左单旋再以 10 为旋转点执行右单旋经过这样的操作树就能重新恢复平衡 。一、左右双旋1. 条件左右双旋的触发条件当 AVL 树中某个节点的左子树高度比右子树高度大 2且失衡是由左子树的右子树插入节点导致即左子树的右子树深度增加称为“LR 型失衡”时需要通过左右双旋恢复平衡。左右双旋是左单旋 右单旋的复合操作专门处理LR 型失衡左右双旋通过“先左旋修正左子树方向再右旋整体平衡”的两步操作解决 LR 型失衡问题其核心是在保持 BST 有序性的前提下分阶段调整子树结构确保任意节点的左右子树高度差 ≤ 1这种复合旋转机制让 AVL 树能处理更复杂的失衡场景始终维持近似平衡保证操作的时间复杂度稳定在2. 核心左右双旋的核心操作对subL执行左单旋将subL的右子节点subLR提升为新根subLR的左子树subLRL挂接到subL的右子树对parent执行右单旋将subLR提升为整棵子树的根subLR的原右子树subLRR挂接到parent的左子树更新父子关系调整各节点的_parent指针确保三叉链结构正确更新平衡因子根据插入位置subLR的左 / 右子树分情况修正subLR、subL、parent的平衡因子为 0 或 ±13. 步骤/---------------第一阶段准备阶段---------------/记录parent的右子节点的“指针”记录parent的右子节点的左子节点的“指针”记录parent的右子节点的左子节点的“平衡因子”/---------------第二阶段旋转阶段---------------/首先对当前的节点的右子树进行“右单旋”然后对当前的节点进行“左单旋”/---------------第三阶段更新阶段---------------/情况1subRL节点原始的平衡因子为“-1”情况2subRL节点原始的平衡因子为“1”情况3subRL节点原始的平衡因子为“0”情况4非法平衡因子断言失败.