C++ AVL 树详解（一）：平衡因子、树高控制与插入过程
C++ AVL 树详解（一）：平衡因子、树高控制与插入过程
文章目录
前言
普通二叉搜索树通过下面的规则组织数据：
左子树中的关键字小于根
右子树中的关键字大于根
左右子树仍然是二叉搜索树
借助这个规则，我们可以根据关键字大小决定向左还是向右查找。
但是，普通二叉搜索树有一个明显的问题：
它只规定了关键字之间的大小关系，却没有限制树的形状。
假设依次插入：
1 2 3 4 5 6 7
查找 7 时，需要依次经过：
1 → 2 → 3 → 4 → 5 → 6 → 7
时间复杂度从理想状态下的：
O(log N)
退化成：
O(N)
AVL 树就是为了解决这个问题而出现的。
本文按照下面的顺序，自下而上构建 AVL 树知识体系：
普通二叉搜索树
↓
树高决定操作效率
↓
限制左右子树高度差
↓
引入平衡因子
↓
按照 BST 规则插入
↓
沿祖先路径更新平衡因子
↓
发现不平衡结点
↓
通过旋转恢复平衡
本篇先重点讲解 AVL 树的基础概念和插入过程。四种旋转及完整代码将在下一篇展开。
一、普通二叉搜索树为什么会退化？
1.1 二叉搜索树的复杂度取决于树高
在二叉搜索树中，查找过程只沿着一条路径向下移动。
例如查找 13：
8
/ \
3 14
/
13
查找路径为：
8 → 14 → 13
如果树高为 h，查找、插入和删除的时间复杂度通常可以统一表示为：
O(h)
所以，二叉搜索树性能的关键不是结点总数本身，而是树高。
1.2 接近平衡时
假设树的结点分布较均匀：
4
/ \
2 6
/ \ / \
1 3 5 7
7 个结点只需要 3 层。
树高约为：
log₂N
查找效率接近：
O(log N)
1.3 退化时
如果树变成：
1
\
2
\
3
\
4
4 个结点需要 4 层。
树高约为：
N
操作复杂度就会退化为：
O(N)
因此，要让二叉搜索树获得稳定性能，就必须主动控制树高。
二、什么是 AVL 树？
AVL 树是一种自平衡二叉搜索树。
一棵树是 AVL 树，需要同时满足：
1. 它首先是一棵二叉搜索树
2. 左子树是 AVL 树
3. 右子树是 AVL 树
4. 任意结点左右子树高度差的绝对值不超过 1
用公式表示：
|右子树高度 - 左子树高度| <= 1
例如：
8
/ \
3 10
/ \ \
1 6 14
/ \
4 7
站在结点 6 上：
左子树高度 = 1
右子树高度 = 1
高度差 = 0
站在结点 3 上：
左子树高度 = 1
右子树高度 = 2
高度差 = 1
站在根结点 8 上：
左子树高度 = 3
右子树高度 = 2
高度差 = -1
所有结点的高度差绝对值都不超过 1，因此这是一棵 AVL 树。
三、为什么高度差允许为 1，而不是必须为 0？
乍一看，左右子树高度完全相等似乎更加平衡。
但是，这种要求并不总能实现。
3.1 两个结点无法做到高度差为 0
例如只有两个结点：
8
/
3
根结点的：
左子树高度 = 1
右子树高度 = 0
高度差只能是：
-1
无论把 3 放在左边还是右边，都无法让高度差变成 0。
3.2 四个结点也无法让所有结点完全等高
例如：
3
/ \
2 4
/
1
根结点左右子树高度差为 1。
这已经是四个结点能够获得的较好结构。
因此，AVL 树采用：
高度差绝对值不超过 1
而不是：
高度差必须等于 0
这种规则既能够限制树高，也允许树存储任意数量的结点。
四、平衡因子是什么？
为了更加方便地判断一棵树是否平衡，可以为每个结点记录一个平衡因子。
本文采用的定义是：
平衡因子 = 右子树高度 - 左子树高度
英文通常写作：
balance factor
代码成员可以命名为：
int _bf;
4.1 三种合法的平衡因子
对于 AVL 树中的任意结点，合法平衡因子只能是：
-1
0
1
具体含义如下：
| 平衡因子 | 含义 |
|---|---|
-1 | 左子树比右子树高 1 |
0 | 左右子树一样高 |
1 | 右子树比左子树高 1 |
如果出现：
-2
说明左子树比右子树高 2，结点失衡。
如果出现：
2
说明右子树比左子树高 2，结点失衡。
4.2 平衡因子的正负方向不是统一规定
有些资料定义：
左子树高度 - 右子树高度
本文和课程资料采用：
右子树高度 - 左子树高度
两种定义都可以。
关键是：
一套代码中必须始终使用同一种定义。
如果定义是右减左，那么：
插入左子树：平衡因子减一
插入右子树：平衡因子加一
如果定义反过来，后续所有更新和旋转判断都要反过来。
五、为什么 AVL 树高度是对数级？
AVL 树不会要求每一层全部填满，但它严格限制任意结点左右子树高度差不超过 1。
假设一棵高度为 h 的 AVL 树结点数尽可能少。
为了让树在满足 AVL 条件的情况下尽可能高，它的两棵子树高度应分别为：
h - 1
h - 2
因此最少结点数量满足：
N(h) = N(h - 1) + N(h - 2) + 1
这与斐波那契数列的增长方式相近。
斐波那契数列随高度呈指数增长，因此反过来看：
高度随结点数量呈对数增长
也就是：
h = O(log N)
因此 AVL 树中的查找、插入和删除可以稳定在：
O(log N)
需要注意：
AVL 树并不一定是完全二叉树，但它的高度与完全二叉树处于同一数量级。
六、AVL 树结点应该保存什么？
我们这里使用的是 key/value 模型：
key 用来比较和定位
value 保存 key 对应的数据
一个 AVL 树结点可以定义为：
#include <utility>
template<class K, class V>
struct AVLTreeNode
{
std::pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
explicit AVLTreeNode(
const std::pair<K, V>& kv)
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{
}
};
6.1 _kv
std::pair<K, V> _kv;
其中：
_kv.first 是 key
_kv.second 是 value
树的大小关系由：
_kv.first
决定。
6.2 _left 和 _right
Node* _left;
Node* _right;
分别指向左孩子和右孩子。
它们用于维护二叉搜索树结构。
6.3 _parent
Node* _parent;
指向父结点。
AVL 树插入新结点以后，需要从新结点开始不断向根更新祖先结点的平衡因子。
有了父指针，就可以写成：
parent = parent->_parent;
逐层向上移动。
6.4 _bf
int _bf;
记录当前结点的平衡因子：
右子树高度 - 左子树高度
新创建的叶子结点左右子树都为空，所以：
_bf = 0
七、AVL 树插入的整体过程
AVL 树插入可以分成四个阶段。
阶段一：按照二叉搜索树规则找到位置
key 小于当前 key：向左
key 大于当前 key：向右
key 等于当前 key：插入失败
阶段二：创建并连接新结点
新结点一定插入到空位置，因此刚插入时一定是叶子结点：
左孩子为空
右孩子为空
平衡因子为 0
阶段三：沿祖先路径更新平衡因子
新增叶子可能使某些祖先子树高度增加。
因此需要从新结点的父亲开始向上更新：
新结点
↓
父结点
↓
祖父结点
↓
更高祖先
↓
根结点
阶段四：遇到失衡结点时进行旋转
当某个祖先的平衡因子变成：
-2 或 2
说明该结点失衡。
此时根据新结点的插入方向选择：
右单旋
左单旋
左右双旋
右左双旋
旋转完成后，插入结束。
八、先按照二叉搜索树规则插入
8.1 查找插入位置
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
parent = cur;
if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else
{
return false;
}
}
循环结束时：
cur == nullptr
parent 指向新结点的父结点
8.2 创建结点
cur = new Node(kv);
cur->_parent = parent;
8.3 连接到父结点
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
到这里为止，执行的是普通二叉搜索树插入。
接下来才是 AVL 树特有的平衡维护。
九、为什么只更新祖先结点？
插入一个新叶子后，不是整棵树的高度都可能改变。
假设新结点插入在下面的位置：
8
/ \
3 10
/ \
1 6
\
7 ← 新结点
新结点 7 只可能影响：
6
3
8
因为它们是 7 的祖先。
结点 1、10 以及其他无关子树没有发生任何变化。
所以 AVL 树只需要沿着：
新结点到根
这条路径更新平衡因子。
这也是为什么结点中保存 _parent 会使代码更加方便。
十、平衡因子怎样更新？
假设：
cur 是刚刚高度发生变化的子树根
parent 是 cur 的父结点
10.1 cur 位于 parent 左边
左子树高度增加，所以：
右子树高度 - 左子树高度
会减少 1。
代码为：
if (cur == parent->_left)
{
--parent->_bf;
}
10.2 cur 位于 parent 右边
右子树高度增加，所以平衡因子增加 1：
else
{
++parent->_bf;
}
完整更新代码：
if (cur == parent->_left)
{
--parent->_bf;
}
else
{
++parent->_bf;
}
更新以后，关键问题不是只看结点是否平衡，还要判断：
parent 所在子树的整体高度是否发生了变化。
这个结果决定了是否继续向上更新。
十一、更新后的三种情况
更新一个祖先结点后，平衡因子可能变成：
0
1 或 -1
2 或 -2
它们分别对应三种不同处理方式。
11.1 平衡因子变成 0：停止更新
例如原来：
parent._bf = 1
表示右边比左边高 1。
现在新结点插入左边：
1 → 0
结构可以理解为：
插入前：右高左低
插入后：左右等高
虽然较低的一边高度增加了，但 parent 所在整棵子树的总高度没有增加。
因此不会影响 parent 的父结点。
代码：
if (parent->_bf == 0)
{
break;
}
结论：
更新后为 0
→ 当前子树总高度不变
→ 不再影响更高祖先
→ 停止更新
11.2 平衡因子变成 1 或 -1：继续向上
例如原来：
parent._bf = 0
新结点插入右边后：
0 → 1
原来左右子树一样高，现在右边高 1。
虽然 parent 仍然满足 AVL 条件，但 parent 所在子树的总高度增加了 1。
这可能继续影响 parent 的父结点。
代码：
else if (parent->_bf == 1 ||
parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
结论：
更新后为 ±1
→ 当前结点仍然平衡
→ 当前子树高度增加
→ 继续影响更高祖先
→ 向上更新
11.3 平衡因子变成 2 或 -2：执行旋转
例如：
1 → 2
表示原本右边已经高 1，新结点又插入到较高的右侧。
此时右边比左边高 2，违反 AVL 条件。
同理：
-1 → -2
表示左边比右边高 2。
代码框架：
else if (parent->_bf == 2 ||
parent->_bf == -2)
{
// 根据具体形态选择旋转
}
十二、为什么插入旋转后可以停止向上更新？
插入前，失衡结点所在子树是平衡的。
插入新结点后，它的高度增加了 1，因此影响上层祖先。
旋转的目标不仅是让左右高度差重新不超过 1，还要让这棵局部子树的高度恢复到插入前的高度。
可以表示为：
插入前高度：h
插入后失衡：h + 1
旋转后高度：h
既然旋转后局部子树高度恢复了，它就不会继续影响上一层祖先。
因此，AVL 插入中通常只需要修复从新结点向上遇到的第一个失衡祖先。
需要注意：
这是 AVL 插入的特点。AVL 删除后，子树高度可能继续降低，可能需要沿路径执行多次调整。
十三、如何判断属于哪一种旋转？
设：
parent 是第一个失衡结点
cur 是 parent 路径上较高的孩子
本文采用：
平衡因子 = 右高 - 左高
插入时可以根据下面的组合选择旋转。
| parent 平衡因子 | cur 平衡因子 | 失衡类型 | 处理方式 |
|---|---|---|---|
-2 | -1 | 左左型 LL | 右单旋 |
2 | 1 | 右右型 RR | 左单旋 |
-2 | 1 | 左右型 LR | 左右双旋 |
2 | -1 | 右左型 RL | 右左双旋 |
可以先用一句话记忆：
同方向：单旋
不同方向：双旋
例如：
parent 左边高
cur 也左边高
属于左左型，执行右单旋。
如果：
parent 左边高
cur 却右边高
属于左右型，需要先左旋，再右旋。
十四、AVL 插入框架代码
下面给出插入过程的主体框架，各位同学可以先自己尝试着实现一下
四种旋转函数在下一篇中完整实现。
#include <cassert>
#include <utility>
template<class K, class V>
struct AVLTreeNode
{
std::pair<K, V> _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;
explicit AVLTreeNode(
const std::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 std::pair<K, V>& kv)
{
// 1. 空树直接创建根结点
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
// 2. 按照 BST 规则查找插入位置
Node* parent = nullptr;
Node* cur = _root;
while (cur != nullptr)
{
parent = cur;
if (kv.first < cur->_kv.first)
{
cur = cur->_left;
}
else if (cur->_kv.first < kv.first)
{
cur = cur->_right;
}
else
{
return false;
}
}
// 3. 创建并连接新结点
cur = new Node(kv);
cur->_parent = parent;
if (kv.first < parent->_kv.first)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
// 4. 沿祖先路径更新平衡因子
while (parent != nullptr)
{
if (cur == parent->_left)
{
--parent->_bf;
}
else
{
++parent->_bf;
}
// 子树高度不变，停止更新
if (parent->_bf == 0)
{
break;
}
// 子树仍然平衡，但高度增加，继续向上
if (parent->_bf == -1 ||
parent->_bf == 1)
{
cur = parent;
parent = parent->_parent;
continue;
}
// 发现失衡结点
if (parent->_bf == -2)
{
if (cur->_bf == -1)
{
RotateR(parent);
}
else if (cur->_bf == 1)
{
RotateLR(parent);
}
else
{
assert(false);
}
}
else if (parent->_bf == 2)
{
if (cur->_bf == 1)
{
RotateL(parent);
}
else if (cur->_bf == -1)
{
RotateRL(parent);
}
else
{
assert(false);
}
}
else
{
assert(false);
}
// 插入旋转后，局部子树高度恢复
break;
}
return true;
}
private:
void RotateR(Node* parent);
void RotateL(Node* parent);
void RotateLR(Node* parent);
void RotateRL(Node* parent);
private:
Node* _root = nullptr;
};
十五、插入过程手算示例
依次插入：
10 5 3
15.1 插入 10
10
平衡因子：
10._bf = 0
15.2 插入 5
10
/
5
5 插入在 10 左边：
10._bf：0 → -1
当前结点仍平衡，但子树高度增加，更新到根后结束。
15.3 插入 3
10
/
5
/
3
先更新 5：
5._bf：0 → -1
继续向上。
再更新 10：
10._bf：-1 → -2
结点 10 失衡。
由于：
10 左边高
5 也左边高
这是左左型：
LL
需要执行右单旋。
旋转后：
5
/ \
3 10
三个结点平衡因子都恢复为 0。
十六、AVL 树插入复杂度
16.1 查找插入位置
AVL 树高度为：
O(log N)
所以寻找插入位置需要：
O(log N)
16.2 更新平衡因子
最坏情况下需要从新结点一直更新到根：
O(log N)
16.3 执行旋转
单旋只修改常数个结点和指针：
O(1)
双旋由两次单旋组成：
O(1)
所以 AVL 插入的总时间复杂度为：
O(log N)
结点额外保存：
_parent
_bf
每个结点只增加常数空间，因此整棵树额外空间仍为：
O(N)
十七、常见错误整理
17.1 平衡因子方向前后不一致
本文规定：
右子树高度 - 左子树高度
所以：
左边插入：--
右边插入：++
如果前面使用右减左，后面却按照左减右判断旋转，代码一定会出错。
17.2 只看平衡因子，不看子树高度是否变化
平衡因子更新为：
0
意味着当前子树总高度没有增加，应立即停止。
平衡因子更新为：
±1
虽然仍平衡，但子树高度增加，需要继续向上。
17.3 从根向下更新平衡因子
插入影响的是新结点的祖先，应当从新结点向根更新。
从根向下很难判断究竟哪一侧高度发生变化。
17.4 忘记维护 parent 指针
新结点插入后必须写：
cur->_parent = parent;
旋转过程中也必须同步修改父指针。
否则向上更新和后续操作都会出现悬空关系或错误路径。
17.5 发现第一个失衡结点后仍继续向上更新
AVL 插入旋转后，局部子树高度恢复到插入前，因此可以结束。
继续使用旧的 parent 和 cur 更新，反而可能破坏平衡因子。
17.6 认为 AVL 树一定是完全二叉树
AVL 树只保证：
任意结点左右子树高度差不超过 1
它不要求最后一层从左到右连续排列，因此不一定是完全二叉树。
17.7 认为所有平衡因子都必须是 0
AVL 树允许：
-1
0
1
平衡不等于左右子树必须完全等高。
十八、把所有知识点串起来
现在重新从普通二叉搜索树开始。
18.1 二叉搜索树提供有序性
左边小
右边大
因此可以定向查找。
18.2 但普通 BST 不控制树高
有序插入可能让树退化成单链表。
树高从：
O(log N)
增长到：
O(N)
18.3 AVL 增加高度约束
规定任意结点：
|右子树高度 - 左子树高度| <= 1
从而防止树严重倾斜。
18.4 平衡因子记录倾斜方向
bf = 右高 - 左高
-1：左边略高
0 ：两边等高
1 ：右边略高
18.5 插入仍然先按照 BST 规则进行
AVL 树并没有改变关键字之间的顺序。
新结点仍然通过比较 key 插入到叶子位置。
18.6 新结点只影响祖先路径
所以从新结点父亲开始，不断向根更新平衡因子。
18.7 根据更新结果决定下一步
bf == 0
→ 子树高度不变
→ 停止
bf == ±1
→ 子树高度增加
→ 继续向上
bf == ±2
→ 子树失衡
→ 执行旋转
18.8 旋转恢复局部高度
旋转既要保持：
二叉搜索树的有序性
又要恢复：
AVL 的高度平衡
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
16
0- 0
已为社区贡献27条内容
所有评论(0)