【C++】20. AVL树的实现
在前面的章节中，我们实现了二叉搜索树，但是当时我们提及了一个二叉搜索树的的缺点，最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为： N
这就很坏了，那有没有好的解决办法呢？
今天我们就来介绍一种，那就是AVL树
1. AVL的概念
AVL树：自平衡二叉查找树的先驱
I. AVL树的基本定义与性质
AVL树（Adelson-Velsky and Landis Tree）是最早发明的自平衡二叉查找树，它要么是一棵空树，要么满足以下严格的性质：
- 子树性质：其左右子树均为AVL树
- 平衡性质：左右子树高度差的绝对值不超过1
通过这种严格的高度差控制，AVL树实现了高度平衡的二叉搜索结构。例如，在一个包含7个节点的AVL树中，树的高度始终为3，而普通二叉搜索树在相同节点数下，高度可能达到6。
II. 历史渊源与命名由来
AVL树以两位前苏联科学家G. M. Adelson-Velsky和E. M. Landis的名字命名。1962年，他们在论文《An algorithm for the organization of information》中首次提出了这一数据结构。这篇开创性的论文发表在《Doklady Akademii Nauk SSSR》期刊上，为计算机科学领域的数据结构研究开辟了新的方向。
III. 平衡因子的引入与作用
在AVL树的实现中，平衡因子（balance factor）是一个关键概念：
- 定义：每个节点的平衡因子 = 右子树高度 - 左子树高度
- 取值范围：在AVL树中，平衡因子的值只能是-1、0或1
- 作用：虽然平衡因子并非AVL树的必要属性，但它如同风向标一般，能够直观地帮助我们观察和控制树的平衡状态。例如，在插入新节点后，我们可以通过检查平衡因子来判断是否需要进行旋转操作。
IV. 高度差限制的合理性
为什么AVL树要求高度差不超过1，而不是完全平衡（高度差为0）呢？通过具体案例分析可以发现：
- 节点数为2：无法实现完全平衡，因为一个节点必须作为根节点，另一个节点只能作为左子树或右子树
- 节点数为4：同样无法实现完全平衡，此时高度差为1已经是最佳平衡状态
- 实际应用：在数据库索引等场景中，这种近似平衡已经能够提供足够好的性能，同时避免了完全平衡带来的实现复杂度
V. 性能分析与应用价值
AVL树的节点数量与分布特征与完全二叉树相似，其高度可严格控制在logN级别。因此，其基本操作的时间复杂度都能保持在O(logN)：
- 查找操作：与普通二叉搜索树相同，时间复杂度为O(logN)
- 插入操作：需要额外进行平衡调整，但时间复杂度仍为O(logN)
- 删除操作：同样需要进行平衡调整，时间复杂度为O(logN)
这种性能优势使得AVL树在以下场景中得到广泛应用：
- 数据库索引
- 内存中的有序数据存储
- 需要频繁查找、插入和删除操作的场景
通过这种严格的自平衡机制，AVL树在保证高效操作的同时，避免了普通二叉搜索树可能退化为链表的最坏情况，为各种需要高效查找和动态更新的应用场景提供了可靠的数据结构支持。
2. AVL树的实现
2.1 实现AVL树的准备工作
和二叉搜索树一样，首先要封装一个树节点类和一个树类，如下：
I. 节点结构体 AVLTreeNode
template<class K, class V>
struct AVLTreeNode {pair<K, V> _kv; // 键值对AVLTreeNode<K, V>* _left; // 左子节点AVLTreeNode<K, V>* _right; // 右子节点AVLTreeNode<K, V>* _parent;// 父节点指针int _bf; // 平衡因子（右子树高度 - 左子树高度）AVLTreeNode(const pair<K, V>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {} // 构造函数初始化成员
};关键成员解析
| 成员 | 作用 |
|---|---|
_kv | 存储键值对（Key-Value），用于节点数据的存储和比较。 |
_left | 指向左子节点的指针，遵循二叉搜索树规则（左子树值 < 当前节点值）。 |
_right | 指向右子节点的指针，遵循二叉搜索树规则（右子树值 > 当前节点值）。 |
_parent | 指向父节点的指针，用于回溯调整平衡因子和旋转操作。 |
_bf | 平衡因子（Balance Factor），计算公式为 右子树高度 - 左子树高度。 |
II. AVL树类 AVLTree
template<class K, class V>
class AVLTree {using Node = AVLTreeNode<K, V>; // 类型别名简化代码
public:// 公有方法（待实现：插入、删除、查找等）
private:Node* _root = nullptr; // 根节点指针
};关键设计点
-
模板参数：
-
K和V表示键（Key）和值（Value），支持泛型，允许存储任意类型的数据。 -
例如：
AVLTree<int, string>表示键为整数、值为字符串的AVL树。
-
-
类型别名
Node：-
使用
using Node = AVLTreeNode<K, V>简化类型名称，避免重复写模板参数。
-
-
私有成员
_root：-
根节点指针，初始化为
nullptr，表示空树。
-
III. 父节点指针的意义
-
为什么需要
_parent？
在插入或删除节点后，需要从当前节点向上回溯到根节点，依次检查每个祖先节点的平衡因子。显式维护_parent可以避免递归回溯，直接通过指针链向上遍历。 -
旋转操作中的关键作用：
旋转会改变节点父子关系，需同步更新_parent、_left、_right指针，否则会导致树结构错误。
IV. 对比简化实现
若省略 _parent，需通过递归或栈记录路径，代码会稍复杂。例如：
// 递归插入示例（无_parent）
Node* Insert(Node* root, const K& key) {if (!root) return new Node(key);if (key < root->_key) root->_left = Insert(root->_left, key);else root->_right = Insert(root->_right, key);// 递归返回时更新平衡因子并旋转UpdateBalance(root);return root;
}总结
这段代码是AVL树的框架实现，核心特点是：
-
通过
_parent指针显式维护父子关系，优化回溯过程。 -
使用模板支持泛型键值对。
-
平衡因子
_bf直接存储，避免重复计算。
template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv; // 键值对AVLTreeNode<K, V>* _left; // 左子节点AVLTreeNode<K, V>* _right; // 右子节点AVLTreeNode<K, V>* _parent;// 父节点指针int _bf;//balance factor — 平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),parent(nullptr),_bf(0){}
};template<class K, class V>
class AVLTree
{using Node = AVLTreeNode<K, V>;
public:
private:Node* _root = nullptr;
};2.2 AVL树的插入
2.2.1 AVL树插入值的基本流程
-
插入操作：按照二叉搜索树的规则插入新值。
-
更新平衡因子：插入新节点后，仅影响其祖先节点的高度，进而可能影响部分祖先节点的平衡因子。因此，需要从新节点到根节点的路径上更新平衡因子。在最坏情况下，需要更新到根节点，但在某些情况下，更新到中间节点即可停止，具体细节将在后续详细分析。
-
插入完成：如果在更新平衡因子的过程中未出现不平衡，则插入操作完成。
-
旋转处理：如果在更新平衡因子的过程中发现不平衡，则对不平衡的子树进行旋转。旋转不仅调整了子树的平衡，还降低了子树的高度，因此不会影响更高层的节点，插入操作完成。
2.2.2 平衡因子的更新
更新原则：
- 平衡因子计算：平衡因子 = 右子树高度 - 左子树高度。
- 影响条件：只有子树高度变化才会影响当前节点的平衡因子。
- 插入影响：插入新节点会增加子树高度。如果新节点插入在父节点的右子树，则父节点的平衡因子加1；如果插入在左子树，则父节点的平衡因子减1。
- 继续更新条件：父节点所在子树的高度是否变化决定了是否需要继续向上更新。
更新停止条件：
-
平衡因子为0：更新后父节点的平衡因子为0，且更新过程中平衡因子从-1变为0或从1变为0。这表明插入前父节点的子树一边高一边低，新节点插入在较低的一边，插入后子树高度不变，不会影响父节点的父节点的平衡因子，更新结束。
-
平衡因子为1或-1：更新后父节点的平衡因子为1或-1，且更新过程中平衡因子从0变为1或从0变为-1。这表明插入前父节点的子树两边高度相同，插入后子树一边高一边低，虽然子树仍符合平衡要求，但高度增加了1，会影响父节点的父节点的平衡因子，因此需要继续向上更新。
-
平衡因子为2或-2：更新后父节点的平衡因子为2或-2，且更新过程中平衡因子从1变为2或从-1变为-2。这表明插入前父节点的子树一边高一边低，新节点插入在较高的一边，导致子树更高的一边进一步增高，破坏了平衡。此时需要对子树进行旋转处理，旋转的目标有两个：一是使子树恢复平衡；二是降低子树的高度，恢复到插入前的高度。旋转后不需要继续向上更新，插入操作完成。
-
更新到根节点：如果更新到根节点，且根节点的平衡因子为1或-1，则更新停止。
更新到10结点，平衡因子为2，10所在的子树已经不平衡，需要旋转处理
更新到中间结点，3为根的子树高度不变，不会影响上一层，更新结束
最坏更新到根停止
2.2.3 代码实现和梳理
步骤 1：初始化与空树处理
bool Insert(const pair<K, T>& kv) {Node* newnode = new Node(kv);if (_root == nullptr) {_root = newnode;return true;}// ...
}作用：
-
创建新节点
newnode，存储键值对kv。 -
若树为空（
_root为nullptr），直接将新节点设为根节点，插入完成。
步骤 2：查找插入位置
Node* parent = nullptr;
Node* cur = _root;
while (cur) {if (cur->_kv.first < kv.first) {parent = cur;cur = cur->_right;} else if (cur->_kv.first > kv.first) {parent = cur;cur = cur->_left;} else {return false; // 键已存在，插入失败}
}过程：
-
从根节点
_root开始，用cur指针遍历树。 -
比较当前节点键值
cur->_kv.first与待插入键值kv.first：-
当前节点键 < 插入键：向右子树移动。
-
当前节点键 > 插入键：向左子树移动。
-
键相等：直接返回
false（假设不允许重复键）。
-
-
最终
cur变为nullptr，parent指向插入位置的父节点。
步骤 3：插入新节点
if (parent->_kv.first < kv.first) {parent->_right = newnode;
} else {parent->_left = newnode;
}
newnode->_parent = parent; // 链接父节点
cur = newnode;//更新cur逻辑：
-
根据
parent的键值与插入键的比较结果，将新节点插入到正确位置：-
插入到父节点的右子树（
parent->_right）或左子树（parent->_left）。
-
-
设置新节点的父指针
_parent，形成双向链接。 -
cur此时为nullptr，更新cur
步骤 4：更新平衡因子
while (parent) {// 判断新节点是左子树还是右子树if (parent->_left == cur) {parent->_bf--; // 左子树高度增加，平衡因子-1} else {parent->_bf++; // 右子树高度增加，平衡因子+1}// 根据平衡因子决定是否继续回溯if (parent->_bf == 0) {break; // 子树高度未变，无需继续更新} else if (parent->_bf == 1 || parent->_bf == -1) {cur = parent;parent = parent->_parent; // 继续向上更新} else if (parent->_bf == 2 || parent->_bf == -2) {// 触发旋转调整（代码未实现）break;} else {assert(false); // 平衡因子异常（绝对值为3）}
}平衡因子更新规则
| 平衡因子变化 | 含义 |
|---|---|
| 0 | 原平衡因子为1或-1，插入后子树高度不变，停止回溯。 |
| 1/-1 | 原平衡因子为0，插入后子树高度增加，需继续向上更新。 |
| 2/-2 | 子树不平衡，触发旋转（代码中未实现，需补充旋转逻辑）。 |
| 其他值 | 非法情况（如平衡因子绝对值为3），断言报错。 |
步骤 5：旋转调整（未实现）
还未实现旋转逻辑：
else if (parent->_bf == 2 || parent->_bf == -2) {// 旋转操作（需补充）break;
}需补充以下逻辑：
-
根据平衡因子和子树结构判断旋转类型（LL/RR/LR/RL）。
-
执行对应的旋转操作（左旋、右旋、左右旋、右左旋）。
-
更新旋转后相关节点的父指针和平衡因子。
接下来我们就来实现一下旋转逻辑，插入完整代码在实现旋转逻辑之后，再统一贴上来
2.3 旋转
2.3.1 旋转的原则
- 保持搜索树的规则：旋转操作必须确保二叉搜索树的性质不被破坏。
- 恢复平衡并降低高度：通过旋转使不平衡的树重新达到平衡状态，同时尽可能降低树的高度。
旋转操作主要分为四种类型：左单旋、右单旋、左右双旋和右左双旋。
说明：在后续图示中，部分节点（如10和5）使用了具体数值进行说明，这仅是为了便于讲解。实际应用中，节点值可以是任意符合二叉搜索树性质的数值。
2.3.2 右单旋
-
图1展示了一棵以10为根的树，其中a、b、c分别代表三棵高度为h的子树（h≥0），且这些子树均满足AVL树的要求。10可能是整棵树的根节点，也可能是某个局部子树的根节点。a、b、c作为高度为h的子树，是对右单旋场景的抽象概括，实际右单旋的具体形态可参考图2至图5的详细描述。
-
失衡原因：在a子树中插入一个新节点，导致a子树的高度从h增加到h+1。随着平衡因子的逐层更新，10的平衡因子从-1变为-2，使得以10为根的树左右高度差超过1，违反了AVL树的平衡规则。此时，树的左侧过高，需要通过右旋操作来恢复平衡。
-
旋转步骤：由于5 < b子树的值 < 10，旋转的核心操作是将b子树作为10的左子树，10作为5的右子树，并将5提升为新的根节点。这一操作不仅保持了二叉搜索树的性质，还恢复了树的平衡，使树的高度重新回到插入前的h+2。如果10原本是整棵树的某个局部子树，旋转后不会影响上层结构，插入操作完成。
图1
图2
图3
图4
图5
2.3.3 右单旋代码实现和梳理
步骤 1：获取关键节点
Node* subL = parent->_left; // parent的左子节点（旋转后的新根）
Node* subLR = subL->_right; // subL的右子节点（可能为空）作用：
-
subL是旋转后将成为新根的节点。 -
subLR是需要转移的子树（原subL的右子树）。
步骤 2：调整节点指针关系
subL->_right = parent; // subL接管parent为其右子节点
parent->_left = subLR; // parent接管subLR为其左子节点步骤 3：维护父节点指针
Node* pParent = parent->_parent; // 保存原parent的父节点
parent->_parent = subL; // parent的父指针指向subLif (subLR) { // 若subLR存在，更新其父指针subLR->_parent = parent;
}subL->_parent = pParent; // subL的父指针指向原parent的父节点意义：
-
确保旋转后所有节点的父指针正确，维护树的双向链接。
步骤 4：更新根节点或父节点的子树链接
if (parent == _root) { // 若parent是原根节点_root = subL; // 更新根节点为subL
} else { // 若parent不是根节点if (pParent->_left == parent) {pParent->_left = subL; // 原parent在左子树的位置被subL取代} else {pParent->_right = subL; // 原parent在右子树的位置被subL取代}
}关键点：
-
若旋转的是整棵树的根节点，需更新全局根指针
_root。 -
若旋转的是子树，需让原父节点指向新的子节点
subL。
步骤 5：重置平衡因子
subL->_bf = 0;
parent->_bf = 0;原理：
-
右单旋后，原不平衡的子树高度恢复平衡，
subL和parent的平衡因子均变为0。
具体代码如下：
// 右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;// parent的左子节点（旋转后的新根）Node* subLR = subL->_right;// subL的右子节点（可能为空）// 旋转节点subL->_right = parent;parent->_left = subLR;// 维护父指针Node* pParent = parent->_parent;parent->_parent = subL;if (subLR) //若subLR存在,更新其父指针,避免堆空指针解引用{subLR->_parent = parent;}subL->_parent = pParent;// 维护parent的父节点if (parent == _root) // parent为根节点的情况{_root = subL;}else // parent是一棵局部子树的情况{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}}// 更新平衡因子subL->_bf = 0;parent->_bf = 0;
}2.3.4 左单旋
- 图6展示了一棵以10为根的树，其中a、b、c分别代表三棵高度为h的子树（h≥0）。这些子树均满足AVL树的要求，即每个节点的左右子树高度差不超过1。10可能是整棵树的根节点，也可能是某个局部子树的根节点。这里的a、b、c作为高度为h的子树，是对所有右单旋场景的抽象表示，其具体形态与前述右旋情况类似。
- 当在a子树中插入一个新节点时，a子树的高度从h增至h+1。这一变化会逐层向上更新平衡因子，导致10的平衡因子从1变为2，使得以10为根的树左右高度差超过1，违反了AVL树的平衡规则。此时，由于树的右侧过高，需要通过左旋操作来恢复平衡。
左旋操作的核心步骤
- 确定旋转点：以10为旋转点，其右子树b的高度为h+1，左子树a的高度为h+1，右子树的右子树c的高度为h。
- 调整子树关系：
- 由于10 < b子树的值 < 15，将b子树调整为10的右子树。
- 将10调整为15的左子树。
- 15则成为这棵树的新根节点。
- 恢复平衡：这一调整既符合二叉搜索树的规则，又恢复了树的平衡。旋转后，树的高度恢复到插入前的h+2，符合旋转原则。
旋转后的影响
如果10原本是整棵树的局部子树，旋转后不会影响上层结构，插入操作即告完成。旋转操作不仅恢复了树的平衡，还保持了二叉搜索树的性质，即左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。
图6
2.3.5 左单旋代码实现和梳理
步骤 1：获取关键节点
Node* subR = parent->_right; // parent的右子节点（旋转后的新根）
Node* subRL = subR->_left; // subR的左子节点（可能为空）作用：
-
subR是旋转后将成为新根的节点。 -
subRL是需要转移的子树（原subR的左子树）。
步骤 2：调整节点指针关系
subR->_left = parent; // subR接管parent为其左子节点
parent->_right = subRL; // parent接管subRL为其右子节点步骤 3：维护父节点指针
Node* pParent = parent->_parent; // 保存原parent的父节点
parent->_parent = subR; // parent的父指针指向subRif (subRL) { // 若subRL存在，更新其父指针subRL->_parent = parent;
}subR->_parent = pParent; // subR的父指针指向原parent的父节点意义：
-
确保旋转后所有节点的父指针正确，维护树的双向链接。
步骤 4：更新根节点或父节点的子树链接
if (parent == _root) { // 若parent是原根节点_root = subR; // 更新根节点为subR
} else { // 若parent不是根节点if (pParent->_left == parent) {pParent->_left = subR; // 原parent在左子树的位置被subR取代} else {pParent->_right = subR; // 原parent在右子树的位置被subR取代}
}关键点：
-
若旋转的是整棵树的根节点，需更新全局根指针
_root。 -
若旋转的是子树，需让原父节点指向新的子节点
subR。
步骤 5：重置平衡因子
subR->_bf = 0;
parent->_bf = 0;原理：
-
左单旋后，原不平衡的子树高度恢复平衡，
subR和parent的平衡因子均变为0。
具体代码如下：
// 左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;// parent的右子节点（旋转后的新根）Node* subRL = subR->_left;// subR的左子节点（可能为空）// 旋转节点subR->_left = parent;parent->_right = subRL;// 维护父指针Node* pParent = parent->_parent;parent->_parent = subR;if (subRL) //若subRL存在,更新其父指针,避免堆空指针解引用{subRL->_parent = parent;}subR->_parent = pParent;// 维护parent的父节点if (parent == _root) // parent为根节点的情况{_root = subR;}else // parent是一棵局部子树的情况{if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}}// 更新平衡因子subR->_bf = 0;parent->_bf = 0;
}2.3.6 左右双旋
如图7和图8所示，当左子树较高且新节点插入在b子树而非a子树时，b子树的高度将从h增至h+1，导致树结构失衡。此时，仅靠右单旋无法恢复平衡，因为右单旋仅适用于纯粹的左子树较高情况。在本例中，以10为根的子树不仅左子树较高，其右子树（以5为根）也出现了右子树较高的情况。因此，需要通过两次旋转来恢复平衡：首先以5为旋转点进行左单旋，然后以10为旋转点进行右单旋，最终使整棵树达到平衡状态。
图7
图8
图7和图8分别展示了左右双旋在h=0和h=1时的具体场景。为便于分析，我们将a/b/c子树抽象为高度h的AVL子树。同时，需要将b子树进一步展开为节点8及其左子树（高度为h-1的e和f子树），因为以节点5为旋转点进行左单旋时，需要调整b子树中的左子树。由于新增节点在b子树中的位置不同，平衡因子的更新方式也有所差异。根据节点8的平衡因子变化，我们将其分为三种场景进行讨论。
场景1：当h≥1时，若新增节点插入在e子树，e子树的高度将从h-1变为h，并依次更新节点8、5、10的平衡因子，最终引发旋转。此时节点8的平衡因子为-1，旋转后节点8和5的平衡因子为0，节点10的平衡因子为1。
场景2：当h≥1时，若新增节点插入在f子树，f子树的高度将从h-1变为h，并依次更新节点8、5、10的平衡因子，最终引发旋转。此时节点8的平衡因子为1，旋转后节点8和10的平衡因子为0，节点5的平衡因子为-1。场景3：当h=0时，a/b/c子树均为空树，b本身即为新增节点。此时依次更新节点5、10的平衡因
子，最终引发旋转。节点8的平衡因子为0，旋转后节点8、10、5的平衡因子均为0。
图9
2.3.7 左右双旋代码实现和梳理
步骤 1：获取关键节点与平衡因子
Node* subL = parent->_left; // parent的左子节点
Node* subLR = subL->_right; // subL的右子节点（关键节点）
int bf = subLR->_bf; // 保存旋转前的平衡因子作用：
-
subL是 parent 的左子节点，subLR是导致不平衡的关键节点。 -
记录
subLR的原始平衡因子bf，用于后续调整。
步骤 2：执行双旋操作
RotateL(parent->_left); // 对subL进行左旋（处理subL的右子树过高）
RotateR(parent); // 对parent进行右旋（处理parent的左子树过高）步骤 3：根据原始平衡因子更新平衡因子
情况 1：bf == 0（subLR自身是新增节点）
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;逻辑：
-
子树高度不变，所有相关节点平衡因子归零。
情况 2：bf == -1（新增节点在subLR的左子树）
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;逻辑：
-
左子树高度降低，parent 的右子树相对变高，平衡因子变为 +1。
情况 3：bf == 1（新增节点在subLR的右子树）
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;逻辑：
-
右子树高度降低，subL 的左子树相对变高，平衡因子变为 -1。
非法情况
else {assert(false); // 平衡因子绝对值超过1，非法
}具体代码如下：
// 左右双旋
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf; // 保存旋转前的平衡因子RotateL(parent->_left); // 对subL进行左旋（处理subL的右子树过高）RotateR(parent); // 对parent进行右旋（处理parent的左子树过高）// 更新平衡因子if (bf == 0){// 此时subLR就是新增节点subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else if (bf == -1){// 此时subLR的左子节点是新增节点subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){// 此时subLR的右子节点是新增节点subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else{assert(false); // 平衡因子绝对值超过1，非法}
}2.3.8 右左双旋
与左右双旋类似，我们将a/b/c子树抽象为高度h的AVL子树进行分析。此外，需要将b子树进一步展开为12节点及其左子树e和f，其中e和f的高度均为h-1。由于需要对b的父节点15进行右单旋，而右单旋会涉及b子树中的右子树。根据b子树中新增节点的位置不同，平衡因子的更新方式也有所差异。通过观察12节点的平衡因子，我们将分三种场景进行讨论。
场景1：当h ≥ 1时，若新增节点插入在e子树，e子树的高度从h-1变为h，并依次更新12→15→10的平衡因子，从而引发旋转。此时12的平衡因子为-1，旋转后10和12的平衡因子为0，15的平衡因子为1。
场景2：当h ≥ 1时，若新增节点插入在f子树，f子树的高度从h-1变为h，并依次更新12→15→10的平衡因子，从而引发旋转。此时12的平衡因子为1，旋转后15和12的平衡因子为0，10的平衡因子为-1。
场景3：当h = 0时，a/b/c均为空树，b本身即为新增节点，依次更新15→10的平衡因子，从而引发旋转。此时12的平衡因子为0，旋转后10、12和15的平衡因子均为0。
图10
2.3.9 右左双旋代码实现和梳理
步骤 1：获取关键节点与平衡因子
Node* subR = parent->_right; // parent的右子节点
Node* subRL = subR->_left; // subR的左子节点（关键节点）
int bf = subRL->_bf; // 保存旋转前的平衡因子作用：
-
subR是 parent 的右子节点，subRL是导致不平衡的关键节点。 -
记录
subRL的原始平衡因子bf，用于后续调整。
步骤 2：执行双旋操作
// 先对 subR 进行右旋（处理右子树的左子树过高）
RotateR(parent->_right);
// 再对 parent 进行左旋（处理 parent 的右子树过高）
RotateL(parent); 步骤 3：根据原始平衡因子更新平衡因子
情况 1：bf == 0（subRL自身是新增节点）
subRL->_bf = 0;
subR->_bf = 0;
parent->_bf = 0;逻辑：
-
子树高度不变，所有相关节点平衡因子归零。
情况 2：bf == -1（新增节点在subRL的左子树）
subRL->_bf = 0;
subR->_bf = 1; // 右子树高度增加
parent->_bf = 0; // 左子树高度不变逻辑：
-
subR 的右子树高度增加，平衡因子变为 +1。
情况 3：bf == 1（新增节点在subRL的右子树）
subRL->_bf = 0;
subR->_bf = 0; // 右子树高度不变
parent->_bf = -1; // 左子树高度降低逻辑：
-
parent 的左子树高度降低，平衡因子变为 -1。
非法情况
else {assert(false); // 平衡因子绝对值超过1，非法
}具体代码如下：
// 右左双旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf; // 保存旋转前的平衡因子RotateR(parent->_right); // 对subR进行右旋（处理subR的左子树过高）RotateL(parent); // 对parent进行左旋（处理parent的右子树过高）// 更新平衡因子if (bf == 0){// 此时subRL就是新增节点subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else if (bf == -1){// 此时subRL的左子节点是新增节点subRL->_bf = 0;subR->_bf = 1; // 右子树高度增加parent->_bf = 0; // 左子树高度不变}else if (bf == 1){// 此时subRL的右子节点是新增节点subRL->_bf = 0;subR->_bf = 0; // 右子树高度不变parent->_bf = -1; // 左子树高度降低}else{assert(false); // 平衡因子绝对值超过1，非法}
}补充insert中的旋转逻辑
-
旋转条件与类型判断
当 parent->_bf 的绝对值为 2 时，需根据 parent 和子节点 cur 的平衡因子判断具体的不平衡类型：
父节点 _bf | 子节点 cur->_bf | 不平衡类型 | 旋转操作 |
|---|---|---|---|
| -2 | -1 | LL型 | 右单旋 |
| 2 | 1 | RR型 | 左单旋 |
| -2 | 1 | LR型 | 左右双旋 |
| 2 | -1 | RL型 | 右左双旋 |
-
旋转逻辑详解
LL型（左左不平衡）
-
触发条件：
parent->_bf == -2（左子树高2）且cur->_bf == -1（左子树的左子树更高）。 -
操作：右单旋
RotateR(parent)。 -
效果：将左子树提升为根，恢复平衡。
RR型（右右不平衡）
-
触发条件：
parent->_bf == 2（右子树高2）且cur->_bf == 1（右子树的右子树更高）。 -
操作：左单旋
RotateL(parent)。 -
效果：将右子树提升为根，恢复平衡。
LR型（左右不平衡）
-
触发条件：
parent->_bf == -2（左子树高2）且cur->_bf == 1（左子树的右子树更高）。 -
操作：左右双旋
RotateLR(parent)。-
步骤：先对
cur左旋，再对parent右旋。
-
-
效果：将左子树的右子树提升为根，恢复平衡。
RL型（右左不平衡）
-
触发条件：
parent->_bf == 2（右子树高2）且cur->_bf == -1（右子树的左子树更高）。 -
操作：右左双旋
RotateRL(parent)。-
步骤：先对
cur右旋，再对parent左旋。
-
-
效果：将右子树的左子树提升为根，恢复平衡。
完整插入代码：
bool Insert(const pair<K, V>& kv)
{Node* newnode = new Node(kv);if (_root == nullptr){_root = newnode;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}if (parent->_kv.first < kv.first){parent->_right = newnode;}else{parent->_left = newnode;}//链接父亲节点newnode->_parent = parent;cur = newnode;// 更新cur//更新平衡因子while (parent){// 新增节点是左子节点，父亲节点的平衡因子--if (parent->_left == cur){parent->_bf--;}else // 新增节点是右子节点，父亲节点的平衡因子++{parent->_bf++;}if (parent->_bf == 0)// 1->0 || -1->0,说明高度不变{break;}else if (parent->_bf == 1 || parent->_bf == -1)//0->1 || 0->-1,说明高度增加,父亲节点为根的子树从两边高度相等变为一边高一边低{//继续向上更新平衡因子cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//1->2 || -1->-2,父节点为根的子树一边高一边低,newnode插入在了高的那边{//旋转if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}else{assert(false);//非法情况}}return true;
}2.4 AVL树的查找
AVL树是一种自平衡的二叉搜索树，其查找操作与普通的二叉搜索树（BST）相同。由于AVL树在插入和删除节点时会通过旋转操作保持树的平衡，因此其查找效率始终保持在O(logN)的水平，其中N为树中节点的数量。
查找操作步骤
- 从根节点开始：查找操作从AVL树的根节点开始。
- 比较目标值与当前节点值：
- 如果目标值等于当前节点的值，则查找成功，返回该节点。
- 如果目标值小于当前节点的值，则继续在当前节点的左子树中继续查找。
- 如果目标值大于当前节点的值，则继续在当前节点的右子树中继续查找。
- 循环迭代查找：直到找到目标节点或到达叶子节点（即当前节点为空），此时查找失败，返回空值。
Node* Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;
}2.5 AVL树平衡检测
在实现AVL树后，我们需要通过严格的平衡检测来验证其是否符合AVL树的性质。AVL树是一种自平衡二叉搜索树，其核心特性是每个节点的左右子树高度差（平衡因子）的绝对值不超过1。为了确保我们实现的AVL树是合格的，我们可以通过以下步骤进行平衡检测：
1. 平衡因子计算与验证
平衡因子是AVL树平衡检测的关键指标，其定义为：平衡因子 = 右子树高度 - 左子树高度
对于每个节点，我们需要：
- 计算其左右子树的高度。
- 根据上述公式计算平衡因子。
- 验证平衡因子的绝对值是否小于等于1。
如果某个节点的平衡因子绝对值大于1，则说明该节点不平衡，需要进一步调整。
2. 递归遍历检测
为了全面检测整棵AVL树的平衡性，我们可以采用递归遍历的方法：
- 前序遍历：从根节点开始，依次访问每个节点，计算其平衡因子并验证。
- 后序遍历：从叶子节点开始，逐步向上计算每个节点的高度和平衡因子。
3. 节点更新检查
在AVL树的插入或删除操作中，节点的平衡因子可能会发生变化。因此，我们需要确保：
- 每次操作后，相关节点的平衡因子被正确更新。
- 如果某个节点的平衡因子超出范围（即绝对值大于1），立即触发旋转操作以恢复平衡。
例如，在插入一个新节点后，我们需要从该节点开始，沿着父节点路径向上更新每个节点的平衡因子，直到根节点或某个节点的平衡因子不再变化。
4. 应用场景与测试
为了验证AVL树的平衡性，我们可以设计以下测试场景：
- 随机插入测试：随机生成一组数据插入AVL树，检查每次插入后树的平衡性。
- 删除测试：从AVL树中随机删除节点，检查每次删除后树的平衡性。
- 边界测试：测试极端情况，如插入大量有序数据或删除根节点，确保树的平衡性不受影响。
通过以上步骤，我们可以全面检测AVL树的平衡性，确保其符合自平衡二叉搜索树的性质。
2.5.1 中序遍历打印
和二叉搜索树一样都采用中序遍历来打印
void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}2.5.2 检查AVL树的平衡
1. High() 函数
作用
返回整棵 AVL 树的高度。
代码
int High() {return _High(_root); // 调用辅助函数，从根节点开始计算高度
}2. _High(Node* root) 函数
作用
递归计算以 root 为根的子树的高度。
步骤解析
-
终止条件：
若当前节点为空（root == nullptr），返回高度 0。if (root == nullptr) return 0; -
递归计算左子树高度：
int leftHigh = _High(root->_left); -
递归计算右子树高度：
int rightHigh = _High(root->_right); -
返回当前子树高度：
当前节点的高度为左右子树高度的较大值加 1。return (leftHigh > rightHigh) ? leftHigh + 1 : rightHigh + 1;
3. IsBalance() 函数
作用
检查整棵树是否满足 AVL 树的平衡条件。
代码流程
bool IsBalance() {return _IsBalance(_root); // 调用辅助函数，从根节点开始检查
}4. _IsBalance(Node* root) 函数
作用
递归检查以 root 为根的子树是否平衡，包括：
-
左右子树高度差不超过 1。
-
节点的平衡因子
_bf与实际高度差一致。
步骤解析
-
终止条件：
若当前节点为空（root == nullptr），返回true（空树视为平衡）。if (root == nullptr) return true; -
计算左右子树高度：
int leftHigh = _High(root->_left); int rightHigh = _High(root->_right); -
验证高度差：
计算diff = rightHigh - leftHigh，检查是否满足|diff| < 2。int diff = rightHigh - leftHigh; if (abs(diff) >= 2) {cout << root->_kv.first << "高度差异常" << endl;return false; } -
验证平衡因子：
检查节点的平衡因子_bf是否等于diff。if (root->_bf != diff) {cout << root->_kv.first << "平衡因子异常" << endl;return false; } -
递归检查子树：
对左子树和右子树分别递归调用_IsBalance。return _IsBalance(root->_left) && _IsBalance(root->_right);具体代码如下：
int High(){return _High(_root);}bool IsBalance(){return _IsBalance(_root);}
private:int _High(Node* root){if (root == nullptr) return 0;int leftHigh = _High(root->_left);int rightHigh = _High(root->_right);return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;}bool _IsBalance(Node* root){if (root == nullptr) return true;int leftHigh = _High(root->_left);int rightHigh = _High(root->_right);int diff = rightHigh - leftHigh;if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return _IsBalance(root->_left) && _IsBalance(root->_right);}5. Size
为方便后续测试对比查看，我们这里再来实现一个AVL树的节点数量的接口
int Size(){return _Size(_root);}
private:int _Size(Node* root){if (root == nullptr) return 0;int leftSize = _Size(root->_left);int rightSize = _Size(root->_right);return leftSize + rightSize + 1;}2.6 测试
这里我们分别弄一组常规测试数据和一组特殊带有双旋的测试数据，来测试一下我们的插入和旋转逻辑有没有问题
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.IsBalance() << endl;
}运行结果：
插入一堆随机值，测试平衡，顺便测试一下高度和性能等
测试性能的时候，我们可以分别测试查找随机值和一定存在的值
// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestAVLTree2()
{const int N = 100000;vector<int> v;v.reserve(N);srand((unsigned int)time(0));for (int 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.IsBalance() << endl;cout << "Height:" << t.High() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值/*for (auto e : v){t.Find(e);}*/// 随机值for (int i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}运行结果：
查找测试随机值
查找一定在的值
多次运行程序可以发现，查找一定在的值是要快一点的，这是由于随机值有可能不存在，那就会一直查找到空，而一定存在的值最坏情况也是查找到叶子节点，所以性能要稍微好一点
AVL树的删除本章节不做讲解，有兴趣的同学可参考：《殷人昆 数据结构：用面向对象方法与C++语言描述》中讲解。
AVL树代码(.h头文件)：
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv; // 键值对AVLTreeNode<K, V>* _left; // 左子节点AVLTreeNode<K, V>* _right; // 右子节点AVLTreeNode<K, V>* _parent;// 父节点指针int _bf;//balance factor — 平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}
};template<class K, class V>
class AVLTree
{using Node = AVLTreeNode<K, V>;
public:bool Insert(const pair<K, V>& kv){Node* newnode = new Node(kv);if (_root == nullptr){_root = newnode;return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}if (parent->_kv.first < kv.first){parent->_right = newnode;}else{parent->_left = newnode;}//链接父亲节点newnode->_parent = parent;cur = newnode;// 更新cur//更新平衡因子while (parent){// 新增节点是左子节点，父亲节点的平衡因子--if (parent->_left == cur){parent->_bf--;}else // 新增节点是右子节点，父亲节点的平衡因子++{parent->_bf++;}if (parent->_bf == 0)// 1->0 || -1->0,说明高度不变{break;}else if (parent->_bf == 1 || parent->_bf == -1)//0->1 || 0->-1,说明高度增加,父亲节点为根的子树从两边高度相等变为一边高一边低{//继续向上更新平衡因子cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2)//1->2 || -1->-2,父节点为根的子树一边高一边低,newnode插入在了高的那边{//旋转if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}else{assert(false);//非法情况}}return true;}// 右单旋void RotateR(Node* parent){Node* subL = parent->_left;// parent的左子节点（旋转后的新根）Node* subLR = subL->_right;// subL的右子节点（可能为空）// 旋转节点subL->_right = parent;parent->_left = subLR;// 维护父指针Node* pParent = parent->_parent;parent->_parent = subL;if (subLR) //若subLR存在,更新其父指针,避免堆空指针解引用{subLR->_parent = parent;}subL->_parent = pParent;// 维护parent的父节点if (parent == _root) // parent为根节点的情况{_root = subL;}else // parent是一棵局部子树的情况{if (pParent->_left == parent){pParent->_left = subL;}else{pParent->_right = subL;}}// 更新平衡因子subL->_bf = 0;parent->_bf = 0;}// 左单旋void RotateL(Node* parent){Node* subR = parent->_right;// parent的右子节点（旋转后的新根）Node* subRL = subR->_left;// subR的左子节点（可能为空）// 旋转节点subR->_left = parent;parent->_right = subRL;// 维护父指针Node* pParent = parent->_parent;parent->_parent = subR;if (subRL) //若subRL存在,更新其父指针,避免堆空指针解引用{subRL->_parent = parent;}subR->_parent = pParent;// 维护parent的父节点if (parent == _root) // parent为根节点的情况{_root = subR;}else // parent是一棵局部子树的情况{if (pParent->_left == parent){pParent->_left = subR;}else{pParent->_right = subR;}}// 更新平衡因子subR->_bf = 0;parent->_bf = 0;}// 左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf; // 保存旋转前的平衡因子RotateL(parent->_left); // 对subL进行左旋（处理subL的右子树过高）RotateR(parent); // 对parent进行右旋（处理parent的左子树过高）// 更新平衡因子if (bf == 0){// 此时subLR就是新增节点subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else if (bf == -1){// 此时subLR的左子节点是新增节点subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){// 此时subLR的右子节点是新增节点subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else{assert(false); // 平衡因子绝对值超过1，非法}}// 右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf; // 保存旋转前的平衡因子RotateR(parent->_right); // 对subR进行右旋（处理subR的左子树过高）RotateL(parent); // 对parent进行左旋（处理parent的右子树过高）// 更新平衡因子if (bf == 0){// 此时subRL就是新增节点subRL->_bf = 0;subR->_bf = 0;parent->_bf = 0;}else if (bf == -1){// 此时subRL的左子节点是新增节点subRL->_bf = 0;subR->_bf = 1; // 右子树高度增加parent->_bf = 0; // 左子树高度不变}else if (bf == 1){// 此时subRL的右子节点是新增节点subRL->_bf = 0;subR->_bf = 0; // 右子树高度不变parent->_bf = -1; // 左子树高度降低}else{assert(false); // 平衡因子绝对值超过1，非法}}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}int High(){return _High(_root);}bool IsBalance(){return _IsBalance(_root);}int Size(){return _Size(_root);}
private:int _Size(Node* root){if (root == nullptr) return 0;int leftSize = _Size(root->_left);int rightSize = _Size(root->_right);return leftSize + rightSize + 1;}int _High(Node* root){if (root == nullptr) return 0;int leftHigh = _High(root->_left);int rightHigh = _High(root->_right);return leftHigh > rightHigh ? leftHigh + 1 : rightHigh + 1;}bool _IsBalance(Node* root){if (root == nullptr) return true;int leftHigh = _High(root->_left);int rightHigh = _High(root->_right);int diff = rightHigh - leftHigh;if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return _IsBalance(root->_left) && _IsBalance(root->_right);}void _InOrder(Node* root){if (root == nullptr) return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}
private:Node* _root = nullptr;
};测试代码(.cpp文件)：
#include <vector>
#include "AVLTree.h"
// 测试代码
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.IsBalance() << endl;
}// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestAVLTree2()
{const int N = 100000;vector<int> v;v.reserve(N);srand((unsigned int)time(0));for (int 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.IsBalance() << endl;cout << "Height:" << t.High() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值for (auto e : v){t.Find(e);}// 随机值/*for (int i = 0; i < N; i++){t.Find((rand() + i));}*/size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}