手搓 AVL 树
0. 前言
之前的文章我们实现了二叉搜索树（BST），虽然它能在平均情况下提供不错的查找性能，但当输入数据趋于有序时，BST 会退化为链表结构，查找效率将从 O(log N) 直降为 O(N) —— 这在工程中几乎是无法接受的。
为了解决这种性能退化问题，我们引入了更'聪明'的树形结构 —— AVL 树。它通过在插入和删除过程中实时调整自身结构，让整棵树始终保持'平衡'状态，使得查找、插入、删除操作的时间复杂度都能稳定在 O(log N)。
本文将从最基础的平衡因子概念讲起，逐步实现一棵功能完整的 AVLTree<K, V> 模板类，详细剖析其核心操作：
- 插入逻辑的演化过程（从 BST 到 AVL）
- 平衡因子的更新与传播机制
- 单旋与双旋的触发与实现原理
- 旋转后平衡因子的维护策略
1. 二叉搜索树的缺陷
性能分析
- 查找 / 插入 / 删除（平均）时间复杂度：O(h)，h 为树高。
- 空间：迭代版本额外
O(1)；递归版本额外O(h)递归栈。 - 拷贝构造/Copy: O(n) 时间与 O(h) 递归栈。
结点数为 N的二叉搜索树，最多查找高度次。对于随机插入的平衡树平均 h = O(log n)；最坏情况下 h = O(n)。
- 最优情况下：⼆叉搜索树为完全⼆叉树 (或者接近完全二叉树)，其高度为：
log2 N - 最差情况下：⼆叉搜索树（退化为单链表），其高度为：
N，查找效率退化为 O(N)，这也正是二叉搜索树的缺陷
综合而言，⼆叉搜索树增删查改时间复杂度为：O(N)，这样的效率显然是⽆法满⾜我们需求的
- 今天我们来认识二叉搜索树的进阶形态——
AVL树，满足我们在内存中存储和搜索数据高性能需求。
2. 什么是 AVL 树
概念与定义
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在链表中搜索元素，效率低下。
AVL 树：是一种 自平衡二叉搜索树，由苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在 1962 年提出，其名称来源于这两位发明者的名字缩写。
AVL树是最早发明的自平衡二叉搜索树- 当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过 1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
AVL树是在普通二叉搜索树的基础上增加了平衡条件，确保树始终保持近似平衡状态AVL树要么是空树，要么是满足以下性质的二叉搜索树：- 其左、右子树也都是 AVL 树
- 左、右子树高度之差 (简称平衡因子) 的绝对值不超过 1
如果一棵二叉搜索树是高度平衡的，它就是 AVL 树。如果它有 n 个结点，其高度可保持在 O(log2 n)，搜索时间复杂度O(log2 n)
平衡因子
AVL 树是一颗高度平衡的搜索二叉树，通过控制高度差去控制平衡
AVL 树可以始终保持平衡状态，是因为在实现 AVL 树时，我们引入了 平衡因子（balance factor） 的概念：
每个节点都有一个平衡因子，其值等于该节点右子树的高度减去左子树的高度
- 因此：任何节点的平衡因子只能是 0、1 或 -1
当然平衡因子并非 AVL 树的必需属性，因为AVL 树的维持平衡不一定需要平衡因子，也可以动态计算高度或其他方法使 AVL 树保持平衡
- 使用平衡因子实现只是实现平衡的其中一种方式
但平衡因子如同一个 '风向标'：
- 可以更方便我们去观察和控制树是否平衡
- 高效控制树的平衡维护过程 —— 通过判断平衡因子是否超出
[-1, 1]范围 - 可快速定位需要调整的节点，进而通过旋转操作恢复树的平衡
以下就是一颗 AVL 树，同时附有相应的平衡因子
而下面这棵树就不是一棵 AVL 树，因为 10 这个节点它的左右子树的高度差超过了 1
基本性质
核心特点：
- 高度近似平衡：
AVL树通过不断调整树的结构，保证树的左右子树高度差始终在允许范围内，使得树的高度相对较低。- 例如：在插入或删除节点后，会通过旋转操作（左旋、右旋、左右双旋、右左双旋）来重新平衡树，从而维持高度平衡。
- 查找效率稳定：
- 由于
AVL树高度平衡，其高度近似于 O(log N)，其中 n 是节点数量，这意味着在 AVL 树中进行查找操作时，时间复杂度稳定在 O(log N) - 相比于普通二叉搜索树在最坏情况下可能退化为链表，查找时间复杂度为 O(n)，AVL 树查找效率更高且稳定
- 由于
基本操作：
- 插入：
- 新节点插入后，从插入节点开始向上检查祖先节点的平衡因子。如果发现某个节点的平衡因子绝对值超过 1，就需要进行旋转操作来恢复平衡。
- 查找：
- 按照普通二叉搜索树的查找逻辑查找，时间复杂度为 O(log N)
优缺比较：
- 优点：查找效率高且稳定，时间复杂度为 O(log N)，适用于对查找效率要求较高，且插入和删除操作相对不太频繁的场景。
- 缺点：每次插入和删除操作都可能需要进行旋转来维持平衡，这会增加额外的计算开销，导致插入和删除操作的时间复杂度比普通二叉搜索树要高一些。
为什么 AVL 树不要求左右子树的高度为 0 呢？
为什么AVL 树要求左右子树的高度差不超过 1，而非必须为 0 呢？
从平衡的理想状态看，高度差为 0 确实更平衡，但实际情况中，部分树的结构无法满足这一要求：
- 当树的节点数为 2、4 ……等特定数量时，最优的高度差只能是 1，无法强制达到 0
- 这说明
AVL树的平衡条件是在 '绝对平衡' 和 '实现可行性' 之间的权衡设计
3. AVL 树的实现
整体架构设计
AVL 树的结点定义
- AVL 树为模版实现
template<class K, class V>
struct AVLTreeNode {
pair<K, V> _kv; // 键值对
// 三叉链
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent; // 插入结点后，需要更新平衡因子，有了_parent，可以很方便的找父节点
int _balanceFactor; // balance factor 平衡因子，用于判断当前子树 有没有出现不平衡的问题
// Node 结点 的构造函数
AVLTreeNode(const pair<K, V>& kv) :
_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _balanceFactor(0) // 新结点 初始的平衡因子为 0
{}
};
- 搜索树常用于存储键值，方便查找关键字，这里我们使用
std::pair<K, V>来存储我们的键值对 - 结点中的成员变量：采用三叉链的方式实现
AVLTreeNode<K, V>* _left：指向左孩子的指针AVLTreeNode<K, V>* _right：指向右孩子的指针AVLTreeNode<K, V>* _parent：指向父节点的指针- 插入结点后，需要更新平衡因子，有了
_parent，可以很方便的找父节点
- 插入结点后，需要更新平衡因子，有了
int _balanceFactor：平衡因子，用于判断当前子树 有没有出现不平衡的问题
- 默认构造函数
AVLTreeNode(const pair<K, V>& kv)：- 将三个指针初始化为
nullptr，初始化平衡因子为 0 - 使用
kv初始化类内的_kv成员
- 将三个指针初始化为
- 结点采用
struct设计，默认权限为public，方便下文的AVLTree类访问成员
AVL 树设计
- 我们采用的设计：左右子树高度之差的绝对值 小于等于 1 (-1 0 1)
- 方便起见：我们使用 平衡因子 == 右子树的高度 - 左子树的高度
template<class K, class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
private:
AVLTreeNode<K, V>* _root = nullptr;
public:
// ... 对外共有接口
private:
// ... 内部私有成员函数
};
AVLTreeNode<K, V>* _root = nullptr：初始时根节点为空typedef AVLTreeNode<K, V> Node：结点类型重定义，简化书写
AVL 树的操作实现
插入
1. 本质
插入操作的本质是：
AVL树的插入操作是在二叉搜索树插入逻辑基础上，增加了平衡维护的关键步骤，核心要解决 '插入新节点可能破坏树的平衡，导致查询效率下降' 的问题。
2. 思路简述
插入操作思路的简述：
AVL 树插入 == 二叉搜索树插入（找位置、挂节点） + 平衡修复（更新平衡因子 + 旋转调整）
流程分 5 步：
- 空树处理：树为空时，新节点直接作为根
- 查找插入位置：从根出发，按二叉搜索树规则（小往左、大往右）找到新节点的父节点
parent，确定挂左还是挂右 - 挂载新节点：创建新节点，连接到
parent的 左 or 右 子树，并维护parent指针 - 更新平衡因子：从新节点的父节点开始，向上更新路径上所有节点的平衡因子（
_balacnFactor），反映子树高度变化 - 平衡修复：根据平衡因子判断是否失衡（绝对值 ≥ 2），若失衡则通过旋转操作（单旋 / 双旋）恢复平衡，同时更新旋转后节点的平衡因子
3. 二叉搜索树的插入逻辑
public:
bool insert(const pair<K, V>& kv) {
// 先走二叉搜索树的插入逻辑
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// _root 不为空时的操作
Node* parent = nullptr;
Node* curNode = _root;
// 先找空，找到一个可以插入的位置
while (curNode) {
if (kv.first < curNode->_kv.first) {
parent = curNode;
curNode = curNode->_left;
} else if (kv.first > curNode->_kv.first) {
parent = curNode;
curNode = curNode->_right;
} else // 搜索树中不允许有重复的值 对于已有值，不插入
return false;
}
// while 循环结束后，代表找到了可以插入的位置
// 找到位置了，但父节点不知道 新结点 比自己大还是比自己小，需要再次判断
curNode = new Node(kv);
if (curNode->_kv.first < parent->_kv.first)
parent->_left = curNode;
else
parent->_right = curNode;
curNode->_parent = parent;
// 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
// 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作 的代码
// 控制平衡 ...
}
详细讲解二叉搜索树迭代插入的逻辑）：
- 插入时，需要先找到空位置，默认插入的元素不能重复
- 空树特判：若
_root == nullptr，直接把根设为新节点（new Node(key)）。 - 否则从
_root向下查找插入位置：- 使用
curNode跟随，parent保存其父节点（因为当curNode为nullptr时需要把新节点挂到parent）。 - 如果
kv.first > curNode->_kv.first，curNode沿右子树移动；kv.first < curNode->_kv.first时，curNode沿左子树移动。 - 如果
kv.first == curNode->_kv.first，返回false（二叉搜索树默认不允许重复键）。
- 使用
- 当
curNode走到nullptr（找到空位）后，代表curNode已找到合适的可以插入的位置。 new Node(kv)建节点- 要插入新结点，必须修改
curNode的父节点内的左右孩子指针，但父节点并不知道要插入的key比自己大还是自己小，只知道下面由位置可以插入，不知道插入到哪个位置 - 因此要根据
key与parent->_key的比较把它接为左/右子节点。- 如果
curNode->_kv.first > parent->_kv.first→ 插到右边 (parent->_right = curNode) - 如果
curNode->_kv.first < parent->_kv.first→ 插到左边 (parent->_left = curNode)
- 如果
- 要插入新结点，必须修改
- 总结：✔️ 循环结束时，位置已经找到了，就是
curNode == nullptr的地方。 ✔️ 但是插入操作不能直接修改curNode，必须通过parent去改指针。 ✔️ 而parent自己并不知道空位是在左边还是右边，所以需要再比较一次来决定。
4. 更新平衡因子
1. 插入后父节点的平衡因子变化分析
-
新创建结点的平衡因子：
-
新结点插入在右：
-
新结点插入在左：
2. 平衡因子更新后的三种情况：
-
更新后平衡因子 == 0：不用继续沿着到
root的路径往上更新平衡因子 -
更新后平衡因子 == 1 or -1：继续沿着到
root的路径往上更新平衡因子 -
更新后平衡因子 == 2 or -2：树已失衡，需进行旋转
3. 更新平衡因子的最坏情况
- 更新平衡因子的最坏情况：为一路更新到根节点，因此可以使用循环控制更新，循环条件为
while(parent)
4. 更新平衡因子的代码实现
public:
bool insert(const pair<K, V>& kv) {
// ... 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
// 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作 ...
// 插入后，最坏情况时：可能 root 的平衡因子需要更新，只有 root 的 parent 为空
while (parent) {
// 插入后，先更新平衡因子
if (curNode == parent->_left)
--parent->_balanceFactor;
else // if (curNode == parent->_right)
++parent->_balanceFactor;
// 当前 parent 结点更新完了，判断是否还需要再往上更新
// 处理平衡因子更新后有三种情况
// 情况一 parent 所在子树高度不变且平衡，无需更新 和 旋转，结束循环
if (parent->_balanceFactor == 0) {
break;
}
// 情况二 parent 所在子树高度变了，继续往上更新
else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
curNode = parent;
parent = parent->_parent;
}
// 情况三 当前子树不平衡了，需要旋转
else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
// 旋转的情况和操作
}
else // 其他情况报错
assert(false);
}
// 插入结束后，return true
return true;
}
核心操作：
while (parent)
/-------------第一步：更新新插入节点的父节点的平衡因子-------------/
- 新插入节点是左子节点 —> 父节点的平衡因子
-1 - 新插入节点是右子节点 —> 父节点的平衡因子
+1
/-------------第二步：根据父节点的平衡因子做进一步的更新-------------/
- 情况 1：父节点的平衡因子为 0 —> 高度变化未影响上层，结束更新
- 情况 2：父节点的平衡因子为±1 —> 高度变化需向上传递，继续更新上层节点
- 情况 3：父节点的平衡因子为±2 —> 树失衡，需要旋转调整
- 情况 4：非法平衡因子 —> 断言失败
return true;
旋转操作
旋转的目的
- 保持搜索树的规则
- 不平衡的树变成平衡的，其次降低旋转树的高度
旋转总共分为四种：根据不同的不平衡情况我们需要采取不同的旋转方式，这些操作在插入或删除节点导致树失衡时自动触发
- 左单旋：处理 RR 型失衡
- 右单旋：处理 LL 型失衡
- 左右双旋：处理 RL 型失衡
- 右左双旋：处理 LR 型失衡
需要旋转的情况：父节点的平衡因子为±2 —> 树失衡，需要旋转调整
- 失衡 1：左左失衡（父子平衡因子都为'负'） —> 右单旋
- 失衡 2：右右失衡（父子平衡因子都为'正'） —> 左单旋
- 失衡 3：左右失衡（父为'负'，子为'正'） —> 左右双旋
- 失衡 4：右左失衡（父为'正'，子为'负'） ----> 右左双旋
- 特殊情况：非法平衡因子 —> 断言失败
一、左单旋
触发条件
- 左单旋的触发条件：
- 当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的右子树插入节点导致（即右子树的右子树深度增加，称为 'RR 型失衡'）时，需要通过左单旋恢复平衡。
左单旋原理与核心操作
核心操作：旋转过程分为三步（以节点 60(curNode) 为旋转中心，对 parent 进行左单旋）
- 先处理 curNode 的 left 结点或子树：处理
curLeft和parent的链接关系，注意curLeft可能为空 - parent 可能是整棵树的根节点，也可能是某棵树的子树
- parent 是根节点时：
curNode成为整棵树的新根，_parent指向nullptr。最后再将parent正确挂载，成为curNode的左子树 - parent 不是根节点时：需要先保存
curNode的祖父结点ppNode，判断parent 是 ppNode 的左孩子还是右孩子，再更改链接关系。最后再将parent正确挂载，成为curNode的左子树
- parent 是根节点时：
- 最后将 parent 和 curNode 的平衡因子都更改为 0
左单旋原理：
代码实现
private:
// 左单旋 2 1 newNode 练成线，单纯的右边高
void RotateL(Node* parent) {
if (parent == nullptr || parent->_right == nullptr)
return;
Node* curNode = parent->_right;
Node* curLeft = curNode->_left; // curLeft 有可能为空
// 先处理 curNode 的 left 结点，curLeft 有可能是空
parent->_right = curLeft;
if (curLeft)
curLeft->_parent = parent;
// 再处理 curNode 结点
// parent 有可能是根节点，也有可能是子树的根节点
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
parent->_parent = curNode;
curNode->_left = parent;
} else {
Node* ppNode = parent->_parent; // 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
parent->_parent = curNode;
curNode->_left = parent;
}
parent->_balanceFactor = curNode->_balanceFactor = 0;
}
二、右单旋
右单旋可以看做是左单旋的镜像操作
触发条件
- 右单旋的触发条件：
- 当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的左子树插入节点导致（即右子树的右子树深度增加，称为 'LL 型失衡'）时，需要通过右单旋恢复平衡。
右单旋原理与核心操作
核心操作：旋转过程分为三步（以节点 30(curNode) 为旋转中心，对 parent 进行右单旋）
- 先处理 curNode 的 right 结点或子树：处理
curRight和parent的链接关系，注意curRight可能为空 - parent 可能是整棵树的根节点，也可能是某棵树的子树
- parent 是根节点时：
curNode成为整棵树的新根，_parent指向nullptr。最后再将parent正确挂载，成为curNode的左子树 - parent 不是根节点时：需要先保存
curNode的祖父结点ppNode，判断parent 是 ppNode 的左孩子还是右孩子，再更改链接关系。最后再将parent正确挂载，成为curNode的右子树
- parent 是根节点时：
- 最后将 parent 和 curNode 的平衡因子都更改为 0
parent 为根节点的情况：
parent 为某棵树的子树的情况：
代码实现
private:
// 右单旋 -2 -1 newNode 连成线，单纯的左边高
void RotateR(Node* parent) {
// parent 为空 或 curNode 为空的情况
if (parent == nullptr || parent->_left == nullptr)
return;
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
// 把 curNode 的 right 给给 parent 的 left
parent->_left = curRight;
if (curRight)
curRight->_parent = parent;
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
curNode->_right = parent;
parent->_parent = curNode;
} else {
Node* ppNode = parent->_parent; // 找 parent 是 ppNode 的左还是右
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
curNode->_right = parent;
parent->_parent = curNode;
}
curNode->_balanceFactor = parent->_balanceFactor = 0;
}
三、单旋有效与失效的场景
仅单旋有效的场景总结：
单旋失效场景总结：
四、双旋的分析
双旋的简单样例
双旋的本质
双旋后平衡因子的更新
- 双旋平衡因子的更新分为三种情况讨论，以下为左右双旋的场景：
- 双旋的核心操作不在于旋转，因为双旋只是左单旋和右单旋的简单组合
- 双旋的核心操作在于旋转后平衡因子的更新
五、左右双旋
触发条件
- 左右双旋的触发条件：折线的拐角在左边
- 当 AVL 树中某个节点的左子树高度比右子树高度大 2，且失衡是由左子树的右子树插入节点导致（即左子树的右子树深度增加，称为 'LR 型失衡' ）时，需要通过左右双旋恢复平衡。
- 左右双旋是 左单旋 + 右单旋 的复合操作，专门处理 LR 型失衡
- 左右双旋通过 '先左旋修正左子树方向，再右旋整体平衡' 的两步操作，解决 LR 型失衡问题
左右双旋的过程以及平衡因子的更新：
代码实现
关键操作：
- 对
cur结点进行左旋 - 再对
parent结点进行右旋 - 最终
curRight结点成为树的新根 - 旋转完后进行平衡因子的更新
// 左右双旋
void RotateLR(Node* parent) {
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
int bf_curRight = curRight->_balanceFactor;
// 旋转
RotateL(parent->_left);
RotateR(parent);
// 双旋 这里的麻烦事 是平衡因子的更新
// 更新平衡因子
if (bf_curRight == 0) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 0;
curRight->_balanceFactor = 0;
} else if (bf_curRight == 1) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = -1;
curRight->_balanceFactor = 0;
} else if (bf_curRight == -1) {
parent->_balanceFactor = 1;
curNode->_balanceFactor = 0;
curRight->_balanceFactor = 0;
} else
assert(false);
}
六、右左双旋
右左双旋可以看做是左右双旋的镜像操作，二者可以看作是一个对称的关系。当插入节点在不平衡节点的右子树的左边时，可以记作右左型 (RL 型)，此时采用右左双旋的方法去调整平衡，即先对不平衡节点的右子树进行一次右单旋，之后再对不平衡节点为根的子树进行一次左单旋。
触发条件
- 右左双旋的触发条件：折线的拐角在右边
- 当 AVL 树中某个节点的右子树高度比左子树高度大 2，且失衡是由右子树的左子树插入节点导致（即右子树的左子树深度增加，称为 'RL 型失衡' ）时，需要通过右左双旋恢复平衡。
- 左双旋是 右单旋 + 左单旋 的复合操作，专门处理RL 型失衡
- 右左双旋通过 '先右旋修正右子树方向，再左旋整体平衡' 的两步操作，解决 RL 型失衡问题
右左双旋的过程以及平衡因子的更新：
代码实现
关键操作：
- 对
cur结点进行右旋 - 再对
parent结点进行左旋 - 最终
curLeft结点成为树的新根 - 旋转完后进行平衡因子的更新
// 右左双旋 parent 的平衡因子为 2 或 -2
void RotateRL(Node* parent) {
Node* curNode = parent->_right;
Node* curLeft = curNode->_left;
int bf_curLeft = curLeft->_balanceFactor;
// 旋转
RotateR(parent->_right);
RotateL(parent);
// 双旋 这里的麻烦事 是平衡因子的更新
// 更新平衡因子
if (bf_curLeft == 0) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 0;
curLeft->_balanceFactor = 0;
} else if (bf_curLeft == 1) {
parent->_balanceFactor = -1;
curNode->_balanceFactor = 0;
curLeft->_balanceFactor = 0;
} else if (bf_curLeft == -1) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 1;
curLeft->_balanceFactor = 0;
} else
assert(false);
}
插入的总结与完整代码
总结流程：
- 空树处理：树为空时，新节点直接作为根
- 查找插入位置：从根出发，按二叉搜索树规则（小往左、大往右）找到新节点的父节点
parent，确定挂左还是挂右 - 挂载新节点：创建新节点，连接到
parent的 左 or 右 子树，并维护parent指针 - 更新平衡因子：从新节点的父节点开始，向上更新路径上所有节点的平衡因子（
_balacnFactor），反映子树高度变化 - 平衡修复：根据平衡因子判断是否失衡（绝对值 ≥ 2），若失衡则通过旋转操作（单旋 / 双旋）恢复平衡，同时更新旋转后节点的平衡因子
- 右单旋：处理 LL 型失衡
- 左单旋：处理 RR 型失衡
- 左右双旋：处理 RL 型失衡
- 右左双旋：处理 LR 型失衡
完整插入代码
public:
bool insert(const pair<K, V>& kv) {
// 先走二叉搜索树的插入逻辑
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// _root 不为空时，二叉搜索树的逻辑
Node* parent = nullptr;
Node* curNode = _root;
// 先找空，找到一个可以插入的位置
while (curNode) {
if (kv.first < curNode->_kv.first) {
parent = curNode;
curNode = curNode->_left;
} else if (kv.first > curNode->_kv.first) {
parent = curNode;
curNode = curNode->_right;
} else // 搜索树中不允许有重复的值 对于已有值，不插入
return false;
}
// while 循环结束后，代表找到了可以插入的位置
// 找到位置了，但父节点不知道 新结点比自己大还是比自己小
curNode = new Node(kv);
if (curNode->_kv.first < parent->_kv.first) {
parent->_left = curNode;
} else {
parent->_right = curNode;
}
curNode->_parent = parent;
// 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
// 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作
// 控制平衡 ...
// 插入后，先更新平衡因子
// 插入后，最坏情况时：可能 root 的平衡因子需要更新，只有 root 的 parent 为空
while (parent) {
// 更新平衡因子
if (curNode == parent->_left)
--parent->_balanceFactor;
else // if (curNode == parent->_right)
++parent->_balanceFactor;
// 当前 parent 结点更新完了，判断是否还需要再往上更新
// 处理平衡因子更新后有三种情况
// 情况一 parent 所在子树高度不变且平衡，无需更新 和 旋转 结束循环
if (parent->_balanceFactor == 0) {
break;
}
// 情况二 parent 所在子树高度变了，继续往上更新
else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
curNode = parent;
parent = parent->_parent;
}
// 情况三 当前子树不平衡了，需要旋转
else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
// 左单旋'右子树右高'的一种情况
// 2 1 newNode 排成直线，单纯的右边高，进行 左单旋
// 2 -> 右高，1 -> 右高，右右 左单旋
if (parent->_balanceFactor == 2 && curNode->_balanceFactor == 1) {
RotateL(parent);
}
// -2 -1 newNode 排成直线，单纯的右边高，进行，右单旋
// -2 -> 左高，-1 -> 左高，左左 右单旋
else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == -1) {
RotateR(parent);
}
// 2 -1 newNode 排成折线 右左双旋
else if (parent->_balanceFactor == 2 && curNode->_balanceFactor == -1) {
RotateRL(parent);
}
// -2 1 newNode 排成折线 左右双旋
else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == 1) {
RotateLR(parent);
} else {
assert(false);
}
// 旋转后，让这棵树平衡，且降低了这棵树的高度，
// 旋转后 就无需再更新平衡因子了，可以跳出循环
break;
} else {
assert(false); // 平衡因子不是 0 1 -1 2 -2 直接报错
}
}
return true;
}
AVL 树的删除
AVL 树的删除操作这里不做重点讲解，这个操作会比插入稍复杂一些，但核心思路依然是走正常的二叉搜索树的删除操作 + 更新平衡因子 + 失衡时进行旋转
只不过与二叉搜索树删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。
具体实现可参考《算法导论》或《数据结构 - 用面向对象方法与 C++ 描述》殷人昆版
4. 验证操作
求树的高度
求树的高度思路如下：
- 先分别求树的左右子树高度
- 最终返回左右子树中 高度更大的高度 + 1
public:
int Height(Node* root) {
if (root == nullptr)
return 0;
// 分别求左右子树的高度
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
// 左右子树中 高度更大的那个 + 1
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
判断树是否是 AVL 平衡树
- 先分别求树的左右子树高度
- AVL 平衡树的条件：
- 当前树是 AVL 树：
abs(rightHeight - leftHeight) < 2 &&- 左右子树也都是 AVL 树：
_IsBalance(root->_left) && _IsBalance(root->_right);
- 左右子树也都是 AVL 树：
- 当前树是 AVL 树：
public:
// 判断是否是 AVL 树
bool isBalance() {
return _IsBalance(_root);
}
private:
bool _IsBalance(Node* root) {
if (root == nullptr)
return true;
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
// 加一层保障
if (rightHeight - leftHeight != root->_balanceFactor) {
cout << " 平衡因子异常：" << root->_kv.first << "->" << root->_balanceFactor << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}
测试 AVL 树的正确性
- 使用
20000000个随机数测试
void test() {
const int N = 20000000;
vector<int> v;
v.reserve(N);
srand(time(0));
AVLTree<int, int> t;
for (size_t i = 0; i < N; ++i)
v.push_back(rand());
for (auto e : v)
t.insert(make_pair(e, e));
cout << t.isBalance() << endl;
}
int main() {
test();
return 0;
}
4. 完整代码实现
#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; // 插入结点后，需要更新平衡因子，有了_parent，可以很方便的找父节点
// 平衡因子，用于判断当前子树 有没有出现不平衡的问题
int _balanceFactor; // balance factor 平衡因子
// Node 的构造函数
AVLTreeNode(const pair<K, V>& kv) :
_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _balanceFactor(0) // 新结点 初始的平衡因子为 0
{}
// 我们使用 平衡因子 = 右子树的高度 - 左子树的高度
// AVL 树的实现不是一定需要平衡因子，也可以动态的计算高度来判断
// 使用平衡因子实现只是其中一种方式
};
// 左右子树高度之差的绝对值 小于等于 1 (-1 0 1)
template<class K, class V>
class AVLTree {
typedef AVLTreeNode<K, V> Node;
private:
AVLTreeNode<K, V>* _root = nullptr;
public:
bool insert(const pair<K, V>& kv) {
// 先走二叉搜索树的插入逻辑
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
// _root 不为空时，二叉搜索树的逻辑
Node* parent = nullptr;
Node* curNode = _root;
// 先找空，找到一个可以插入的位置
while (curNode) {
if (kv.first < curNode->_kv.first) {
parent = curNode;
curNode = curNode->_left;
} else if (kv.first > curNode->_kv.first) {
parent = curNode;
curNode = curNode->_right;
} else // 搜索树中不允许有重复的值 对于已有值，不插入
return false;
}
// while 循环结束后，代表找到了可以插入的位置
// 找到位置了，但父节点不知道 新结点比自己大还是比自己小
curNode = new Node(kv);
if (curNode->_kv.first < parent->_kv.first) {
parent->_left = curNode;
} else {
parent->_right = curNode;
}
curNode->_parent = parent;
// 以上是二叉搜索树的插入逻辑，这样插入可能导致树不平衡，从而导致查找效率退化为 O(n)
// 以下是 AVL 树对二叉搜索树 进行的 控制平衡 操作
// 控制平衡 ...
// 插入后，先更新平衡因子
// 插入后，最坏情况时：可能 root 的平衡因子需要更新，只有 root 的 parent 为空
while (parent) {
// 更新平衡因子
if (curNode == parent->_left)
--parent->_balanceFactor;
else // if (curNode == parent->_right)
++parent->_balanceFactor;
// 当前 parent 结点更新完了，判断是否还需要再往上更新
// 处理平衡因子更新后有三种情况
// 情况一 parent 所在子树高度不变且平衡，无需更新 和 旋转 结束循环
if (parent->_balanceFactor == 0) {
break;
}
// 情况二 parent 所在子树高度变了，继续往上更新
else if (parent->_balanceFactor == 1 || parent->_balanceFactor == -1) {
curNode = parent;
parent = parent->_parent;
}
// 情况三 当前子树不平衡了，需要旋转
else if (parent->_balanceFactor == 2 || parent->_balanceFactor == -2) {
// 左单旋'右子树右高'的一种情况
// 2 1 newNode 排成直线，单纯的右边高，进行 左单旋
// 2 -> 右高，1 -> 右高，右右 左单旋
if (parent->_balanceFactor == 2 && curNode->_balanceFactor == 1) {
RotateL(parent);
}
// -2 -1 newNode 排成直线，单纯的右边高，进行，右单旋
// -2 -> 左高，-1 -> 左高，左左 右单旋
else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == -1) {
RotateR(parent);
}
// 2 -1 newNode 排成折线 右左双旋
else if (parent->_balanceFactor == 2 && curNode->_balanceFactor == -1) {
RotateRL(parent);
}
// -2 1 newNode 排成折线 左右双旋
else if (parent->_balanceFactor == -2 && curNode->_balanceFactor == 1) {
RotateLR(parent);
} else {
assert(false);
}
// 旋转后，让这棵树平衡，且降低了这棵树的高度，
// 旋转后 就无需再更新平衡因子了，可以跳出循环
break;
} else {
assert(false); // 平衡因子不是 0 1 -1 2 -2 直接报错
}
}
return true;
}
// 判断是否是 AVL 树
bool isBalance() {
return _IsBalance(_root);
}
private:
bool _IsBalance(Node* root) {
if (root == nullptr)
return true;
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
// 加一层保障
if (rightHeight - leftHeight != root->_balanceFactor) {
cout << " 平衡因子异常：" << root->_kv.first << "->" << root->_balanceFactor << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}
int Height(Node* root) {
if (root == nullptr)
return 0;
// 分别求左右子树的高度
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
// 左右子树中 高度更大的那个 + 1
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 左单旋 复习版
void RotateL_review(Node* parent) {
if (parent == nullptr || parent->_right == nullptr)
return;
Node* curNode = parent->_right;
Node* curLeft = curNode->_left;
parent->_right = curLeft;
if (curLeft) // curLeft 可能为空
curLeft->_parent = parent;
// parent 可能是根节点，也可能是一颗子树
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
parent->_parent = curNode;
curNode->_left = parent;
} else {
Node* ppNode = parent->_parent; // 先立新根
// 这里不知道 parent 是 ppNode 的左 还是右
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 再挂 parent
parent->_parent = curNode;
curNode->_left = parent;
}
parent->_balanceFactor = curNode->_balanceFactor = 0;
}
// 左单旋 2 1 newNode 练成线，单纯的右边高
void RotateL(Node* parent) {
if (parent == nullptr || parent->_right == nullptr)
return;
Node* curNode = parent->_right;
Node* curLeft = curNode->_left; // curLeft 有可能为空
// 先处理 curNode 的 left 结点，curLeft 有可能是空
parent->_right = curLeft;
if (curLeft)
curLeft->_parent = parent;
// 再处理 curNode 结点
// parent 有可能是根节点，也有可能是子树的根节点
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
parent->_parent = curNode;
curNode->_left = parent;
} else {
Node* ppNode = parent->_parent; // 这里不知道 parent 是 ppNode 的 左孩子 还是 右孩子
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
parent->_parent = curNode;
curNode->_left = parent;
}
parent->_balanceFactor = curNode->_balanceFactor = 0;
}
// 右单旋 -2 -1 newNode 连成线，单纯的左边高
void RotateR(Node* parent) {
// parent 为空 或 curNode 为空的情况
if (parent == nullptr || parent->_left == nullptr)
return;
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
// 把 curNode 的 right 给给 parent 的 left
parent->_left = curRight;
if (curRight)
curRight->_parent = parent;
if (parent == _root) {
// 先立新根
_root = curNode;
curNode->_parent = nullptr;
// 再挂旧根
curNode->_right = parent;
parent->_parent = curNode;
} else {
Node* ppNode = parent->_parent; // 找 parent 是 ppNode 的左还是右
if (parent == ppNode->_left)
ppNode->_left = curNode;
else
ppNode->_right = curNode;
curNode->_parent = ppNode;
// 挂 parent
curNode->_right = parent;
parent->_parent = curNode;
}
curNode->_balanceFactor = parent->_balanceFactor = 0;
}
// 右左双旋 parent 的平衡因子为 2 或 -2
void RotateRL(Node* parent) {
Node* curNode = parent->_right;
Node* curLeft = curNode->_left;
int bf_curLeft = curLeft->_balanceFactor;
// 旋转
RotateR(parent->_right);
RotateL(parent);
// 双旋 这里的麻烦事 是平衡因子的更新
// 更新平衡因子
if (bf_curLeft == 0) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 0;
curLeft->_balanceFactor = 0;
} else if (bf_curLeft == 1) {
parent->_balanceFactor = -1;
curNode->_balanceFactor = 0;
curLeft->_balanceFactor = 0;
} else if (bf_curLeft == -1) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 1;
curLeft->_balanceFactor = 0;
} else
assert(false);
}
// 左右双旋
void RotateLR(Node* parent) {
Node* curNode = parent->_left;
Node* curRight = curNode->_right;
int bf_curRight = curRight->_balanceFactor;
// 旋转
RotateL(parent->_left);
RotateR(parent);
// 双旋 这里的麻烦事 是平衡因子的更新
// 更新平衡因子
if (bf_curRight == 0) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = 0;
curRight->_balanceFactor = 0;
} else if (bf_curRight == 1) {
parent->_balanceFactor = 0;
curNode->_balanceFactor = -1;
curRight->_balanceFactor = 0;
} else if (bf_curRight == -1) {
parent->_balanceFactor = 1;
curNode->_balanceFactor = 0;
curRight->_balanceFactor = 0;
} else
assert(false);
}
};
5. 结语
从最初的二叉搜索树到 AVL 树，我们一步步地走完了'从失衡到平衡'的进化历程。
AVL 树通过平衡因子 + 旋转操作巧妙地在插入、删除之间保持树的高度稳定，让查找性能始终维持在对数级别。
它是现代平衡树结构（如红黑树、Treap、B 树等）的理论基石，也让我们深刻理解了'以空间换时间'、'以维护换性能'的设计哲学。
虽然 AVL 树在插入删除时的维护成本略高，但在查找密集的场景中，它的稳定性与高效性仍然无可替代。
希望这篇文章能帮助你彻底理解平衡二叉树的核心思想，为你后续深入学习红黑树、STL map/set 底层实现打下坚实的基础。