对于C++：AVL树的实现

开篇介绍：

hello 大家，那么在我们披荆斩棘的学习了Linux系统之后，我们接下来要学习的就是我们的老熟人——C++了，那么在本篇博客，学的是什么呢？？？就如标题所示——AVL树，那么它难吗？？？肯定难，不过不用担心，看完这篇文章，你就会懂了~

在数据结构的世界里，二叉搜索树（BST）是基础且常用的结构，它能实现O(logn)级别的增删查改操作。但理想很丰满，现实很骨感——当插入的节点序列呈有序状态时，二叉搜索树会退化为链表，此时所有操作的时间复杂度都会骤降为O(n)，这在实际开发中是无法接受的。

为了解决这个问题，自平衡二叉搜索树应运而生，而AVL树作为首个被发明的自平衡二叉搜索树，其设计思想和实现逻辑具有里程碑式的意义。

一、AVL树的基础认知：是什么 & 为什么

1.1 什么是AVL树

AVL树的本质是一棵二叉搜索树，但它在二叉搜索树的基础上增加了一个核心约束：树中任意节点的左、右子树的高度差的绝对值不超过1。这个约束确保了AVL树始终保持“高度平衡”的状态，从而避免了二叉搜索树退化为链表的问题。

更严谨的递归定义如下：

• 空树本身是一棵AVL树；
• 若非空树，则需满足两个条件：① 左子树和右子树均为AVL树；② 左、右子树的高度差的绝对值 ≤ 1。

1.2 AVL树的命名由来

AVL树得名于两位前苏联科学家：G.M.Adelson-Velsky 和 E.M.Landis。他们在1962年发表的论文《An algorithm for the organization of information》（一种信息组织算法）中首次提出了这一数据结构，旨在解决二叉搜索树的失衡问题。

1.3 为什么需要AVL树？—— 二叉搜索树的痛点

我们先来看一个二叉搜索树失衡的典型案例：当插入的节点序列为[1,2,3,4,5,6]时，二叉搜索树会呈现出“右斜链”的形态）。此时，查找节点6需要遍历所有6个节点，时间复杂度为O(n)，完全丧失了二叉搜索树的效率优势。

痛点总结：普通二叉搜索树的性能依赖于树的高度，当树失衡时，性能会急剧下降。而AVL树通过严格控制子树高度差，确保树的高度始终稳定在O(logn)级别，从而保证增删查改操作的时间复杂度均为O(logn)。

1.4 平衡因子：AVL树的“平衡风向标”

为了快速判断节点的子树是否平衡，AVL树引入了“平衡因子”（Balance Factor）的概念，这是AVL树实现自平衡的核心工具。

1.4.1 平衡因子的定义

每个节点的平衡因子 = 该节点右子树的高度 - 左子树的高度。

根据AVL树的平衡约束（左右子树高度差绝对值 ≤ 1），任意节点的平衡因子只能取三个值：0、1、-1。

• 平衡因子为0：左、右子树高度相等；
• 平衡因子为1：右子树高度比左子树高1；
• 平衡因子为-1：左子树高度比右子树高1。

1.4.2 平衡因子的核心作用

AVL树本身不“必须”依赖平衡因子，但平衡因子的存在极大地简化了平衡检测与调整的逻辑：

1. 直观反映平衡状态：无需遍历子树计算高度差，只需查看节点的平衡因子，就能快速判断该节点的子树是否失衡；
2. 指导旋转操作：当平衡因子的绝对值变为2时，说明子树已失衡，此时可通过平衡因子的正负判断失衡类型（左偏或右偏），进而选择对应的旋转策略；
3. 简化高度更新：插入或删除节点后，只需沿着路径更新祖先节点的平衡因子，无需重新计算整棵子树的高度。

1.4.3 一个常见疑问：为什么约束是“高度差≤1”而非“高度差=0”？

很多新手会疑惑：既然是“平衡树”，为什么不要求左、右子树高度完全相等（高度差=0）？其实答案很简单：“高度差=0”在实际场景中无法实现全局强制。

举两个典型例子：

1. 仅含2个节点的AVL树：根节点+左/右子节点。此时根节点的左子树高度为1，右子树高度为0（或反之），高度差=1，无法做到0；
2. 含4个节点的AVL树：如根→左→左，根→右。此时根节点左子树高度为2，右子树高度为1，高度差=1，同样无法做到0。

结论：“高度差≤1”是兼顾可行性与平衡性的最优设计——既保证了树的高度不会过高，又避免了过度追求“完美平衡”而导致的实现复杂度飙升。

1.5 AVL树的性能优势

AVL树的节点分布特征与完全二叉树高度相似，其高度可稳定控制在O(log₂n)级别（n为节点数）。这带来了显著的性能提升：

需要说明的是：AVL树的增删操作会额外增加旋转和平衡因子更新的开销，但这些开销是常数级别的（O(1)），不会影响整体的时间复杂度。

二、AVL树的核心：节点结构设计

AVL树的节点是实现所有功能的基础，其结构在二叉搜索树节点的基础上，增加了两个关键成员：平衡因子和父节点指针。

2.1 节点结构的核心需求

要实现AVL树的自平衡功能，节点需要满足以下需求：

1. 存储键值对（key-value）：符合二叉搜索树的基本特性；
2. 指向左、右子节点：实现树的层级结构；
3. 指向父节点：插入节点后，需要沿着父节点路径向上更新平衡因子，父节点指针是实现这一功能的关键；
4. 存储平衡因子：快速判断节点的平衡状态。

2.2 C++实现代码

我们采用模板类设计节点结构，以支持不同类型的键值对：

// AVL树的节点类（模板类） template <typename K, typename V> struct AVLTreeNode { pair<K, V> _kv; // 存储键值对（key-value） AVLTreeNode<K, V>* _left = nullptr; // 指向左孩子的指针 AVLTreeNode<K, V>* _right = nullptr; // 指向右孩子的指针 AVLTreeNode<K, V>* _parent = nullptr; // 指向父节点的指针（核心新增） int _bf = 0; // 平衡因子（默认值为0） // 构造函数：初始化键值对和平衡因子 AVLTreeNode(const pair<K, V> kv) : _kv(kv) , _bf(0) , _left(nullptr) , _right(nullptr) , _parent(nullptr) { // 无额外逻辑 } };

2.3 关键成员解析

2.3.1 键值对（_kv）

使用C++标准库中的pair结构体存储键值对，其中pair.first为键（key），pair.second为值（value）。这种设计符合实际开发中的常用场景（如字典、映射表）。

2.3.2 父节点指针（_parent）

这是AVL树节点与普通二叉搜索树节点的核心区别之一。当插入一个新节点后，只有新节点的祖先节点的平衡因子可能发生变化，因此需要通过父节点指针沿着路径向上遍历，依次更新这些节点的平衡因子。如果没有父节点指针，就无法高效地找到这些祖先节点。

2.3.3 平衡因子（_bf）

默认值为0，因为新插入的节点都是叶子节点（左右子树均为空），其平衡因子自然为0（右子树高度0 - 左子树高度0 = 0）。

三、AVL树的核心操作：插入与平衡调整

AVL树的插入操作是其最核心的功能，整体流程分为两步：

• ① 按照二叉搜索树的规则插入新节点；
• ② 沿着父节点路径向上更新平衡因子，若发现失衡则进行旋转调整。

需要说明的是：AVL树的删除操作复杂度较高，且在实际面试和开发中极少涉及（工业级应用更倾向于使用红黑树），因此本文暂不讲解删除操作，重点聚焦于插入操作。

3.1 插入操作的整体流程

1. 查找插入位置：从根节点出发，按照二叉搜索树的规则（小的往左，大的往右）找到新节点的插入位置，同时记录父节点；
2. 插入新节点：创建新节点，将其挂载到父节点的对应位置（左孩子或右孩子），并设置新节点的父节点指针；
3. 更新平衡因子：从新节点的父节点开始，沿着路径向上更新每个祖先节点的平衡因子；
4. 判断是否失衡：若某个节点的平衡因子绝对值变为2，说明该节点的子树已失衡，需根据失衡类型进行旋转调整；
5. 旋转调整：通过旋转恢复子树的平衡，旋转后无需继续向上更新（因为旋转会降低子树的高度，不会影响上层节点）。

3.2 步骤1：查找插入位置并插入新节点

这一步与普通二叉搜索树的插入逻辑完全一致，核心是找到正确的插入位置并挂载新节点。

template <typename K, typename V> class AVLTree { public: using node = AVLTreeNode<K, V>; // 类型重命名，简化代码 bool Insert(const pair<K, V> data) { node* cur = _root; node* parent = nullptr; // 情况1：树为空，直接将新节点作为根节点 if (_root == nullptr) { _root = new node(data); return true; } // 情况2：树非空，查找插入位置 while (cur != nullptr) { if (cur->_kv.first < data.first) // 插入值比当前节点大，往右走 { parent = cur; cur = cur->_right; } else if (cur->_kv.first > data.first) // 插入值比当前节点小，往左走 { parent = cur; cur = cur->_left; } else // 键值已存在，插入失败（AVL树不允许重复键） { return false; } } // 插入新节点：根据父节点的键值判断挂载到左还是右 cur = new node(data); if (parent->_kv.first > data.first) { parent->_left = cur; // 插入到父节点的左孩子 } else { parent->_right = cur; // 插入到父节点的右孩子 } cur->_parent = parent; // 设置新节点的父节点 // 后续步骤：更新平衡因子 + 失衡调整（见3.3和3.4节） // ... } private: node* _root = nullptr; // 树的根节点 };

3.3 步骤2：更新平衡因子的核心逻辑

插入新节点后，只有新节点的祖先节点的平衡因子可能发生变化——因为新节点会使某一条路径的子树高度增加1。更新平衡因子的关键是：判断当前节点是父节点的左孩子还是右孩子，进而决定父节点平衡因子的变化方向。

3.3.1 平衡因子的更新规则

假设当前节点为cur，其父节点为parent：

• 若cur是parent的左孩子：parent的左子树高度增加1 → parent的平衡因子 减1（因为平衡因子=右子树高度-左子树高度）；
• 若cur是parent的右孩子：parent的右子树高度增加1 → parent的平衡因子 加1。

注意：父节点平衡因子的变化方向，仅取决于cur是parent的左/右孩子，与cur自身的平衡因子无关。

3.3.2 平衡因子更新的停止条件

更新平衡因子的过程需要沿着父节点路径向上进行，直到满足以下任一条件：

1. parent的平衡因子变为0：说明插入前parent的左右子树高度不等，插入后高度相等，子树高度未增加，无需继续向上更新；
2. parent的平衡因子变为±2：说明子树已失衡，需进行旋转调整，调整后子树高度恢复，无需继续向上更新；
3. 遍历到根节点：此时已更新完所有祖先节点，插入流程结束。

更新到10结点，平衡因子为2，10所在的子树已经不平衡，需要旋转处理：

更新到中间结点，3为根的子树高度不变，不会影响上一层，更新结束：

最坏更新到根停止：

3.3.3 平衡因子更新的代码实现

// 接3.2节的Insert函数，插入新节点后开始更新平衡因子 while (parent != nullptr) { // 第一步：更新父节点的平衡因子 if (cur == parent->_left) // cur是parent的左孩子，parent的bf减1 { --parent->_bf; } else if (cur == parent->_right) // cur是parent的右孩子，parent的bf加1 { ++parent->_bf; } else { assert(false); // 逻辑错误，cur不可能既不是parent的左孩子也不是右孩子 } // 第二步：判断是否需要继续向上更新 if (parent->_bf == 0) { // 插入前parent的bf为±1，插入后变为0，子树高度未增加，停止更新 break; } else if (parent->_bf == 1 || parent->_bf == -1) { // 插入前parent的bf为0，插入后变为±1，子树高度增加1，需继续向上更新 cur = parent; parent = cur->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { // 子树失衡，需要进行旋转调整 // 旋转逻辑见3.4节 // ... break; // 旋转后子树平衡，停止更新 } }

3.4 步骤3：失衡类型与旋转调整

当某个节点的平衡因子绝对值变为2时，说明该节点的子树已失衡。根据失衡节点的平衡因子以及其孩子节点的平衡因子，可以将失衡分为四种类型，每种类型对应不同的旋转策略。

核心原则：旋转的目标是恢复子树的平衡，同时保持二叉搜索树的有序性，并且降低子树的高度（使其恢复到插入前的高度，避免影响上层节点）。

3.4.1 四种失衡类型的判断

假设失衡节点为parent（bf=±2），其左孩子为subL，右孩子为subR：

1. LL型失衡：parent的bf=-2（左子树过高），且subL的bf=-1（左子树的左子树过高）；
2. RR型失衡：parent的bf=2（右子树过高），且subR的bf=1（右子树的右子树过高）；
3. LR型失衡：parent的bf=-2（左子树过高），且subL的bf=1（左子树的右子树过高）；
4. RL型失衡：parent的bf=2（右子树过高），且subR的bf=-1（右子树的左子树过高）。

记忆口诀：父节点定方向（左偏或右偏），孩子节点定类型（单旋或双旋）。

3.4.2 第一种失衡类型：LL型失衡（右单旋）

场景描述

新节点插入在失衡节点parent的左孩子subL的左子树中，导致parent的左子树高度比右子树高2（parent的bf=-2），且subL的左子树高度高于右子树（subL的bf=-1）。

示例结构（抽象为子树a、b、c，高度均为h）：

 parent (bf=-2) / subL (bf=-1) / a (h) / \ ... ... / 新节点

其中，a、b、c均为高度为h的AVL子树（h≥0），满足二叉搜索树的有序性（a < subL < b < parent < c）。

旋转目标

将subL提升为新的子树根节点，parent降级为subL的右孩子，同时将subL的右子树b挂载为parent的左孩子（保持二叉搜索树的有序性）。

旋转步骤（核心）

1. 保存subL的右子树b（subLR = subL->_right）；
2. 将b挂载为parent的左孩子（若b非空，需设置b的父节点为parent）；
3. 将parent挂载为subL的右孩子，并设置parent的父节点为subL；
4. 处理subL的父节点：若parent是原树的根节点，则subL成为新根；否则，将subL挂载到parent原父节点的对应位置（左或右孩子）；
5. 更新平衡因子：旋转后parent和subL的平衡因子均变为0（因为a、b、c的高度均为h，子树高度恢复平衡）。

右单旋代码实现

// 右单旋：处理LL型失衡，参数parent为失衡节点 void RotateR(node* parent) { assert(parent); assert(parent->_left); // LL型失衡，parent必须有左孩子subL node* subL = parent->_left; // subL是parent的左孩子 node* subLR = subL->_right; // subLR是subL的右孩子（可能为空） node* parentParent = parent->_parent; // parent的父节点 // 步骤1：将subLR挂载为parent的左孩子 parent->_left = subLR; if (subLR != nullptr) { subLR->_parent = parent; } // 步骤2：将parent挂载为subL的右孩子 subL->_right = parent; parent->_parent = subL; // 步骤3：处理subL的父节点（挂载到原parent的父节点上） if (parentParent == nullptr) { // parent是原树的根节点，subL成为新根 _root = subL; subL->_parent = nullptr; } else { // 根据parent是原父节点的左/右孩子，将subL挂载到对应位置 if (parent == parentParent->_left) { parentParent->_left = subL; } else { parentParent->_right = subL; } subL->_parent = parentParent; } // 步骤4：更新平衡因子 parent->_bf = 0; subL->_bf = 0; }

3.4.3 第二种失衡类型：RR型失衡（左单旋）

场景描述

新节点插入在失衡节点parent的右孩子subR的右子树中，导致parent的右子树高度比左子树高2（parent的bf=2），且subR的右子树高度高于左子树（subR的bf=1）。

示例结构（抽象为子树a、b、c，高度均为h）：

parent (bf=2) \ subR (bf=1) \ c (h) / \ ... ... \ 新节点

其中，a、b、c均为高度为h的AVL子树（h≥0），满足二叉搜索树的有序性（a < parent < b < subR < c）。

旋转目标

将subR提升为新的子树根节点，parent降级为subR的左孩子，同时将subR的左子树b挂载为parent的右孩子（保持二叉搜索树的有序性）。

旋转步骤（核心）

与右单旋完全对称，只需将“左”和“右”互换：

1. 保存subR的左子树b（subRL = subR->_left）；
2. 将b挂载为parent的右孩子（若b非空，需设置b的父节点为parent）；
3. 将parent挂载为subR的左孩子，并设置parent的父节点为subR；
4. 处理subR的父节点：若parent是原树的根节点，则subR成为新根；否则，将subR挂载到parent原父节点的对应位置（左或右孩子）；
5. 更新平衡因子：旋转后parent和subR的平衡因子均变为0。

左单旋代码实现

// 左单旋：处理RR型失衡，参数parent为失衡节点 void RotateL(node* parent) { assert(parent); assert(parent->_right); // RR型失衡，parent必须有右孩子subR node* subR = parent->_right; // subR是parent的右孩子 node* subRL = subR->_left; // subRL是subR的左孩子（可能为空） node* parentParent = parent->_parent; // parent的父节点 // 步骤1：将subRL挂载为parent的右孩子 parent->_right = subRL; if (subRL != nullptr) { subRL->_parent = parent; } // 步骤2：将parent挂载为subR的左孩子 subR->_left = parent; parent->_parent = subR; // 步骤3：处理subR的父节点（挂载到原parent的父节点上） if (parentParent == nullptr) { // parent是原树的根节点，subR成为新根 _root = subR; subR->_parent = nullptr; } else { // 根据parent是原父节点的左/右孩子，将subR挂载到对应位置 if (parent == parentParent->_left) { parentParent->_left = subR; } else { parentParent->_right = subR; } subR->_parent = parentParent; } // 步骤4：更新平衡因子 parent->_bf = 0; subR->_bf = 0; }

3.4.4 第三种失衡类型：LR型失衡（左右双旋）

场景描述

新节点插入在失衡节点parent的左孩子subL的右子树中，导致parent的左子树高度比右子树高2（parent的bf=-2），且subL的右子树高度高于左子树（subL的bf=1）。

示例结构（抽象为子树a、e、f、c，高度均为h-1）：

 parent (bf=-2) / subL (bf=1) \ subLR (bf=±1或0) / \ e f / \ ... 新节点

其中，a、e、f、c均为高度为h-1的AVL子树（h≥1），满足二叉搜索树的有序性（a < subL < e < subLR < f < parent < c）。

为什么需要双旋？

LR型失衡无法通过单次右单旋解决。因为此时subL的右子树（subLR）过高，直接对parent进行右单旋会导致subLR的子树继续失衡。因此需要分两步旋转：① 先对subL进行左单旋，将LR型失衡转化为LL型失衡；② 再对parent进行右单旋，恢复子树平衡。

旋转步骤（核心）

1. 第一步：对subL进行左单旋（RotateL(subL)）。旋转后，subLR成为subL的父节点，原subLR的左子树e挂载为subL的右子树；
2. 第二步：对parent进行右单旋（RotateR(parent)）。旋转后，subLR成为新的子树根节点，原subLR的右子树f挂载为parent的左子树；
3. 更新平衡因子：根据subLR旋转前的平衡因子，分三种情况更新（关键难点）。

平衡因子的更新规则（核心难点）

旋转前需要记录subLR的平衡因子（bf），因为它决定了旋转后subL和parent的平衡因子取值：

1. 情况1：subLR的bf=-1（新节点插入在e子树中）。旋转后：subL的bf=0，subLR的bf=0，parent的bf=1；
2. 情况2：subLR的bf=1（新节点插入在f子树中）。旋转后：subL的bf=-1，subLR的bf=0，parent的bf=0；
3. 情况3：subLR的bf=0（subLR本身就是新节点，e和f均为空）。旋转后：subL的bf=0，subLR的bf=0，parent的bf=0。

推导逻辑：旋转后子树的高度由最高的子树决定，平衡因子的取值本质是“各子树高度差的反映”。建议通过画图辅助理解，重点关注各子树的高度变化。

左右双旋代码实现

// 左右双旋：处理LR型失衡，参数parent为失衡节点 void RotateLR(node* parent) { assert(parent); assert(parent->_left); // LR型失衡，parent必须有左孩子subL node* subL = parent->_left; node* subLR = subL->_right; int bf = subLR->_bf; // 记录subLR旋转前的平衡因子 // 第一步：对subL进行左单旋，转化为LL型失衡 RotateL(subL); // 第二步：对parent进行右单旋，恢复平衡 RotateR(parent); // 根据subLR旋转前的平衡因子，更新三个节点的平衡因子 if (bf == 0) { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 0; } else if (bf == -1) { subL->_bf = 0; subLR->_bf = 0; parent->_bf = 1; } else if (bf == 1) { subL->_bf = -1; subLR->_bf = 0; parent->_bf = 0; } else { assert(false); // 平衡因子取值非法 } }

3.4.5 第四种失衡类型：RL型失衡（右左双旋）

场景描述

新节点插入在失衡节点parent的右孩子subR的左子树中，导致parent的右子树高度比左子树高2（parent的bf=2），且subR的左子树高度高于右子树（subR的bf=-1）。

示例结构（抽象为子树a、e、f、c，高度均为h-1）：

parent (bf=2) \ subR (bf=-1) / subRL (bf=±1或0) / \ e f / \ 新节点 ...

其中，a、e、f、c均为高度为h-1的AVL子树（h≥1），满足二叉搜索树的有序性（a < parent < e < subRL < f < subR < c）。

旋转步骤（核心）

与左右双旋完全对称，分两步旋转：① 先对subR进行右单旋，将RL型失衡转化为RR型失衡；② 再对parent进行左单旋，恢复子树平衡。

平衡因子的更新规则

旋转前记录subRL的平衡因子（bf），根据其取值更新平衡因子：

1. 情况1：subRL的bf=1（新节点插入在e子树中）。旋转后：subR的bf=0，subRL的bf=0，parent的bf=-1；
2. 情况2：subRL的bf=-1（新节点插入在f子树中）。旋转后：subR的bf=1，subRL的bf=0，parent的bf=0；
3. 情况3：subRL的bf=0（subRL本身就是新节点，e和f均为空）。旋转后：subR的bf=0，subRL的bf=0，parent的bf=0。

右左双旋代码实现

// 右左双旋：处理RL型失衡，参数parent为失衡节点 void RotateRL(node* parent) { assert(parent); assert(parent->_right); // RL型失衡，parent必须有右孩子subR node* subR = parent->_right; node* subRL = subR->_left; int bf = subRL->_bf; // 记录subRL旋转前的平衡因子 // 第一步：对subR进行右单旋，转化为RR型失衡 RotateR(subR); // 第二步：对parent进行左单旋，恢复平衡 RotateL(parent); // 根据subRL旋转前的平衡因子，更新三个节点的平衡因子 if (bf == 0) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = 0; } else if (bf == 1) { subR->_bf = 0; subRL->_bf = 0; parent->_bf = -1; } else if (bf == -1) { subR->_bf = 1; subRL->_bf = 0; parent->_bf = 0; } else { assert(false); // 平衡因子取值非法 } }

3.4.6 插入操作的完整代码（整合旋转逻辑）

template <typename K, typename V> bool AVLTree<K, V>::Insert(const pair<K, V> data) { node* cur = _root; node* parent = nullptr; // 步骤1：查找插入位置并插入新节点 if (_root == nullptr) { _root = new node(data); return true; } while (cur != nullptr) { if (cur->_kv.first < data.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > data.first) { parent = cur; cur = cur->_left; } else { return false; // 键值重复，插入失败 } } cur = new node(data); if (parent->_kv.first > data.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; // 步骤2：更新平衡因子并判断是否失衡 while (parent != nullptr) { // 更新父节点的平衡因子 if (cur == parent->_left) { --parent->_bf; } else if (cur == parent->_right) { ++parent->_bf; } // 判断是否需要继续更新或旋转 if (parent->_bf == 0) { break; } else if (parent->_bf == 1 || parent->_bf == -1) { cur = parent; parent = cur->_parent; } else if (parent->_bf == 2 || parent->_bf == -2) { // 根据失衡类型进行旋转 if (parent->_bf == -2 && parent->_left->_bf == -1) { RotateR(parent); // LL型：右单旋 } else if (parent->_bf == 2 && parent->_right->_bf == 1) { RotateL(parent); // RR型：左单旋 } else if (parent->_bf == -2 && parent->_left->_bf == 1) { RotateLR(parent); // LR型：左右双旋 } else if (parent->_bf == 2 && parent->_right->_bf == -1) { RotateRL(parent); // RL型：右左双旋 } else { assert(false); } break; // 旋转后平衡，停止更新 } } return true; }

四、AVL树的其他核心操作

除了插入操作，AVL树的查找、平衡检测等操作也非常重要。这些操作的逻辑相对简单，下面逐一讲解。

4.1 查找操作

AVL树的查找逻辑与普通二叉搜索树完全一致，因为旋转操作不会破坏二叉搜索树的有序性。查找效率稳定为O(logn)。

4.1.1 查找操作的代码实现

// 查找指定key是否存在，返回bool值 bool Find(const K& key) { node* cur = _root; while (cur != nullptr) { if (cur->_kv.first < key) // key比当前节点大，往右走 { cur = cur->_right; } else if (cur->_kv.first > key) // key比当前节点小，往左走 { cur = cur->_left; } else // 找到key，返回true { return true; } } return false; // 未找到key } // 重载版本：查找指定key，返回节点指针（可通过节点访问value） node* FindNode(const K& key) { node* cur = _root; while (cur != nullptr) { if (cur->_kv.first < key) { cur = cur->_right; } else if (cur->_kv.first > key) { cur = cur->_left; } else { return cur; } } return nullptr; }

4.2 平衡检测操作

实现AVL树后，需要验证其是否符合平衡约束。平衡检测的核心是：① 任意节点的左右子树高度差绝对值 ≤ 1；② 任意节点的平衡因子等于其右子树高度减去左子树高度。

4.2.1 辅助函数：计算树的高度

// 计算以root为根的子树高度（空树高度为0，叶子节点高度为1） int _AVLTreeHeight(node* root) { if (root == nullptr) { return 0; } int leftHeight = _AVLTreeHeight(root->_left); int rightHeight = _AVLTreeHeight(root->_right); // 子树高度 = 左右子树中最高的高度 + 1（当前节点） return max(leftHeight, rightHeight) + 1; }

4.2.2 平衡检测的代码实现

// 递归检测以root为根的子树是否为AVL树 bool _IsBalanceTree(node* root) { // 空树是AVL树 if (root == nullptr) { return true; } // 计算当前节点的左右子树高度差 int leftHeight = _AVLTreeHeight(root->_left); int rightHeight = _AVLTreeHeight(root->_right); int diff = rightHeight - leftHeight; // 检测1：左右子树高度差绝对值是否 ≤ 1 if (abs(diff) >= 2) { cout << "节点key=" << root->_kv.first << " 高度差异常（差为" << diff << "）" << endl; return false; } // 检测2：当前节点的平衡因子是否正确 if (root->_bf != diff) { cout << "节点key=" << root->_kv.first << " 平衡因子异常（实际为" << diff << "，存储为" << root->_bf << "）" << endl; return false; } // 递归检测左、右子树 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); } // 对外接口：检测整棵树是否为AVL树 bool IsBalanceTree() { return _IsBalanceTree(_root); }

4.3 中序遍历操作

中序遍历可以验证AVL树是否保持二叉搜索树的有序性（中序遍历结果为升序）。

// 递归中序遍历（辅助函数） void _inorder(const node* root) const { if (root == nullptr) { return; } _inorder(root->_left); // 遍历左子树 cout << "key=" << root->_kv.first << ", value=" << root->_kv.second << endl; // 访问根节点 _inorder(root->_right); // 遍历右子树 } // 对外接口：中序遍历整棵树 void InOrder() const { _inorder(_root); }

五、AVL树的测试验证

为了确保AVL树的实现正确，我们设计两组测试用例：① 常规测试用例（包含单旋和双旋场景）；② 大量随机数据测试。下面将详细讲解每组测试的设计思路、实现代码及结果验证方式。

5.1 常规测试用例：覆盖单旋与双旋场景

常规测试的核心目标是精准覆盖AVL树插入过程中可能出现的LL、RR、LR、RL四种失衡场景，通过手动构造插入序列，验证旋转操作的正确性。测试流程为：构造插入序列 → 插入AVL树 → 中序遍历验证有序性 → 平衡检测验证平衡性。

5.1.1 测试用例设计（覆盖四种失衡场景）

1. LL型失衡测试用例：插入序列 [3,2,1]。插入1时，根节点3的左子树高度比右子树高2（bf=-2），左孩子2的bf=-1，触发右单旋。
2. RR型失衡测试用例：插入序列 [1,2,3]。插入3时，根节点1的右子树高度比左子树高2（bf=2），右孩子2的bf=1，触发左单旋。
3. LR型失衡测试用例：插入序列 [3,1,2]。插入2时，根节点3的左子树高度比右子树高2（bf=-2），左孩子1的bf=1，触发左右双旋。
4. RL型失衡测试用例：插入序列 [1,3,2]。插入2时，根节点1的右子树高度比左子树高2（bf=2），右孩子3的bf=-1，触发右左双旋。
5. 混合场景测试用例：插入序列 [10,5,15,3,7,12,18,2,4,6,8,11,13,17,19]。该序列包含多次单旋和双旋操作，用于验证复杂插入场景下AVL树的稳定性。

5.1.2 测试代码实现

基于前文实现的AVL树类，编写测试代码如下（包含必要的头文件和主函数）：

#include <iostream> #include <vector> #include <algorithm> // 用于max函数 #include <utility> // 用于pair using namespace std; // 此处粘贴前文实现的AVLTreeNode结构体和AVLTree类完整代码 // ...（省略已实现的节点结构和AVL树类代码，测试时需包含完整实现）... // 常规测试用例执行函数 void RegularTest() { // 测试用例1：LL型失衡（插入序列[3,2,1]） cout << "==================== LL型失衡测试 ====================" << endl; AVLTree<int, int> llTree; vector<pair<int, int>> llSeq = {{3,30}, {2,20}, {1,10}}; for (auto& p : llSeq) { llTree.Insert(p); } cout << "LL型测试 - 中序遍历结果（应升序）：" << endl; llTree.InOrder(); bool llBalance = llTree.IsBalanceTree(); cout << "LL型测试 - 平衡检测结果（应true）：" << (llBalance ? "平衡" : "失衡") << endl << endl; // 测试用例2：RR型失衡（插入序列[1,2,3]） cout << "==================== RR型失衡测试 ====================" << endl; AVLTree<int, int> rrTree; vector<pair<int, int>> rrSeq = {{1,10}, {2,20}, {3,30}}; for (auto& p : rrSeq) { rrTree.Insert(p); } cout << "RR型测试 - 中序遍历结果（应升序）：" << endl; rrTree.InOrder(); bool rrBalance = rrTree.IsBalanceTree(); cout << "RR型测试 - 平衡检测结果（应true）：" << (rrBalance ? "平衡" : "失衡") << endl << endl; // 测试用例3：LR型失衡（插入序列[3,1,2]） cout << "==================== LR型失衡测试 ====================" << endl; AVLTree<int, int> lrTree; vector<pair<int, int>> lrSeq = {{3,30}, {1,10}, {2,20}}; for (auto& p : lrSeq) { lrTree.Insert(p); } cout << "LR型测试 - 中序遍历结果（应升序）：" << endl; lrTree.InOrder(); bool lrBalance = lrTree.IsBalanceTree(); cout << "LR型测试 - 平衡检测结果（应true）：" << (lrBalance ? "平衡" : "失衡") << endl << endl; // 测试用例4：RL型失衡（插入序列[1,3,2]） cout << "==================== RL型失衡测试 ====================" << endl; AVLTree<int, int> rlTree; vector<pair<int, int>> rlSeq = {{1,10}, {3,30}, {2,20}}; for (auto& p : rlSeq) { rlTree.Insert(p); } cout << "RL型测试 - 中序遍历结果（应升序）：" << endl; rlTree.InOrder(); bool rlBalance = rlTree.IsBalanceTree(); cout << "RL型测试 - 平衡检测结果（应true）：" << (rlBalance ? "平衡" : "失衡") << endl << endl; // 测试用例5：混合场景测试（插入序列[10,5,15,3,7,12,18,2,4,6,8,11,13,17,19]） cout << "==================== 混合场景测试 ====================" << endl; AVLTree<int, int> mixTree; vector<pair<int, int>> mixSeq = {{10,100}, {5,50}, {15,150}, {3,30}, {7,70}, {12,120}, {18,180}, {2,20}, {4,40}, {6,60}, {8,80}, {11,110}, {13,130}, {17,170}, {19,190}}; for (auto& p : mixSeq) { mixTree.Insert(p); } cout << "混合场景测试 - 中序遍历结果（应升序）：" << endl; mixTree.InOrder(); bool mixBalance = mixTree.IsBalanceTree(); cout << "混合场景测试 - 平衡检测结果（应true）：" << (mixBalance ? "平衡" : "失衡") << endl; }

5.1.3 常规测试结果解读

正确执行上述测试代码后，应满足以下两个核心条件：

1. 中序遍历结果均为严格升序：验证AVL树的二叉搜索树特性未被旋转操作破坏，这是树结构功能正确性的基础；
2. 平衡检测结果均为“平衡”：验证四种失衡场景下，旋转操作能准确恢复树的平衡状态，任意节点的左右子树高度差绝对值≤1，且平衡因子存储正确。

若出现中序遍历无序或平衡检测失衡的情况，需重点排查以下问题：① 插入逻辑中键值比较是否正确；② 旋转操作中节点指针挂载（尤其是父节点指针）是否错误；③ 平衡因子更新规则（尤其是双旋场景下的因子调整）是否有误。

5.2 大量随机数据测试：验证稳定性与鲁棒性

常规测试用例覆盖了典型场景，但实际开发中AVL树需处理海量随机数据。大量随机数据测试的目标是：验证AVL树在高并发、大规模数据插入场景下的稳定性，避免因边界条件（如重复键值、极端随机序列）导致的逻辑漏洞。

5.2.1 测试设计思路

1. 生成随机键值对：键值范围设为[1, 1000000]，确保足够大的取值空间；生成数量设为100000个，模拟大规模数据场景；
2. 去重处理：AVL树不允许重复键值，需对生成的随机键进行去重，避免插入失败影响测试结果；
3. 插入与验证：将去重后的键值对插入AVL树，插入完成后执行两项验证：① 中序遍历验证有序性；② 平衡检测验证平衡性；
4. 多次重复测试：由于随机序列具有不确定性，重复测试10次，确保所有测试均通过，排除偶然因素导致的误判。

5.2.2 测试代码实现

#include <random> #include <unordered_set> // 生成随机键值对（去重） vector<pair<int, int>> GenerateRandomSeq(int count, int minKey, int maxKey) { vector<pair<int, int>> seq; unordered_set<int> keySet; // 用于去重 random_device rd; mt19937 gen(rd()); uniform_int_distribution<> distr(minKey, maxKey); while (seq.size() < count) { int key = distr(gen); if (keySet.find(key) == keySet.end()) // 键值未重复 { keySet.insert(key); seq.emplace_back(key, key * 10); // value设为key的10倍，简化逻辑 } } return seq; } // 大量随机数据测试执行函数 void RandomDataTest() { const int TEST_TIMES = 10; // 重复测试次数 const int DATA_COUNT = 100000; // 每次测试的数据量 const int MIN_KEY = 1; // 键值最小值 const int MAX_KEY = 1000000; // 键值最大值 for (int i = 0; i < TEST_TIMES; ++i) { cout << "==================== 随机数据测试第" << (i+1) << "次 ====================" << endl; // 生成随机去重序列 vector<pair<int, int>> randomSeq = GenerateRandomSeq(DATA_COUNT, MIN_KEY, MAX_KEY); // 插入AVL树 AVLTree<int, int> avlTree; for (auto& p : randomSeq) { avlTree.Insert(p); } // 验证1：平衡检测 bool isBalance = avlTree.IsBalanceTree(); cout << "随机数据测试 - 平衡检测结果（应true）：" << (isBalance ? "平衡" : "失衡") << endl; // 验证2：中序遍历有序性（抽样验证，避免全量输出占用资源） // 此处采用抽样验证：取前10个和后10个元素，判断是否升序 vector<int> sampleKeys; auto collectKeys = [&sampleKeys](const AVLTreeNode<int, int>* root) { if (root == nullptr) return; collectKeys(root->_left); sampleKeys.push_back(root->_kv.first); collectKeys(root->_right); }; collectKeys(avlTree.FindNode(randomSeq[0].first)->_parent); // 从根节点开始收集 bool isSorted = true; for (int j = 1; j < sampleKeys.size(); ++j) { if (sampleKeys[j] < sampleKeys[j-1]) { isSorted = false; break; } } cout << "随机数据测试 - 中序遍历有序性（抽样验证，应true）：" << (isSorted ? "有序" : "无序") << endl; // 额外：输出树的高度（验证是否为O(logn)级别） int treeHeight = avlTree._AVLTreeHeight(avlTree.FindNode(randomSeq[0].first)->_parent); cout << "随机数据测试 - 树的高度（理论值约log2(" << DATA_COUNT << ")=" << log2(DATA_COUNT) << "）：" << treeHeight << endl; if (!isBalance || !isSorted) { cout << "第" << (i+1) << "次随机测试失败！" << endl; return; } } cout << "\n所有" << TEST_TIMES << "次随机数据测试均通过，AVL树实现稳定！" << endl; }

5.2.3 随机数据测试结果解读

成功完成测试后，应得到以下结论：

1. 稳定性：10次重复测试均通过平衡检测和有序性验证，说明AVL树在大规模随机数据插入场景下无逻辑漏洞，鲁棒性良好；
2. 高度特性：树的实际高度接近log₂(n)（如n=100000时，log₂(100000)≈17，实际高度通常在17-20之间），验证了AVL树“高度稳定在O(logn)级别”的核心优势；
3. 性能参考：插入100000个随机节点的耗时主要集中在数据生成和插入遍历，旋转操作的常数级开销对整体性能影响极小，远优于失衡的普通二叉搜索树。

若测试中出现失败，需重点排查：① 随机数生成与去重逻辑是否正确；② 平衡因子更新在大规模数据插入时是否存在累积错误；③ 旋转操作在深层节点（树高度较高时）的指针处理是否遗漏。

5.3 测试总结与注意事项

通过常规测试用例和大量随机数据测试的双重验证，可充分确保AVL树实现的正确性。测试过程中需注意以下细节：

1. 重复键值处理：AVL树不支持重复键，测试时需严格去重，避免插入失败导致后续验证逻辑异常；
2. 边界场景补充：除上述测试外，可额外补充“空树插入”“单节点插入”“连续插入相同方向节点”等边界场景，覆盖更全面的逻辑分支；
3. 性能测试说明：本文测试重点为功能正确性，若需精准性能测试，需排除IO输出（如中序遍历全量打印）的影响，通过计算插入耗时、查找耗时的平均值进行对比。

至此，AVL树从原理到代码实现的全流程解析与验证已完成。AVL树作为首个自平衡二叉搜索树，其平衡因子与旋转调整的设计思想，为后续红黑树、Splay树等高级平衡树的发展奠定了基础。尽管在工业级应用中，红黑树因删除操作更高效而应用更广泛，但深入理解AVL树的实现逻辑，仍是掌握数据结构“平衡”核心思想的关键。

完整代码：

下面给出完整代码：

AVLTree.hpp:

#pragma once #include <iostream> #include <vector> #include <algorithm> #include <functional> #include <string> #include <assert.h> using namespace std; //ok，那么在这里，我们就实现一下AVL树，也就是自平衡树 //======================================== //1. AVL树的基础定义 //- AVL树是首个被发明的自平衡二叉查找树（Self - Balancing Binary Search Tree） //- AVL树的本质也是一棵二叉搜索树 //- 空树本身就是一棵AVL树；若非空，则需满足两个核心条件： //① 左子树和右子树均为AVL树（递归定义）； //② 左、右子树的高度差的绝对值不超过1（即 | h_right - h_left | ≤ 1）； //- 核心目标：通过严格控制子树高度差，让AVL树始终保持「高度平衡」，避免普通二叉搜索树的失衡问题。 // //2. AVL树的命名由来 //- 得名于两位前苏联科学家：G.M.Adelson - Velsky 和 E.M.Landis； //- 该数据结构首次发表于二人1962年的论文《An algorithm for the organization of information》（一种信息组织算法）。 // //3. 平衡因子（Balance Factor）的设计与作用 //- 定义：每个结点的平衡因子 = 该结点右子树的高度 - 左子树的高度； //- 取值范围：由于AVL树的高度差约束，任何结点的平衡因子只能是 0、1 或 - 1； //- 核心作用：AVL树本身不「必须」依赖平衡因子，但平衡因子如同「平衡风向标」： //✅ 直观反映当前结点的子树高度平衡状态； //✅ 简化平衡检测与调整的逻辑（无需额外遍历子树计算高度差）； //✅ 是实现AVL树旋转（左旋 / 右旋）调整平衡的核心判断依据。 // //4. 高度差约束为「≤1」而非「 = 0」的原因 //- 看似「高度差 = 0」是更完美的平衡，但实际场景中无法实现全局强制为0： //例1：仅含2个结点的AVL树（根结点 + 左 / 右子结点）： //根结点的左子树高度为1，右子树高度为0（或反之），高度差 = 1，无法做到0； //例2：含4个结点的AVL树（如根→左→左，根→右）： //根结点左子树高度为2，右子树高度为1，高度差 = 1，同样无法做到0； //- 结论：「高度差≤1」是兼顾可行性与平衡性的最优设计，而非刻意放宽条件。 // //5. AVL树的结构与性能优势 //- 结点分布特征：AVL树的整体结点数量和分布规律与完全二叉树高度相似； //- 高度控制：完全二叉树的高度为⌊log₂n⌋ + 1（n为结点数），AVL树高度可稳定控制在O(log₂n)级别； //- 效率提升： //✅ 普通二叉搜索树最坏情况（如退化为链表）：增删查改效率为O(n)； //✅ AVL树因高度可控，增删查改操作的时间复杂度均稳定在O(logn)，实现了本质性的效率提升。 //======================================== //那么对于AVL树的了解知道这些也就够了 //下面就去实现一下AVL树，不过先说明一下，我们就实现find，insert就够了，至于erase删除 //没什么必要学习，因为数据结构又不是徒手造轮子，再加上面试很少会问到AVL树的删除 //所以就可以不用去学习AVL树的删除，学习了插入insert就够了 //那么很显然，我们要先构建AVL树的节点，那么我们知道，AVL树的本质就是一棵二叉搜索树 //所以，节点里肯定要有左、右指针，然后就是key值和value值，因为我们实现的要高级一点 //所以就选择key-value型来进行实现。 //那么上面这些都是二叉搜索树有的，而AVL树这个自平衡的树，要有什么呢？ //首先最重要的就是平衡因子，即节点的右子树高度减去左子树的高度 //这个非常重要，AVL树的自平衡，就是依靠它，但是有它还不够 //因为我们知道，每个节点都有平衡因子，而当我们插入一个节点时 //是不是插入节点所在的那棵子树的根节点的平衡因子会发生变化，是的，就是会变化 //那么，想想看，插入节点所在的那棵子树的根节点的平衡因子会发生变化 //那么插入节点所在的那棵子树的根节点所在的那棵子树的根节点平衡因子，是不是也会发生变化 //以此类推，想想看，我们要怎么去修改上面所说的一堆根节点的平衡因子呢？？？？？ //那么首先就是肯定要能先找到那一堆根节点，不然谈何修改！！！ //而怎么找到的，再想想看，所谓的根节点，是不是就是它孩子的parent！！！！！ //插入节点所在的那棵子树的根节点，不就是新插入节点的parent吗！！！ //所以，在AVL树中的节点中，我们还得再创建parent指针，指向节点的parent！！！ //那么上面所说的这些就是AVL树的节点所应该有的成员变量!!! //由于树是很抽象的概念，必须结合着图来讲，而代码中无法结合图 //所以我就直接进行分析，然后说结论，我们没必要去理解说，为什么要这么做，为什么这么做可以 //这是天才，对于我们，只需要去知道，应该怎么做，这，就够了！！！ //所以，知道一定的原因，然后直接记住结论即可，当然，也得会画图，哈哈哈 namespace AVLTreeModule//来个命名空间域 { //AVL树的节点类,记得是模版类哦 template <typename K, typename V> struct AVLTreeNode { pair<K, V> _kv;//前面在使用set和map的时候，已经知道pair这个结构体了 //pair->first一般是key，pair->second一般是value，我们这里直接使用pair结构体就行了 AVLTreeNode<K, V>* _left = nullptr;//指向左孩子的指针 AVLTreeNode<K, V>* _right = nullptr;//指向右孩子的指针 AVLTreeNode<K, V>* _parent = nullptr;//指向父节点的指针 int _bf = 0;//平衡因子 balance factor //构造函数 //节点肯定得有构造函数，不难怎么传入key值和value值 AVLTreeNode(const pair<K, V> kv) :_kv(kv) , _bf(0) , _left(nullptr) , _right(nullptr) , _parent(nullptr) { //无内容 } }; //接下来就是AVLTree类了，即整颗树的类 //因为会插入数据，所以也得是模版类 template <typename K, typename V> class AVLTree { public: //重命名：using 别名 = 原类型; using node = AVLTreeNode<K, V>;//进行重命名,记得显式实例化 //== typedef AVLTreeNode<K, V> node typedef 原类型 别名; //编译器自动生成的二叉搜索树类的无参构造函数就够用了 //但是由于我们下面写了拷贝构造函数，所以编译器就不帮我们生成构造函数了 //所以我们可以用default强制执行 AVLTree() = default; //实现二叉搜索树类的拷贝构造函数 AVLTree(const AVLTree<K, V>& a) { //得去将传过来的二叉搜索树的节点一个一个插入this //用到前序遍历去进行插入 this->_root = copy(a._root); } //实现二叉搜索树类的=运算符重载函数 AVLTree<K, V>& operator=(const AVLTree<K, V>& b) { //现代写法直接秒 AVLTree<K, V> temp(b); std::swap(this->_root, temp._root); return *this;//连续赋值 } //实现二叉搜索树类的析构函数 ~AVLTree() { //使用后序遍历进行释放节点 destroy(_root);//直接利用我们下面写的destory函数进行释放节点 _root = nullptr; } //AVL树的重点：插入节点 //那么在该函数中，我们不仅要有平衡因子的更新 //更要有在某个根节点的平衡因子的绝对值超过1之后 //按照相对应的情况进行左旋（RR型），右旋（LL型），左右双旋（LR型），右左双旋（RL型） //1.首先按照二叉搜索树的规则插入目标值； //2.新增结点后，仅会影响其祖先结点的高度，进而可能改变部分祖先结点的平衡因子， //因此需要更新从新增结点到根结点路径上所有结点的平衡因子 //（实际场景中最坏情况需更新至根结点，部分情况更新到中间结点即可停止，具体情况后续详细分析）； //3.若更新平衡因子的过程中未出现失衡情况，则插入操作直接结束； //4.若更新过程中出现子树不平衡的情况，需对该失衡子树进行旋转调整， //旋转操作在恢复子树平衡的同时，本质上会降低该子树的高度， //使其不再对上层结点造成影响，此时插入操作也随之结束 bool Insert(const pair<K, V> data) { node* cur = _root;//定义cur指针，最终指向要插入到的节点为止 node* parent = nullptr;//定义parent指针，代表cur的父节点 //newnode->_kv = data; //新节点的左右指针不用管，因为我们已经默认给它们nullptr了 if (_root == nullptr)//如果是一棵空树，那么直接把新节点设置为整棵树的根节点即可 { //在确定了要插入之后，再去new node* newnode = new node(data);//新节点，直接构造就完事了 _root = newnode; return true; } else//不是空树 { while (cur != nullptr) { if (cur->_kv.first < data.first)//比较key值 { //那就让cur指针往它的右子树去 parent = cur; cur = cur->_right; } else if (cur->_kv.first > data.first) { //那就让cur指针往它的左子树去 parent = cur; cur = cur->_left; } else if (cur->_kv.first == data.first) { return false; } } //出了循环之后，cur指向nullptr，也是它要在的位置， //而parent指向新插入节点最终在AVL树中的位置的父节点 //比较parent节点和要插入数据key值 //然后根据比较结果进行插入 if (parent->_kv.first > data.first) { cur = new node(data);//新节点，直接构造就完事了，把它给cur指针 parent->_left = cur;//放入parent的左孩子 } else if (parent->_kv.first < data.first) { cur = new node(data);//新节点，直接构造就完事了，把它给cur指针 parent->_right = cur;//放入parent的右孩子 } else { assert(false);//其实压根不会出现这个情况，但是为了彰显我们的专业性，所以随便加上 } } cur->_parent = parent;//把新节点里的父节点指针更新为parent //因为parent指向新插入节点最终在AVL树中的位置的父节点 while (parent!= nullptr)//只要节点不为空，那么就一直循环下去，直到碰到终止条件 { //然后就是对平衡因子的更新了 //其实更新思路还是很简单的，那么我们知道， //节点的平衡因子就是节点的右子树高度减去左子树高度 //所以，对于新插入节点所在的子树的根节点的平衡因子，是怎么改呢？ //其实就是如果新插入节点是新插入节点所在的子树的根节点的左孩子的话 //那么新插入节点所在的子树的根节点的平衡因子就是--， //因为左子树高度加一，而右子树高度不变， //所以新的节点的右子树高度减去左子树高度的结果就是之前结果-1，自己计算一下就明白了 //如果新插入节点是新插入节点所在的子树的根节点的右孩子的话 //那么新插入节点所在的子树的根节点的平衡因子就是++， //因为左子树高度不变，而右子树高度+1， //所以新的节点的右子树高度减去左子树高度的结果就是之前结果+1，自己计算一下就明白了 //这个还是很好理解的 //而新节点的平衡因子肯定是0啦 if (cur == parent->_left) { --parent->_bf; } else if (cur == parent->_right) { ++parent->_bf; } else { assert(false); } //仅仅只是更新新插入结点的父节点的平衡因子还不够，因为还有一些情况需要考虑 //1.新插入的节点的父节点的平衡因子要是更新后变成1或者-1 //那就说明是从原本的0变成1或者-1，也就是说这个根节点的左右子树从原本的一样高，变成有一边变高 //那么这个新插入结点的父节点的左右子树发生这个变化， //而这个新插入结点的父节点的父节点的左右子树难道不会也发生这个变化吗？？？？？？ //会，会发生这个变化，自己画个图就明白了，这个要知道 //所以，这个新插入结点的父节点的父节点的平衡因子要不要也发生变化？？？ //要！！！！！！！！！！！！ //怎么变？是++还是--？？？？ //我们需要明白 //祖父节点的bf变化，只取决于“父节点是祖父节点的左孩子/右孩子”，和父节点自己的bf值无关。 //有的人可能想着说，哦我知道 //如果这个新插入结点的父节点的平衡因子是变为-1， //那么这个新插入结点的父节点的父节点的平衡因子得--！！！ //如果这个新插入结点的父节点的平衡因子是变为1， //那么这个新插入结点的父节点的父节点的平衡因子得++！！ //那么这个是对的吗？？？对个蛋！！！这个是大错特错的！！！ //我们要知道，某个节点的平衡因子的变化是代表说在它这个节点的左右子树中 //左子树或者右子树的高度有所变化，要严格注意：是针对于这个节点的左右子树 //比如说某个节点的平衡因子变为1，那么就代表说这个节点的右子树比左子树高一层 //那么按照上面的说法就得这个节点的父节点的平衡因子进行++， //而这个的意思是代表说，这个节点的父节点的右子树比左子树高一层 //可是问题是，谁说新插入的节点就是在这个节点的父节点的右子数树部分呢？？？ //难道不可能在左子树部分吗？？？当然可能，那么是在左子树部分的话 //就是左子树高了一层，那么这个节点的父节点能++吗？？？不应该是--吗？？？ //所以，上面的想法是大错特错的！！！ //所以，应该怎么去判断，怎么去更新呢？？？ //首先，我们需要知道，当插入一个新节点之后，那么就是代表说这个新节点的父节点的左子树或者右子树高了一层 //也就是说，这个新节点的父节点的这一棵子树的高度是高了一层的（平衡因子变为1或者-1的情况） //那么我们怎么知道这个新节点的父节点的父节点的平衡因子应该++还是--呢？？ //其实就是看这个新节点的父节点的父节点是它的左子树高了一层还是右子树高了一层呢？？ //即看这个新节点是插在它的左子树部分还是右子树部分 //那么其实也就是看这个新节点的父节点是这个新节点的父节点的父节点的左孩子还是右孩子 //是左孩子的话，就说明是这个新节点的父节点的父节点是它的左子树高了一层，也就是该节点的平衡因子要-- //是右孩子的话，就说明是这个新节点的父节点的父节点是它的右子树高了一层，也就是该节点的平衡因子要++ //一定要理解这个新节点的父节点的这一棵子树的高度是高了一层的（平衡因子变为1或者-1的情况） //总结一下：向上更新平衡因子时： //若当前节点是其父节点的左孩子 → 父节点的 bf--（因为左子树高度 + 1）； //若当前节点是其父节点的右孩子 → 父节点的 bf++（因为右子树高度 + 1）。 //（当前节点的 bf 值仅用于判断 “是否继续向上更新”，而非 “父节点 bf 的变化方向”。） //并且，要一直类推下去，如果这个新插入结点的父节点的父节点的平衡因子更新变为1或者-1 //那么这个新插入结点的父节点的父节点的父节点的平衡因子也得发生变化，就按照上面说的变化 //那如果从新插入节点的父节点一直到最上面一层的根节点的平衡因子都随之更新为1或者-1 //我们什么时候终止呢？？？这个变为-1或者1的更新呢？？ //就是当节点的_parent变为nullptr，因为最上面一层的根节点的_parent就是nullptr //那么这是新插入节点的父节点一直到最上面一层的根节点的平衡因子都随之更新为1或者-1的情况 //2.还有一种情况是父（根）节点的平衡因子更新后变为0了，那么这说明什么？？？ //这就说明，原本该父（根）节点是左右子树中有一个比较高一层 //而当你新插入了节点之后，它的左右子树变成一样高了，那么，这不就是最佳形态吗？？？ //那么再想想，此时这个父节点的父节点的平衡因子还需要更新吗？？？ //不用，因为你这个父节点的左右子树都一样高了，那么你的父节点的右左子树高度差就是和之前一样 //还是那句话，自己画图理解 //3.父节点的平衡因子更新变为2或者-2了，那么这就说明此时的树违反了AVL树的规则，所以就需要旋转 //至于怎么旋转，下面再说 //那么在这里说明一下，2,3种情况可能发生在第一种情况中的不断更新中，这是有可能的 //比如原本新插入节点的父节点有一个右孩子，而你新插入的节点插入在了它的左孩子 //而对于直接更新的新插入节点的父节点，它的平衡因子可能会变为0，也就是第二种情况 //但是绝对不可能变为2或者-2，即第3种情况 //为什么？？？？？ //新节点是父节点的 “直接叶子孩子”， //（因为cur是一直找，直到为nullptr为止，也就是说明它的父节点的这一侧子树是为空的，即高度为0） //cur 就像一个 “找房跑腿的”，parent 是它刚离开的 “上一个节点”； //我们要插新节点，得按二叉搜索树的规矩来（小的往左、大的往右）， //让 cur 一路找 “空房间”—— 只要 cur 能走到某个子节点（不是空）， //说明这个位置被占了，就继续往前走； //直到 cur 走到 “死胡同”（变成 nullptr）， //意思就是：cur 想往 parent 的某一侧（左 / 右）走， //但这一侧根本没有子节点（是空的），所以走不动了； //既然这一侧是空的，那按照 AVL 树的规则，“空的子树” 高度就是 0—— //这就是说的 “父节点的这一侧子树为空，即高度为 0”。 //插入前父节点的左右子树高度差最多为 1（AVL 合法状态）， //而新节点仅让父节点的某一侧子树高度从 0→1， //相当于 “补全” 了父节点的单侧子树 —— //这种变化最多让父节点的 BF 从±1变回0，或从0变成±1，不可能让高度差突破 1， //因此 BF 绝不可能到±2。 //只有当更新传递到祖父及以上的祖先节点时，才有可能出现 BF = ±2（失衡）。 //比如：父节点 BF 更新为±1后，继续向上更新祖父节点的 BF， //而祖父节点原本的 BF 已经是±1，叠加后才会变成±2 //但新节点的直接父节点，永远不会出现这种情况。 //那么这就是平衡因子更新的思路 //更新原则： //• 平衡因子 = 右子树高度 - 左子树高度 //• 只有子树高度变化才会影响当前结点平衡因子。 //• 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++， //新增结点在parent的左子树，parent平衡因子-- //• parent所在子树的高度是否变化决定了是否会继续往上更新 //更新停止条件： //• 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为 - 1->0 或者 1->0， //说明更新前parent子树一边高一边低，新增的结点插入在低的那边， //插入后parent所在的子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。 //• 更新后parent的平衡因子等于1 或 - 1，更新前更新中parent的平衡因子变化为0->1 或者 0-> - 1， //说明更新前parent子树两边一样高，新增的插入结点后，parent所在的子树一边高一边低， //parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子， //所以要继续向上更新。 //• 更新后parent的平衡因子等于2 或 - 2，更新前更新中parent的平衡因子变化为1->2 或者 - 1-> - 2， //说明更新前parent子树一边高一边低，新增的插入结点在高的那边， //parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求， //需要旋转处理，旋转的目标有两个：1、把parent子树旋转平衡。 //2、降低parent子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束。 //• 不断更新，更新到根，根的平衡因子是1或 - 1也停止了。 //不断向上更新，直到向上有父节点的平衡因子变为0 //或者有父节点的平衡因子变为2或者-2 //又或者是更新到最上面的根节点 //要是更新后的parent的平衡因子变为0了，那么可以终止循环 if (parent->_bf == 0) { break; } else if (parent->_bf == -1 || parent->_bf == 1) { cur = parent; parent = cur->_parent; //将cur节点和parent节点都往上移一个节点 //然后就可以不用操作了 //因为在该循环前面已经有了 //if (cur == parent->_left) //{ // --parent->_bf; //} //else if (cur == parent->_right) //{ // ++parent->_bf; //} //这个就会去进行判断与平衡因子的处理 //所以在本条件里，只需要进行节点向上更新 //之所以要将parent更新为它的父节点，因为我们循环的条件就是设置为parent不为空 } //要是更新后的parent的平衡因子变为2或者-2了，那么就得进行旋转 //此时的parent就是失衡节点了 else if (parent->_bf == -2 || parent->_bf == 2) { //按照不同情况进行不同的旋转 //第一种情况：LL型，即新插入节点在失衡节点的左孩子的左子树中 //进行右单旋 //那么怎么判断是LL型呢？？？ //其实很简单，首先我们知道失衡节点的平衡因子一定是2或者-2的 //而由于新插入节点在失衡节点的左孩子的左子树中 //所以也就是说失衡节点的左子树高度会高于失衡节点的右子树 //所以它的平衡因子就是-2 //那么有这个还不够，怎么判断新插入节点在失衡节点的左孩子的左子树中 //我们又知道失衡节点的左孩子的平衡因子一定是1或者 -1的 //因为是在左孩子的左子树中 //那么就说明失衡节点的左孩子的左右子树中，左子树的高度是高于右子树一层的 //那么也就说明失衡节点的左孩子的平衡因子是-1 //以上皆可以通过画图得出，所以自行理解 //所以由这两个条件就可以准确判断出来了 if (parent->_bf == -2 && parent->_left->_bf == -1) { RotateR(parent); } //第二种情况：RR型，即新插入节点在失衡节点的右孩子的右子树中 //进行左单旋 //那么怎么判断是RR型呢？？？ //其实很简单，首先我们知道失衡节点的平衡因子一定是2或者-2的 //而由于新插入节点在失衡节点的右孩子的右子树中 //所以也就是说失衡节点的右子树高度会高于失衡节点的左子树 //所以它的平衡因子就是2 //那么有这个还不够，怎么判断新插入节点在失衡节点的右孩子的右子树中 //我们又知道失衡节点的右孩子的平衡因子一定是1或者 -1的 //因为是在右孩子的右子树中 //那么就说明失衡节点的右孩子的左右子树中，右子树的高度是高于左子树一层的 //那么也就说明失衡节点的右孩子的平衡因子是1 //以上皆可以通过画图得出，所以自行理解 //所以由这两个条件就可以准确判断出来了 else if (parent->_bf == 2 && parent->_right->_bf == 1) { RotateL(parent); } //第三种情况：LR型，即新插入节点在失衡节点的左孩子的右子树中 //进行左右双旋 //那么依旧是怎么判断呢？？？ //其实和上面的判断思路是一样的 //重点还是抓住新插入节点在失衡节点的左孩子的右子树中 //那么有了上面的经验，这里就可以很简单的看出来 //就是失衡节点的平衡因子是-2 //而失衡节点的左孩子的平衡因子则是1 //其实很简单，首先我们知道失衡节点的平衡因子一定是2或者-2的 //而由于新插入节点在失衡节点的左孩子的右子树中 //所以也就是说失衡节点的左子树高度会高于失衡节点的右子树 //所以它的平衡因子就是-2 //那么有这个还不够，怎么判断新插入节点在失衡节点的左孩子的右子树中 //我们又知道失衡节点的左孩子的平衡因子一定是1或者 -1的 //因为是在左孩子的右子树中 //那么就说明失衡节点的左孩子的左右子树中，右子树的高度是高于左子树一层的 //那么也就说明失衡节点的左孩子的平衡因子是1 //以上皆可以通过画图得出，所以自行理解 //所以由这两个条件就可以准确判断出来了 else if (parent->_bf == -2 && parent->_left->_bf == 1) { RotateLR(parent); } //第四种情况：RL型，即新插入节点在失衡节点的右孩子的左子树中 //进行右左双旋 //那么依旧是怎么判断呢？？？ //其实和上面的判断思路是一样的 //重点还是抓住新插入节点在失衡节点的右孩子的左子树中 //那么有了上面的经验，这里就可以很简单的看出来 //就是失衡节点的平衡因子是2 //而失衡节点的右孩子的平衡因子则是-1 // 修正：左孩子→右孩子 //其实很简单，首先我们知道失衡节点的平衡因子一定是2或者-2的 //而由于新插入节点在失衡节点的右孩子的左子树中 //所以也就是说失衡节点的右子树高度会高于失衡节点的左子树 //所以它的平衡因子就是2 //那么有这个还不够，怎么判断新插入节点在失衡节点的右孩子的左子树中 //我们又知道失衡节点的右孩子的平衡因子一定是1或者 -1的 // 修正：左孩子→右孩子 //因为是在右孩子的左子树中 //那么就说明失衡节点的右孩子的左右子树中，左子树的高度是高于右子树一层的 // 补充：明确“右孩子” //那么也就说明失衡节点的右孩子的平衡因子是-1 // 修正：左孩子→右孩子 //以上皆可以通过画图得出，所以自行理解 //所以由这两个条件就可以准确判断出来了 else if (parent->_bf == 2 && parent->_right->_bf == -1) { RotateRL(parent); } else { assert(false); } //旋转完后树也就恢复平衡了，不用再更新，直接break break; } } //能退出循环也就是代表说插入搞定了 return true; } //AVL树删除函数，这个就不写了 void erase() { //无内容 } //实现AVL树的查找功能，其实和二叉搜索树的查找功能实现方法一样 //这个其实就是真的很简单了 //就是看要查找的值有没有在二叉搜索树里面， //那么先设置一个指针cur，然后按照二叉搜索树的性质去进行cur的移动 //如果要查找的值大于cur的话 //cur就进入它的右子树，要是要查找的值小于cur的话，cur就进入它的左子树 //重复上面操作不断比较，直到cur移动到值与要查找的值相同的节点，代表找到 //或者cur运动到nullptr，此时就代表cur无路可去，即没找到 bool Find(const K& k)//设置返回值为bool，判断是否找到 { node* cur = _root;//从整棵树的最上面的根节点开始寻找 while (cur != nullptr) { if (k < cur->_kv.first) { cur = cur->_left; } else if (k > cur->_kv.first) { cur = cur->_right; } else//即相等了，代表找到 { return true; } } return false;//出了循环就代表没找到 } //也可以重载返回找到节点的find函数，可通过节点访问对应的value node* Find_Node(const K& k) { node* cur = _root;//从整棵树的最上面的根节点开始寻找 while (cur != nullptr) { if (k < cur->_kv.first) { cur = cur->_left; } else if (k > cur->_kv.first) { cur = cur->_right; } else//即相等了，代表找到 { return cur; } } return nullptr;//出了循环就代表没找到 } //中序遍历，证明二叉搜索树的有序性 void InOrder() const { //直接调用我们已经封装好的中序遍历就行，传入根节点指针 _inorder(_root); } bool IsBalanceTree() { //直接调用我们已经封装好的检测函数就行，传入根节点指针 return _IsBalanceTree(_root); } int Height() { return _AVLTreeHeight(_root); } private: //先来个中序遍历，证明二叉搜索树的有序性 //同样记得是封装一个不用传入根节点的中序遍历函数出来 void _inorder(const node* root) const { if (root == nullptr) { return; } //中序遍历：左子树，根节点，右子树 _inorder(root->_left); cout << "key值：" << root->_kv.first << "value值：" << root->_kv.second << endl; _inorder(root->_right); } void destroy(node*& root) { if (root == nullptr) { return; } //使用后序遍历 destroy(root->_left); destroy(root->_right); delete root; //最后要将root置为空指针，避免成为野指针 //那么这也就要求我们要把形参设置为引用 root = nullptr; } node* copy(const node* root, node* parent = nullptr)// 新增 parent 参数，传递父节点 { if (root == nullptr) { return nullptr; } // 1. 复制原节点的 _kv 和 _bf node* newroot = new node({ root->_kv.first, root->_kv.second }); newroot->_bf = root->_bf; // 复制平衡因子 newroot->_parent = parent; // 设置父节点指针 // 2. 递归复制左/右子树，传递当前 newroot 作为子节点的父节点 newroot->_left = copy(root->_left, newroot); newroot->_right = copy(root->_right, newroot); return newroot; } //获取到树的高度的函数，其实很简单，之前就已经实现过了 //本质是使用后序遍历，找根节点中左子树和右子树中较大的那一个+1 //补充：空树高度为0，叶子节点高度为1（符合AVL树节点高度定义） int _AVLTreeHeight(node* root) { if (root == nullptr) { return 0; } int leftheight = _AVLTreeHeight(root->_left); int rightheight = _AVLTreeHeight(root->_right); //return (leftheight > rightheight ? leftheight + 1 : rightheight + 1); return max(leftheight, rightheight) + 1; } //第一种情况：LL型，即新插入节点在失衡节点的左孩子的左子树中 //进行右单旋 void RotateR(node* parent) { assert(parent);//检验是否传入空指针 assert(parent->_left && "LL型失衡节点无左孩子！"); //其实说实话，针对什么情况，是要怎么旋 //旋的过程是什么样的，其实不好直接说，必须得结合着图像来，或者自己脑子里就得有个图出来 //这样子才能手撕AVL树，当然，这得多练多看 //那么进行右单旋的原因就是新节点插入在了失衡节点的左孩子的左子树中 //注意，失衡节点就是指某个平衡因子为2或者-2的节点 //自己脑子里想个图就完事了，直接文字不好说 //就按照上面说的新节点插入在了失衡节点的左孩子的左子树中去进行思考 //所以我们就右单旋，怎么单旋？？？ //记住结论：将失衡节点进行右单旋，并且无论失衡节点的左孩子的右孩子为不为空 //（即无论该节点为不为nullptr） //都得把该孩子纳为失衡节点的左孩子（最终的平衡的树） //而要是该孩子不为nullptr的话，那么得把该孩子的parent进行更新，换为失衡节点 //然后将失衡节点的左孩子的右孩子修改为失衡节点 //那么在最后失衡节点的左孩子会变为原本的失衡节点的整颗子树的新的根节点 //所以要判断原本的失衡节点是不是整棵树的根节点 //是的话,那么就把整棵树的root赋值为失衡节点的左孩子 //不是的话，那么就看原本的失衡节点是它的父节点的左孩子还是右孩子，所以得记录一下失衡节点的父节点 //对应哪一个孩子，就把失衡节点的父节点对应的孩子赋值为失衡节点的左孩子 //然后把失衡节点的左孩子的_parent指针修改为失衡节点的原本的父节点 //即parent->_parent; //无论失衡节点是不是最上面的根节点（是的话，不就是它的父节点为nullptr吗） //都可以进行这个操作 //最后把失衡节点的_parent指针修改为失衡节点的左孩子 //最后的最后把失衡节点和失衡节点的左孩子的平衡因子都修改为0 //因为旋转后的树，就是平衡的，而失衡节点和失衡节点的左孩子的平衡因子都会为0 //直接记住这个结论，然后脑子里有图，那么把代码写出来也就不难了 //所以按照上面的结论，我们需要哪些节点？？？ //需要知道，失衡节点已经由外界传入该函数，即该函数的形参 //1.失衡节点 2.失衡节点的左孩子 3.失衡节点的左孩子的右孩子 // parent subl sublr //OK，然后我们就能按照上面的结论去结合着图写出代码 //失衡节点是该函数的参数，由外界传入 node* subl = parent->_left; node* sublr = parent->_left->_right; //无论失衡节点的左孩子的右孩子为不为空 //（即无论该节点为不为nullptr） //都得把该孩子纳为失衡节点的左孩子（最终的平衡的树） //而要是该孩子不为nullptr的话，那么得把该孩子的parent进行更新，换为失衡节点 parent->_left = sublr; if (sublr != nullptr) { //同时把失衡节点的左孩子的右孩子的_parent指针进行更新 sublr->_parent = parent; } //然后将失衡节点的左孩子的右孩子修改为失衡节点 subl->_right = parent; //那么在最后失衡节点的左孩子会变为原本的失衡节点的整颗子树的新的根节点 //所以要判断原本的失衡节点是不是整棵树的根节点 //是的话,那么就把整棵树的root赋值为失衡节点的左孩子 //不是的话，那么就看原本的失衡节点是它的父节点的左孩子还是右孩子，所以得记录一下失衡节点的父节点 //对应哪一个孩子，就把失衡节点的父节点对应的孩子赋值为失衡节点的左孩子 //记录失衡节点的原本的父节点 node* parentparent = parent->_parent; if (parent == _root) { _root = subl; } else { if (parent == parentparent->_left) { parentparent->_left = subl; } else if (parent == parentparent->_right) { parentparent->_right = subl; } } //然后把失衡节点的左孩子的_parent指针修改为失衡节点的原本的父节点 //即parent->_parent; //无论失衡节点是不是最上面的根节点（是的话，不就是它的父节点为nullptr吗） //都可以进行这个操作 subl->_parent = parentparent; //最后把失衡节点的_parent指针修改为失衡节点的左孩子 parent->_parent = subl; //最后的最后把失衡节点和失衡节点的左孩子的平衡因子都修改为0 //因为旋转后的树，就是平衡的，而失衡节点和失衡节点的左孩子的平衡因子都会为0 parent->_bf = 0; subl->_bf = 0; } //第二种情况：RR型，即新插入节点在失衡节点的右孩子的右子树中 //进行左单旋 void RotateL(node* parent) { assert(parent);//检验是否传入空指针 assert(parent->_right); // 补充：RR型左单旋必须保证失衡节点有右孩子 //其实说实话，针对什么情况，是要怎么旋 //旋的过程是什么样的，其实不好直接说，必须得结合着图像来，或者自己脑子里就得有个图出来 //这样子才能手撕AVL树，当然，这得多练多看 //那么进行左单旋的原因就是新节点插入在了失衡节点的右孩子的右子树中 //注意，失衡节点就是指某个平衡因子为2或者-2的节点 //自己脑子里想个图就完事了，直接文字不好说 //就按照上面说的新节点插入在了失衡节点的右孩子的右子树中去进行思考 //所以我们就左单旋，怎么单旋？？？ //其实和右单旋几乎是一模一样 // 第二种情况：RR型，即新插入节点在失衡节点的右孩子的右子树中 → 进行左单旋 // 左单旋核心逻辑（与右单旋完全对称）： // 1. 无论失衡节点（parent）的右孩子（subr）的左孩子（subrl）是否为空，都将其挂载为parent的右孩子； // 2. 若subrl非空，更新其_parent为parent； // 3. 将parent挂载为subr的左孩子； // 4. subr成为原失衡子树的新根： // - 若parent是整树根节点 → 整树根节点更新为subr； // - 若parent不是根 → 看parent是其祖父节点（parentparent）的左/右孩子，将parentparent对应孩子改为subr； // 5. 更新subr的_parent为parentparent（无论parent是否为根，此操作均有效）； // 6. 更新parent的_parent为subr； // 7. 旋转后parent和subr的平衡因子均重置为0（RR型插入失衡场景下）； //所以按照上面的结论，我们需要哪些节点？？？ //需要知道，失衡节点已经由外界传入该函数，即该函数的形参 //1.失衡节点 2.失衡节点的右孩子 3.失衡节点的右孩子的左孩子 // parent subr subrl //OK，然后我们就能按照上面的结论去结合着图写出代码 //失衡节点是该函数的参数，由外界传入 node* subr = parent->_right; node* subrl = parent->_right->_left; //无论失衡节点的右孩子的左孩子为不为空 //（即无论该节点为不为nullptr） //都得把该孩子纳为失衡节点的右孩子（最终的平衡的树） //而要是该孩子不为nullptr的话，那么得把该孩子的parent进行更新，换为失衡节点 parent->_right = subrl; if (subrl != nullptr) { //同时把失衡节点的右孩子的左孩子的_parent指针进行更新 subrl->_parent = parent; } //然后将失衡节点的右孩子的左孩子修改为失衡节点 subr->_left = parent; //那么在最后失衡节点的右孩子会变为原本的失衡节点的整颗子树的新的根节点 //所以要判断原本的失衡节点是不是整棵树的根节点 //是的话,那么就把整棵树的root赋值为失衡节点的右孩子 //不是的话，那么就看原本的失衡节点是它的父节点的左孩子还是右孩子，所以得记录一下失衡节点的父节点 //对应哪一个孩子，就把失衡节点的父节点对应的孩子赋值为失衡节点的右孩子 //记录失衡节点的原本的父节点 node* parentparent = parent->_parent; if (parent == _root) { _root = subr; } else { if (parent == parentparent->_left) { parentparent->_left = subr; } else if (parent == parentparent->_right) { parentparent->_right = subr; } } //然后把失衡节点的右孩子的_parent指针修改为失衡节点的原本的父节点 //即parent->_parent; //无论失衡节点是不是最上面的根节点（是的话，不就是它的父节点为nullptr吗） //都可以进行这个操作 subr->_parent = parentparent; //最后把失衡节点的_parent指针修改为失衡节点的右孩子 parent->_parent = subr; //最后的最后把失衡节点和失衡节点的右孩子的平衡因子都修改为0 //因为旋转后的树，就是平衡的，而失衡节点和失衡节点的右孩子的平衡因子都会为0 parent->_bf = 0; subr->_bf = 0; } //第三种情况：LR型，即新插入节点在失衡节点的左孩子的右子树中 //进行左右双旋 void RotateLR(node* parent) { assert(parent); assert(parent->_left); //那么对于LR型，即新插入节点在失衡节点的左孩子的右子树中 //其实处理起来还是比较麻烦的 //主要是麻烦在平衡因子的处理 //至于旋转其实很简单，先左单旋，再右单旋即可 //依旧是直接记住结论 //先左单旋失衡节点的左孩子，再右单旋失衡节点即可 //不用知道为什么，记住就行了 //非要知道什么的话，原理就是先经过一次左单旋转使得LR型变为LL型 //那么一旦变为LL型了，就可以使用右单旋使得树变平衡 //先获取到需要的节点 node* subl = parent->_left; node* sublr = parent->_left->_right; int sublrbf = sublr->_bf;//记录失衡节点的左孩子的右孩子的平衡因子 //为什么要记录，下面➡有说 RotateL(subl); RotateR(parent); //最后就是重头戏平衡因子的处理了 //因为对于LR型，有三种情况： //1.失衡节点的左孩子的左右子树以及失衡节点的右子树都不是空的， //且新插入节点是在失衡节点的左孩子的右子树中的左子树 //即新插入节点是在失衡节点的左孩子的右孩子的左子树 //2.失衡节点的左孩子的左右子树以及失衡节点的右子树都不是空的， //且新插入节点是在失衡节点的左孩子的右子树中的右子树 //即新插入节点是在失衡节点的左孩子的右孩子的右子树 //3.失衡节点的左孩子的左右子树以及失衡节点的右子树原本都是空的， //新插入节点直接是插入在了失衡节点的左孩子的右子树中 //即新插入节点是在失衡节点的左孩子的右孩子 //那么对于这三种情况，得进行不同的平衡因子的处理 //所以，首当其冲的就是，怎么去判断是这三种情况的哪一种情况？？？ //其实啊，本质的本质，依旧是画图，树，就必须要去画图 //所以在这里，我们依旧是直接给结论 //针对第一种情况，那么它就是插入了在失衡节点的左孩子的右孩子中的左子树 //想想看，那么对于失衡节点的左孩子的右孩子，它的平衡因子应该是多少？？？ //其实很显然，应该是-1，因为它的右子树比左子树低一层啊！！！！ //而第二种情况呢？？？且新插入节点是在失衡节点的左孩子的右子树中的右子树 //很显然，是1，因为它的右子树比左子树高一层啊！！！！ //那么最后的第三种情况呢？？？？？ //别忘了，按照上面的情况，新插入节点就是失衡节点的左孩子的右孩子啊，其他的都没有了 //所以它的平衡因子就是0， //所以，我们要判断三种情况，本质上就是判断失衡节点的左孩子的右孩子的平衡因子 //然后就是，针对这三种情况，我们要怎么更新平衡因子呢？？？ //首先我们要先知道这三种情况更新平衡因子的相同点 //那么我们就要知道，当最后平衡的时候，失衡节点的左孩子的右孩子会变为新子树的根节点 //所以就是，失衡节点的左孩子的右孩子的平衡因子最后会变为0 //那么这就是三种情况的相同点 //随后就是不同点，那么同样也是要结合着图像进行理解，这里就简单分析一下 //我们知道，无论是左旋还是右旋，都会把被旋转的节点过程中碰到的左/右孩子纳为己用 //那么知道这一点，就可以知道很多了 //那么再根据我们上面旋转的方法以及顺序 //我们是先左旋失衡节点的左孩子，然后再右旋失衡节点 //那么在失衡节点左孩子左旋的过程中， //想想，它是不是会把它所碰到的失衡节点的左孩子的右孩子的左子树纳为己用（如果存在的话） //而在失衡节点右旋的过程中， //它是不是会把它所碰到的失衡节点的左孩子的右孩子的右子树纳为己用（如果存在的话） //所以，知道这两点，就是判断平衡因子的关键所在了 //而对于第一种情况，即新插入节点在失衡节点的左孩子的右孩子的左子树上 //那么再想想，我们假设失衡节点的左孩子的原本的左孩子（左子树）的高度是h //那么失衡节点的左孩子的右孩子的左子树和右子树的高度就都是h-1 //而当新插入节点在失衡节点的左孩子的右孩子的左子树上的时候，是不是 //失衡节点的左孩子的右孩子的左子树的高度是h，而右子树则还是h-1，这个很好理解 //那么我们前面说了， //在失衡节点左孩子左旋的过程中， //它会把它所碰到的失衡节点的左孩子的右孩子的左子树纳为己用（如果存在的话） //而在失衡节点右旋的过程中， //它会把它所碰到的失衡节点的左孩子的右孩子的右子树纳为己用（如果存在的话） //所以，最终的平衡的树，那么失衡节点的左孩子的左右子树就都会是h， // //即失衡节点的左孩子的平衡因子是0 // //而失衡节点的左子树的就是原本的失衡节点的左孩子的右孩子的右子树（h-1） //而失衡节点的右子树是和原本的一样的，即高度是h //为什么不是h+1呢？要是h+1的话，那么是不是原本的失衡节点的左右子树一样高 //那么在插入了新节点之后，怎么可能会失衡呢？？？ //再加上我们这是LR型，所以，原本的失衡节点的左子树比右子树高一层！！！ //回到上面，失衡节点的右子树高度为h， //而失衡节点左子树的就是原本的失衡节点的左孩子的右孩子的右子树（h-1） // //所以最终平衡的树的原本的失衡节点的平衡因子就是1！！！ // //以上是第一种情况 //不过知道了第一种情况的平衡因子的更新之后，第二种情况的平衡因子的更新其实就和第一种情况一样 //只不过是反了过来罢了 //AVL树 LR型失衡（左-右型）平衡因子更新 - 第二种情况 //核心场景：新插入节点在【失衡节点的左孩子的右子树的右子树】中 //关键判断依据：失衡节点左孩子的右孩子（简称mid节点）的平衡因子为1（右子树比左子树高1层） //逻辑衔接：与第一种情况（新节点在mid节点左子树）完全对称，类比理解即可 // 1. 核心节点定义（C++中通常用结构体指针表示树节点） // root: 失衡节点（平衡因子=2，左子树高度 > 右子树高度+1） // leftNode: root的左孩子（root->left） // midNode: leftNode的右孩子（leftNode->right，LR型失衡的中间枢纽节点） // 2. 高度假设体系 // 假设前提1：旋转前，leftNode原本的左子树高度为h； // 假设前提2：插入新节点前，midNode的左、右子树高度均为h-1（LR型失衡的初始结构基础）； // 插入后变化：新节点插入midNode的右子树 → midNode的右子树高度从h-1变为h，左子树仍为h-1； // 推导结论：midNode的平衡因子 = 右子树高度 - 左子树高度 = h - (h-1) = 1（这是第二种情况的核心判断条件）。 // 3. 旋转过程的“子树纳用”逻辑（LR型固定操作：先左旋leftNode，再右旋root） // ① 左旋leftNode时： // leftNode作为被旋转节点，会将midNode的左子树（高度h-1）“纳用”为自己的新右子树； // 原因：左旋的本质是将midNode提升为leftNode的父节点，leftNode成为midNode的左孩子， // 此时midNode原本的左子树需要挂载到leftNode的右子树（保持BST性质）。 // ② 右旋root时： // root作为被旋转节点，会将midNode的右子树（高度h，插入新节点后）“纳用”为自己的新左子树； // 原因：右旋的本质是将midNode提升为root的父节点，root成为midNode的右孩子， // 此时midNode原本的右子树需要挂载到root的左子树（保持BST性质）。 // 4. 平衡因子更新推导（核心：旋转后所有节点的左右子树高度差≤1） // ① midNode的平衡因子： // 旋转后midNode成为新的子树根节点，其左子树是leftNode（左右子树高度均为h）， // 右子树是root（左右子树高度均为h），因此midNode的平衡因子 = h - h = 0； // （与第一种情况一致，三种LR子情况的midNode最终平衡因子均为0） // ② leftNode的平衡因子： // 左旋后leftNode的左子树保持原高度h，右子树是“纳用”的midNode左子树（高度h-1）； // 最终leftNode的左右子树高度差 = h - (h-1) = 1？不，旋转后子树高度会重新校准： // 实际平衡后，leftNode的右子树高度会被调整为h（因为midNode的左子树挂载后，整体高度对齐）， // 因此leftNode的平衡因子 = h - h = 0；（与第一种情况的leftNode平衡因子结果对称） // ③ root的平衡因子： // 右旋后root的右子树保持原高度h（LR型失衡的前提：root左子树原本比右子树高1层）， // 左子树是“纳用”的midNode右子树（高度h）； // 最终root的左右子树高度差 = h - h = 0？不，结合LR型失衡的初始条件修正： // 初始时root的右子树高度为h，左子树（leftNode所在子树）高度为h+1（导致平衡因子=2）； // 旋转后root的左子树高度变为h（纳用midNode的右子树），右子树仍为h， // 因此root的平衡因子 = h - h = 0；（与第一种情况的root平衡因子=-1形成对称，核心差异源于新节点插入方向） // 5. 与第一种情况的核心异同（类比记忆，强化理解） // 相同点： // - 旋转操作顺序一致：先左旋leftNode，再右旋root； // - midNode最终平衡因子均为0； // - leftNode最终平衡因子均为0； // 不同点： // - 新节点插入方向：第一种在midNode左子树，第二种在midNode右子树； // - midNode初始平衡因子：第一种为-1，第二种为1； // - root最终平衡因子：第一种为-1，第二种为0；（对称差异的核心原因是“子树纳用”的来源不同） // 总结：LR型两种子情况（新节点在midNode左/右子树）的平衡因子更新，本质是“旋转导致的子树挂载方向对称”， // 结合第一种情况的逻辑，通过“方向反转”即可快速推导第二种情况，无需重复记忆复杂流程。 //然后就是第三种情况，那么这个其实就简单很多了 //这个情况是 //3.失衡节点的左孩子的左右子树以及失衡节点的右子树原本都是空的， //新插入节点直接是插入在了失衡节点的左孩子的右子树中 //即新插入节点是在失衡节点的左孩子的右孩子 //那么我们直接画图都能理解 //那么旋转之后，失衡节点的平衡因子就是0，而失衡节点的左孩子的平衡因子也是0 //AVL树 LR型失衡（左-右型）平衡因子更新 - 第三种情况 //核心场景：失衡节点的左孩子的左右子树、失衡节点的右子树原本均为空， //新插入节点直接作为【失衡节点的左孩子的右孩子】（即midNode就是新节点） //关键特征：midNode（新节点）无任何子节点，其初始平衡因子为0（无左右子树） // 1. 核心节点定义 // root: 失衡节点（触发LR型失衡的根节点） // leftNode: root的左孩子（root->left，插入前无任何子节点） // midNode: leftNode的右孩子（leftNode->right，就是本次新插入的节点，无左右子树） // 2. 插入前的初始状态（高度+平衡因子） // 为了量化分析，定义“空树高度为0，单个节点高度为1”： // ① leftNode：无左右子树 → 高度=1，平衡因子=0（左子树高度-右子树高度=0-0=0）； // ② root：左子树是leftNode（高度=1），右子树为空（高度=0）→ 平衡因子=1-0=1（未失衡）； // ③ 整体结构：root只有左孩子leftNode，leftNode无任何子节点，root右子树空。 // 3. 插入新节点后的失衡状态 // 新节点作为leftNode的右孩子（midNode），此时结构变化： // ① midNode：无左右子树 → 高度=1，平衡因子=0； // ② leftNode：左子树空（高度=0），右子树是midNode（高度=1）→ 高度=2，平衡因子=0-1=-1； // ③ root：左子树是leftNode（高度=2），右子树空（高度=0）→ 平衡因子=2-0=2（触发失衡）； // ④ 失衡类型判定：root平衡因子=2（左子树过高） + leftNode平衡因子=-1（右子树过高）→ 典型LR型失衡。 // 4. 旋转操作过程（LR型固定逻辑：先左旋leftNode，再右旋root） // ① 左旋leftNode： // leftNode原本只有右孩子midNode，左旋后midNode成为leftNode的父节点， // leftNode变为midNode的左孩子（leftNode的左右子树仍为空）； // 此时leftNode无任何子节点 → 高度=1，midNode的左子树是leftNode（高度=1）、右子树空（高度=0）。 // ② 右旋root： // root原本只有左子树（此时根为midNode），右旋后midNode成为root的父节点， // root变为midNode的右孩子（root的左右子树仍为空）； // 此时root无任何子节点 → 高度=1，midNode的右子树是root（高度=1）、左子树是leftNode（高度=1）。 // 5. 旋转后的平衡因子推导（核心结论：root和leftNode的平衡因子均为0） // 先明确旋转后各节点的子树高度： // ① leftNode：旋转后无任何子节点（左/右均为空）→ 左子树高度=0，右子树高度=0； // 平衡因子 = 左子树高度 - 右子树高度 = 0 - 0 = 0； // ② root：旋转后无任何子节点（左/右均为空）→ 左子树高度=0，右子树高度=0； // 平衡因子 = 左子树高度 - 右子树高度 = 0 - 0 = 0； // ③ midNode（新子树根节点）：左子树是leftNode（高度=1），右子树是root（高度=1）； // 平衡因子 = 1 - 1 = 0（整棵子树完全平衡）。 // 6. 关键逻辑补充（为什么旋转后两者平衡因子都为0？） // 本质原因是“初始结构无冗余子树”： // - 插入前leftNode和root的非空子树仅有“单个节点层”，无多层嵌套； // - 新节点是LR型中“最简化的插入场景”（midNode无任何子节点），旋转仅做“节点层级调整”，无复杂子树挂载； // - 旋转后leftNode和root都回到“单个节点、无任何子节点”的状态，自然左右子树高度差为0，平衡因子为0。 // 7. 与前两种情况的对比 // 相同点：midNode最终平衡因子均为0； // 不同点： // - 前两种情况midNode有子树（左/右），需考虑“子树纳用”对高度的影响； // - 第三种情况midNode无任何子树，旋转仅调整节点父子关系，无额外子树挂载，因此leftNode和root的平衡因子直接归0； // - 前两种情况root/leftNode的平衡因子可能为-1/0等，第三种情况是“完全对称平衡”，两者均为0。 // 总结：第三种情况是LR型失衡中最简化的场景，核心逻辑是“无冗余子树的节点层级重排”， // 旋转后所有涉及的节点都回到“单个节点、无左右子树”的基础状态，因此平衡因子均为0，整棵子树完全平衡。 if(sublrbf == -1)//第一种情况 { sublr->_bf = 0; parent->_bf = 1; subl->_bf = 0; } else if (sublrbf == 1)//第二种情况 { sublr->_bf = 0; parent->_bf = 0; subl->_bf = -1; } else if (sublrbf == 0)//第三种情况 { sublr->_bf = 0; parent->_bf = 0; subl->_bf = 0; } else { assert(false); } } //第四种情况：RL型，即新插入节点在失衡节点的右孩子的左子树中 //进行右左双旋 void RotateRL(node* parent) { assert(parent); assert(parent->_right); //那么对于RL型，即新插入节点在失衡节点的右孩子的左子树中 //其实处理起来还是比较麻烦的 //主要是麻烦在平衡因子的处理 //至于旋转其实很简单，先右单旋，再左单旋即可 //依旧是直接记住结论 //先右单旋失衡节点的右孩子，再左单旋失衡节点即可 //非要知道什么的话，原理就是先经过一次右单旋转使得RL型变为RR型 //那么一旦变为RR型了，就可以使用左单旋使得树变平衡 //先获取到需要的节点 node* subr = parent->_right; node* subrl = parent->_right->_left; // 失衡节点的右孩子的左孩子（mid节点） int subrlbf = subrl->_bf; // 记录失衡节点的右孩子的左孩子的平衡因子 // 为什么要记录：旋转过程会改变该节点的父子关系，平衡因子会被覆盖，需提前保存原始值 RotateR(subr); RotateL(parent); //最后就是重头戏平衡因子的处理了 //因为对于RL型，有三种情况： //1.失衡节点的右孩子的左右子树以及失衡节点的左子树都不是空的， //且新插入节点是在失衡节点的右孩子的左子树中的左子树 //即新插入节点是在失衡节点的右孩子的左孩子的左子树 //2.失衡节点的右孩子的左右子树以及失衡节点的左子树都不是空的， //且新插入节点是在失衡节点的右孩子的左子树中的右子树 //即新插入节点是在失衡节点的右孩子的左孩子的右子树 //3.失衡节点的右孩子的左右子树以及失衡节点的左子树原本都是空的， //新插入节点直接是插入在了失衡节点的右孩子的左子树中 //即新插入节点是在失衡节点的右孩子的左孩子 //那么对于这三种情况，得进行不同的平衡因子的处理 //所以，首当其冲的就是，怎么去判断是这三种情况的哪一种情况？？？ //其实啊，本质的本质，依旧是画图，树，就必须要去画图 //所以在这里，我们依旧是直接给结论 //针对第一种情况，那么它就是插入了在失衡节点的右孩子的左孩子中的左子树 //想想看，那么对于失衡节点的右孩子的左孩子，它的平衡因子应该是多少？？？ //其实很显然，应该是1，因为它的左子树比右子树高一层啊！！！！ //而第二种情况呢？？？且新插入节点是在失衡节点的右孩子的左子树中的右子树 //很显然，是-1，因为它的右子树比左子树高一层啊！！！！ //那么最后的第三种情况呢？？？？？ //别忘了，按照上面的情况，新插入节点就是失衡节点的右孩子的左孩子啊，其他的都没有了 //所以它的平衡因子就是0， //所以，我们要判断三种情况，本质上就是判断失衡节点的右孩子的左孩子的平衡因子 //然后就是，针对这三种情况，我们要怎么更新平衡因子呢？？？ //首先我们要先知道这三种情况更新平衡因子的相同点 //那么我们就要知道，当最后平衡的时候，失衡节点的右孩子的左孩子会变为新子树的根节点 //所以就是，失衡节点的右孩子的左孩子的平衡因子最后会变为0 //那么这就是三种情况的相同点 //随后就是不同点，那么同样也是要结合着图像进行理解，这里就简单分析一下 //我们知道，无论是左旋还是右旋，都会把被旋转的节点过程中碰到的左/右孩子纳为己用 //那么知道这一点，就可以知道很多了 //那么再根据我们上面旋转的方法以及顺序 //我们是先右旋失衡节点的右孩子，然后再左旋失衡节点 //那么在失衡节点右孩子右旋的过程中， //想想，它是不是会把它所碰到的失衡节点的右孩子的左孩子的右子树纳为己用（如果存在的话） //而在失衡节点左旋的过程中， //它是不是会把它所碰到的失衡节点的右孩子的左孩子的左子树纳为己用（如果存在的话） //所以，知道这两点，就是判断平衡因子的关键所在了 //而对于第一种情况，即新插入节点在失衡节点的右孩子的左孩子的左子树上 //那么再想想，我们假设失衡节点的右孩子的原本的右孩子（右子树）的高度是h //那么失衡节点的右孩子的左孩子的左子树和右子树的高度就都是h-1 //而当新插入节点在失衡节点的右孩子的左孩子的左子树上的时候，是不是 //失衡节点的右孩子的左孩子的左子树的高度是h，而右子树则还是h-1，这个很好理解 //那么我们前面说了， //在失衡节点右孩子右旋的过程中， //它会把它所碰到的失衡节点的右孩子的左孩子的右子树纳为己用（如果存在的话） //而在失衡节点左旋的过程中， //它会把它所碰到的失衡节点的右孩子的左孩子的左子树纳为己用（如果存在的话） //所以，最终的平衡的树，那么失衡节点的右孩子的左右子树就都会是h， // //即失衡节点的右孩子的平衡因子是0 // //而失衡节点的右子树的就是原本的失衡节点的右孩子的左孩子的左子树（h-1） //而失衡节点的左子树是和原本的一样的，即高度是h //为什么不是h+1呢？要是h+1的话，那么是不是原本的失衡节点的左右子树一样高 //那么在插入了新节点之后，怎么可能会失衡呢？？？ //再加上我们这是RL型，所以，原本的失衡节点的右子树比左子树高一层！！！ //回到上面，失衡节点的左子树高度为h， //而失衡节点右子树的就是原本的失衡节点的右孩子的左孩子的左子树（h-1） // //所以最终平衡的树的原本的失衡节点的平衡因子就是-1！！！ // //以上是第一种情况 //不过知道了第一种情况的平衡因子的更新之后，第二种情况的平衡因子的更新其实就和第一种情况一样 //只不过是反了过来罢了 //AVL树 RL型失衡（右-左型）平衡因子更新 - 第二种情况 //核心场景：新插入节点在【失衡节点的右孩子的左子树的右子树】中 //关键判断依据：失衡节点右孩子的左孩子（简称mid节点）的平衡因子为-1（右子树比左子树高1层） //逻辑衔接：与第一种情况（新节点在mid节点左子树）完全对称，类比理解即可 // 1. 核心节点定义（C++中通常用结构体指针表示树节点） // root: 失衡节点（平衡因子=-2，右子树高度 > 左子树高度+1） // rightNode: root的右孩子（root->right） // midNode: rightNode的左孩子（rightNode->left，RL型失衡的中间枢纽节点） // 2. 高度假设体系 // 假设前提1：旋转前，rightNode原本的右子树高度为h； // 假设前提2：插入新节点前，midNode的左、右子树高度均为h-1（RL型失衡的初始结构基础）； // 插入后变化：新节点插入midNode的右子树 → midNode的右子树高度从h-1变为h，左子树仍为h-1； // 推导结论：midNode的平衡因子 = 左子树高度 - 右子树高度 = (h-1) - h = -1（这是第二种情况的核心判断条件）。 // 3. 旋转过程的“子树纳用”逻辑（RL型固定操作：先右旋rightNode，再左旋root） // ① 右旋rightNode时： // rightNode作为被旋转节点，会将midNode的右子树（高度h-1）“纳用”为自己的新左子树； // 原因：右旋的本质是将midNode提升为rightNode的父节点，rightNode成为midNode的右孩子， // 此时midNode原本的右子树需要挂载到rightNode的左子树（保持BST性质）。 // ② 左旋root时： // root作为被旋转节点，会将midNode的左子树（高度h，插入新节点后）“纳用”为自己的新右子树； // 原因：左旋的本质是将midNode提升为root的父节点，root成为midNode的左孩子， // 此时midNode原本的左子树需要挂载到root的右子树（保持BST性质）。 // 4. 平衡因子更新推导（核心：旋转后所有节点的左右子树高度差≤1） // ① midNode的平衡因子： // 旋转后midNode成为新的子树根节点，其左子树是root（左右子树高度均为h）， // 右子树是rightNode（左右子树高度均为h），因此midNode的平衡因子 = h - h = 0； // （与第一种情况一致，三种RL子情况的midNode最终平衡因子均为0） // ② rightNode的平衡因子： // 右旋后rightNode的右子树保持原高度h，左子树是“纳用”的midNode右子树（高度h-1）； // 最终rightNode的左右子树高度差 = h - (h-1) = 1？不，旋转后子树高度会重新校准： // 实际平衡后，rightNode的左子树高度会被调整为h（因为midNode的右子树挂载后，整体高度对齐）， // 因此rightNode的平衡因子 = h - h = 0；（与第一种情况的rightNode平衡因子结果对称） // ③ root的平衡因子： // 左旋后root的左子树保持原高度h（RL型失衡的前提：root右子树原本比左子树高1层）， // 右子树是“纳用”的midNode左子树（高度h）； // 最终root的左右子树高度差 = h - h = 0？不，结合RL型失衡的初始条件修正： // 初始时root的左子树高度为h，右子树（rightNode所在子树）高度为h+1（导致平衡因子=-2）； // 旋转后root的右子树高度变为h（纳用midNode的左子树），左子树仍为h， // 因此root的平衡因子 = h - h = 0；（与第一种情况的root平衡因子=-1形成对称，核心差异源于新节点插入方向） // 5. 与第一种情况的核心异同（类比记忆，强化理解） // 相同点： // - 旋转操作顺序一致：先右旋rightNode，再左旋root； // - midNode最终平衡因子均为0； // - rightNode最终平衡因子均为0； // 不同点： // - 新节点插入方向：第一种在midNode左子树，第二种在midNode右子树； // - midNode初始平衡因子：第一种为1，第二种为-1； // - root最终平衡因子：第一种为-1，第二种为0；（对称差异的核心原因是“子树纳用”的来源不同） // 总结：RL型两种子情况（新节点在midNode左/右子树）的平衡因子更新，本质是“旋转导致的子树挂载方向对称”， // 结合第一种情况的逻辑，通过“方向反转”即可快速推导第二种情况，无需重复记忆复杂流程。 //然后就是第三种情况，那么这个其实就简单很多了 //这个情况是 //3.失衡节点的右孩子的左右子树以及失衡节点的左子树原本都是空的， //新插入节点直接是插入在了失衡节点的右孩子的左子树中 //即新插入节点是在失衡节点的右孩子的左孩子 //那么我们直接画图都能理解 //那么旋转之后，失衡节点的平衡因子就是0，而失衡节点的右孩子的平衡因子也是0 //AVL树 RL型失衡（右-左型）平衡因子更新 - 第三种情况 //核心场景：失衡节点的右孩子的左右子树、失衡节点的左子树原本均为空， //新插入节点直接作为【失衡节点的右孩子的左孩子】（即midNode就是新节点） //关键特征：midNode（新节点）无任何子节点，其初始平衡因子为0（无左右子树） // 1. 核心节点定义 // root: 失衡节点（触发RL型失衡的根节点） // rightNode: root的右孩子（root->right，插入前无任何子节点） // midNode: rightNode的左孩子（rightNode->left，就是本次新插入的节点，无左右子树） // 2. 插入前的初始状态（高度+平衡因子） // 为了量化分析，定义“空树高度为0，单个节点高度为1”： // ① rightNode：无左右子树 → 高度=1，平衡因子=0（左子树高度-右子树高度=0-0=0）； // ② root：右子树是rightNode（高度=1），左子树为空（高度=0）→ 平衡因子=0-1=-1（未失衡）； // ③ 整体结构：root只有右孩子rightNode，rightNode无任何子节点，root左子树空。 // 3. 插入新节点后的失衡状态 // 新节点作为rightNode的左孩子（midNode），此时结构变化： // ① midNode：无左右子树 → 高度=1，平衡因子=0； // ② rightNode：右子树空（高度=0），左子树是midNode（高度=1）→ 高度=2，平衡因子=1-0=1； // ③ root：右子树是rightNode（高度=2），左子树空（高度=0）→ 平衡因子=0-2=-2（触发失衡）； // ④ 失衡类型判定：root平衡因子=-2（右子树过高） + rightNode平衡因子=1（左子树过高）→ 典型RL型失衡。 // 4. 旋转操作过程（RL型固定逻辑：先右旋rightNode，再左旋root） // ① 右旋rightNode： // rightNode原本只有左孩子midNode，右旋后midNode成为rightNode的父节点， // rightNode变为midNode的右孩子（rightNode的左右子树仍为空）； // 此时rightNode无任何子节点 → 高度=1，midNode的右子树是rightNode（高度=1）、左子树空（高度=0）。 // ② 左旋root： // root原本只有右子树（此时根为midNode），左旋后midNode成为root的父节点， // root变为midNode的左孩子（root的左右子树仍为空）； // 此时root无任何子节点 → 高度=1，midNode的左子树是root（高度=1）、右子树是rightNode（高度=1）。 // 5. 旋转后的平衡因子推导（核心结论：root和rightNode的平衡因子均为0） // 先明确旋转后各节点的子树高度： // ① rightNode：旋转后无任何子节点（左/右均为空）→ 左子树高度=0，右子树高度=0； // 平衡因子 = 左子树高度 - 右子树高度 = 0 - 0 = 0； // ② root：旋转后无任何子节点（左/右均为空）→ 左子树高度=0，右子树高度=0； // 平衡因子 = 左子树高度 - 右子树高度 = 0 - 0 = 0； // ③ midNode（新子树根节点）：左子树是root（高度=1），右子树是rightNode（高度=1）； // 平衡因子 = 1 - 1 = 0（整棵子树完全平衡）。 // 6. 关键逻辑补充（为什么旋转后两者平衡因子都为0？） // 本质原因是“初始结构无冗余子树”： // - 插入前rightNode和root的非空子树仅有“单个节点层”，无多层嵌套； // - 新节点是RL型中“最简化的插入场景”（midNode无任何子节点），旋转仅做“节点层级调整”，无复杂子树挂载； // - 旋转后rightNode和root都回到“单个节点、无任何子节点”的状态，自然左右子树高度差为0，平衡因子为0。 // 7. 与前两种情况的对比 // 相同点：midNode最终平衡因子均为0； // 不同点： // - 前两种情况midNode有子树（左/右），需考虑“子树纳用”对高度的影响； // - 第三种情况midNode无任何子树，旋转仅调整节点父子关系，无额外子树挂载，因此rightNode和root的平衡因子直接归0； // - 前两种情况root/rightNode的平衡因子可能为-1/0等，第三种情况是“完全对称平衡”，两者均为0。 // 总结：第三种情况是RL型失衡中最简化的场景，核心逻辑是“无冗余子树的节点层级重排”， // 旋转后所有涉及的节点都回到“单个节点、无左右子树”的基础状态，因此平衡因子均为0，整棵子树完全平衡。 if (subrlbf == 1)//第一种情况：新节点在subrl左子树 { subrl->_bf = 0; parent->_bf = -1; subr->_bf = 0; } else if (subrlbf == -1)//第二种情况：新节点在subrl右子树 { subrl->_bf = 0; parent->_bf = 0; subr->_bf = 1; } else if (subrlbf == 0)//第三种情况：新节点就是subrl { subrl->_bf = 0; parent->_bf = 0; subr->_bf = 0; } else { assert(false && "RL型平衡因子值非法！"); } } bool _IsBalanceTree(node* root)//检验是否是AVL树 { //本质需要依靠获取到根节点的左右子树的高度，所以这也是为什么我们前面实现求高度的函数 // 空树也是AVL树 if (nullptr == root) return true; // 计算pRoot结点的平衡因子：即pRoot左右子树的高度差 int leftHeight = _AVLTreeHeight(root->_left); int rightHeight = _AVLTreeHeight(root->_right); int diff = rightHeight - leftHeight; // 如果计算出的平衡因子与pRoot的平衡因子不相等，或者 // pRoot平衡因子的绝对值超过1，则一定不是AVL树 if (abs(diff) >= 2) { cout << root->_kv.first << "高度差异常" << endl; return false; } if (root->_bf != diff) { cout << root->_kv.first << "平衡因子异常" << endl; return false; } // pRoot的左和右如果都是AVL树，则该树一定是AVL树 return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right); } private: node* _root=nullptr;//整棵树的最上面的根节点 }; } 

Test_AVLTree.cpp:

#include "AVLTree.hpp" using namespace AVLTreeModule; using namespace std; // 测试代码 void TestAVLTree1() { AVLTree<int, int> t; // 常规的测试用例 //int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 }; // 特殊的带有双旋场景的测试用例 int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; for (auto e : a) { t.Insert({ e, e }); } t.InOrder(); cout << t.IsBalanceTree() << endl; } // 插入一堆随机值，测试平衡，顺便测试一下高度和性能等 void TestAVLTree2() { const int N = 100000; vector<int> v; v.reserve(N); srand(time(0)); for (size_t i = 0; i < N; i++) { v.push_back(rand() + i); } size_t begin2 = clock(); AVLTree<int, int> t; for (auto e : v) { t.Insert(make_pair(e, e)); } size_t end2 = clock(); cout << "Insert:" << end2 - begin2 << endl; cout << t.IsBalanceTree() << endl; cout << "Height:" << t.Height() << endl; size_t begin1 = clock(); // 确定在的值 //for (auto e : v) //{ // t.Find(e); //} // 随机值 for (size_t i = 0; i < N; i++) { t.Find((rand() + i)); } size_t end1 = clock(); cout << "Find:" << end1 - begin1 << endl; } int main() { TestAVLTree1(); TestAVLTree2(); return 0; } 

各位，对于树的学习，我只想说，请一定自己亲手画图理解，并且脑子里要有旋转的画面，可以先看动图进行理解！！！

结语：于平衡中见智慧，于深耕中得成长

当你合上这份 AVL 树的解析文档时，想必指尖还残留着梳理旋转逻辑时的纠结，脑海里还回荡着平衡因子更新规则的推导 —— 从二叉搜索树退化为链表的痛点，到 AVL 树 “高度差≤1” 的平衡约束，从四种失衡类型的旋转策略，到上万行代码的实现与测试，我们终于走完了这段 “在平衡中求索” 的学习旅程。此刻的你，或许不再为 “LR 型失衡为何需要双旋” 而困惑，不再为 “平衡因子更新到哪一步停止” 而迷茫 —— 这份从 “不懂” 到 “通透” 的跨越，正是技术学习最珍贵的勋章。

回望整个学习过程，AVL 树给我们的绝不仅仅是 “一种自平衡二叉搜索树的实现方法”，更是一套解决复杂问题的思维范式。当我们发现二叉搜索树在有序插入时的效率崩塌，没有停留在 “接受缺陷”，而是思考 “如何主动维持平衡”—— 这是从 “被动适应” 到 “主动设计” 的转变；当我们引入 “平衡因子” 这个工具，把 “判断子树是否平衡” 转化为 “计算左右子树高度差”，这是用 “量化指标” 简化模糊判断的智慧；当我们把失衡类型拆解为 LL、RR、LR、RL 四种场景，为每种场景设计针对性的旋转策略，这是将 “复杂问题拆分为可解决的子问题” 的核心能力。你看，从节点结构中加入父指针以实现向上遍历，到旋转操作中精准调整节点指针以保持二叉搜索树的有序性，再到测试环节用 “常规用例覆盖典型场景 + 随机数据验证鲁棒性” 的思路确保代码正确 —— 每一个细节，都是 “把复杂问题拆解、再逐个击破” 的实践，而这，恰恰是编程领域最核心的思维能力。

我知道，你或许曾在 “左右双旋” 的逻辑里反复画图推演，在 “平衡因子更新规则” 的边界条件中来回试探，在 “旋转后节点指针挂载” 的细节上反复调试 —— 这些看似 “磨人” 的过程，其实是你与 AVL 树 “深度对话” 的证明。就像 AVL 树需要通过不断调整旋转来维持平衡，我们的技术成长也需要在 “遇到问题 - 解决问题 - 总结规律” 的循环中打磨自己。你可能会问：“工业级应用中红黑树更常用，为什么还要花这么多精力学 AVL 树？” 答案很简单：AVL 树是 “自平衡二叉搜索树” 的鼻祖，它的平衡思想是所有高级平衡树的基石。红黑树的 “颜色约束” 本质上是对 AVL 树 “高度约束” 的优化，Splay 树的 “伸展操作” 是对 “局部性原理” 的结合 —— 如果说 AVL 树是带你走进 “平衡树世界” 的第一道门，那么掌握了 AVL 树的平衡逻辑、旋转策略，后续学习任何复杂的平衡树结构，都会有种 “触类旁通” 的通透。

还记得我们在测试环节设计的常规用例吗？LL 型失衡的右单旋、RR 型失衡的左单旋、LR 型的左右双旋、RL 型的右左双旋，每一个用例都精准命中了 AVL 树的核心痛点；而十万级随机数据的测试，则是对代码鲁棒性的终极考验 —— 这让我想起一句话：“能跑的代码不算难，能稳定跑过各种极端场景的代码才可贵。”AVL 树的实现如此，任何技术的落地亦如此。我们写的不仅是 “插入节点” 的代码，更是 “对边界条件的考量”“对异常情况的处理”“对结果的验证意识”—— 这些看似琐碎的习惯，会慢慢沉淀为你编程能力的 “底层基石”，让你在未来面对更复杂的项目时，少走弯路，多一份从容。

技术的学习从来不是 “单点突破”，而是 “织网成面”。AVL 树的学习，串联起了你对二叉搜索树的理解、对递归与迭代的运用、对指针操作的把控、对测试思维的建立 —— 你会发现，之前学过的模板类设计，在这里用于实现通用的键值对存储；之前理解的父指针作用，在这里用于向上更新平衡因子；之前掌握的递归遍历，在这里用于平衡检测与中序验证。这些知识点不再是孤立的 “碎片”，而是被 AVL 树这个 “主线” 串联起来的 “网络”，而你的知识体系，正是在这样的 “串联” 中逐渐成型的。

当你真正理解了 AVL 树，你会发现它不仅是一个数据结构，更是一种 “平衡的哲学”—— 它不追求 “绝对的完美平衡”（高度差 = 0），而是选择 “可行的适度平衡”（高度差≤1），在 “性能” 与 “实现复杂度” 之间找到最优解。这像极了我们的技术选择：不是追求最复杂的方案，而是选择最适合场景的方案；也像极了我们的成长路径：不必急于求成追求 “全能”，而是在每一个阶段找到自己的 “平衡态”，稳步前行。

或许此刻的你，已经迫不及待想探索更广阔的领域：比如研究红黑树如何用颜色规则降低旋转频率，比如了解 B + 树如何适配磁盘 IO 的特性成为数据库索引的核心，比如探索跳表如何用 “分层索引” 实现平衡树的功能却无需旋转 —— 请大胆往前走吧！AVL 树给你的，不仅是一段代码、一个算法，更是一双 “看透问题本质” 的眼睛，一种 “拆解复杂问题” 的思维，一份 “打磨细节、追求极致” 的态度。

技术的道路没有捷径，就像 AVL 树的每一次旋转都必须精准调整每一个指针，你的每一次成长也必须踏踏实实地攻克每一个难点。可能你会遇到更复杂的算法，更晦涩的理论，但请记住学习 AVL 树时的这份坚持：那些让你头疼的旋转逻辑，最终会变成你笔下流畅的代码；那些让你反复推敲的平衡规则，最终会成为你认知里的 “常识”。

AVL 树的故事落幕了，但你的技术探索之路才刚刚启程。愿你带着这份 “于平衡中见智慧” 的感悟，在数据结构与算法的世界里继续深耕，在一行行代码中沉淀力量，在一次次突破中遇见更好的自己。当未来的你回望这段学习经历，会感谢此刻愿意花时间琢磨 “旋转逻辑”“平衡因子” 的自己 —— 因为所有的深耕，终会开花结果；所有的坚持，终会带你抵达想去的远方。