【C++】AVL 树如何自动保持平衡？四种旋转、平衡因子更新与完整代码实战
C++ AVL 树详解
文章目录
上一篇笔记我们走完了关联式容器 map、set 的全貌：set 是 K 模型的去重加排序容器，map 用 pair 键值对实现 KV 模型，multiset 与 multimap 放开键值冗余，map 的 operator[] 凭借 insert 的返回值实现了"不存在则插入、存在则查找"的复合功能。笔记末尾引出了关联式容器的底层铺垫：二叉搜索树在极端情况下会退化成一条链，查找变成 O(n)，于是需要 平衡搜索树来兜底， AVL 树就是其中最早的一种。当时我们只给出了 AVL 树的概念、平衡因子的定义和插入后的更新规则，三叉链的节点结构也搭好了，但真正让树恢复平衡的旋转操作还没写。这篇笔记要把 AVL 树剩下的部分一次讲完：四种旋转为什么要这样旋、代码怎么实现、双旋的平衡因子为什么分三种情况、以及如何严谨地验证一棵树真的平衡。旋转是这套知识里最绕的地方，但只要抓住"旋转后仍是搜索树"和"旋转后高度降低"这两条原则，配合抽象图去理解，就能把无穷无尽的具体情况收敛成固定的几种操作。
一、AVL 树概念回顾与平衡因子
1.1 高度差不超过一
AVL 树由两位俄罗斯数学家 Adelson-Velsky 和 Landis 于 1962 年提出，规则只有一条：任何节点的左右子树高度差不超过 1。为什么不是要求相等？因为相等是理想情况，实际做不到。只有满二叉树才能做到每个节点左右子树高度差为零；非满的完全二叉树也做不到，更一般的树总会有某些节点左右高度差恰好为 1。所以"不超过 1"就是 AVL 树认为的最佳状态。
1.2 平衡因子：观察树是否出问题的风向标
平衡因子（bf）的默认定义是右子树高度减左子树高度。定义并没有固定死，也可以左减右，但一旦选了一种，后面所有逻辑都要跟着调整。AVL 树也不一定必须有平衡因子，有些实现直接比较子树高度；加了平衡因子，好处是随时能看出树有没有出问题，坏处是每次调整后都要维护它，这是付出代价换来的便利。本篇代码选择右减左、带平衡因子、带三叉链（_parent 指针）的方案。
平衡因子的合法范围是 [-1, 1]，绝对值不超过 2。当某节点平衡因子变成 2 或 -2，说明这棵树出问题了，需要旋转修复。
1.3 插入后平衡因子的更新规则
插入节点按搜索树规则走到空位置，新节点插在父节点哪一侧，父节点平衡因子就朝哪个方向变化：插在左子树，平衡因子减一；插在右子树，平衡因子加一。之后沿三叉链向上更新，分三种情况处理：
- 父节点平衡因子变为 0：说明之前是 1 或 -1，节点插在了较低的一侧，左右刚好补齐，子树高度没有变化，停止更新。
- 父节点平衡因子变为 1 或 -1：说明之前是 0，现在一边高了，子树高度确实增加了，继续向上更新。
- 父节点平衡因子变为 2 或 -2：说明之前已经允许 1 或 -1，又在较高的一侧继续插入，树已经不平衡，需要旋转处理。
二、旋转：平衡的修复手段
2.1 旋转的两条原则
旋转不是凭空想出来的操作，它必须同时满足两点：旋转后这棵子树依然是二叉搜索树；旋转后高度降低。插入让子树高度增加了 1，旋转把高度降回插入前的样子，所以旋转后不会继续向上影响祖先的高度，整棵子树回到平衡状态，更新到此结束。
2.2 左单旋的抽象图
以最简单的左单旋为例。右侧偏高时往左边压，称为左单旋。把 30 记为 parent，60 记为 subR（parent 的右孩子），60 的左孩子记为 subRL（也就是图中的 b子树）。这些名字是相对 parent 界定的：我的右孩子、我右孩子的左孩子。
图中 h 为子树的高度
旋转动作只有三步：subRL(b) 变成 parent(30) 的右孩子，parent(30) 变成 subR(60) 的左孩子，subR(60) 成为这棵子树的根。
为什么 subRL 放到 30 的右边是合理的？
因为 subRL 整棵子树的值都比 30 大（它整体在 30 的右子树里），又都比 60 小（它在 60 的左子树里），所以它放在 30 的右边、60 的左边刚刚好。同理，30 和 a 整体都比 60 小，30 变成 60 的左孩子也符合搜索树规则。旋转前子树高度为 h+2，插入后变成 h+3，旋转后回到 h+2，搜索树性质和平衡同时保住。
2.3 旋转种类的判定
四种旋转怎么选？看更新路径上 parent（父节点） 和 cur（当前节点） 的平衡因子是否同号：同号说明是纯粹的一边高，用单旋；异号说明是折线形状，一边高但下面反着高，单旋解决不了，用双旋。
| parent 的 bf | cur 的 bf | 形状 | 旋转 |
|---|---|---|---|
| 2 | 1 | 纯右边高（直线） | 左单旋 |
| -2 | -1 | 纯左边高（直线） | 右单旋 |
| 2 | -1 | 右边高、左折（折线） | 右左双旋 |
| -2 | 1 | 左边高、右折（折线） | 左右双旋 |
三、旋转的代码实现
3.1 节点结构与插入框架
节点在搜索树基础上增加 _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)
{}
};
Insert 的前半段和搜索树完全一样：找到空位置插入新节点，把新节点的 _parent 连上。后半段是平衡因子更新加旋转判定：
// 更新平衡因子
while (parent)
{
if (cur == parent->_left)
parent->_bf--; // 插入在左子树，减一
else
parent->_bf++; // 插入在右子树，加一
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)
{
// 平衡被破坏，按同号单旋、异号双旋的规则旋转
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
RotateLR(parent);
}
break;
}
else
{
assert(false); // 走到这里说明更新前树已经坏了
}
}
3.2 左单旋 RotateL
把抽象图翻译成代码。看起来只动两个指针（parent 的右孩子、subR 的左孩子），但用了三叉链，就要把三份父指针全部维护好，这是当初享受便利付出的代价：
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent; // subRL 可能为空，必须先判空
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parentParent == nullptr)
{
_root = subR; // parent 原来就是根，subR 变成整棵树的根
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
parentParent->_left = subR;
else
parentParent->_right = subR;
subR->_parent = parentParent; // 子树上面的关系也要接上
}
parent->_bf = subR->_bf = 0; // 旋转后两者都平衡，平衡因子清零
}
细节逐个核对：subRL 变成 parent 的右孩子后，它的父指针要指向 parent，但 subRL 可能是空（h 等于 0 时），所以要判空；parent 变成 subR 的左孩子后，parent 的父指针指向 subR；再往上一层，旋转的这棵树可能是整棵树，也可能是某棵子树，如果 parent 上面还有父节点，要看 parent 原来是它父节点的左孩子还是右孩子，把 subR 接到对应位置；如果 parent 本身就是根，subR 直接成为新根，父指针置空。这些就是"拖家带口"式旋转的全部细节。
3.3 右单旋 RotateR
右旋是左边高，往右边压，与左旋完全镜像：subLR 变成 parent 的左孩子，parent 变成 subL 的右孩子，subL 成为根。课堂上这段代码出了一个小问题：旋转的指针操作都对了，唯独漏掉了最后平衡因子的清零，导致后续测试时被 isBalance 抓出来。补上两行就完整了：
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
parentParent->_left = subL;
else
parentParent->_right = subL;
subL->_parent = parentParent;
}
parent->_bf = subL->_bf = 0;
}
四、双旋
4.1 为什么单旋不够
如果插入位置让更新路径变成折线，单旋会来回打转。举例：parent 的平衡因子是 2（右边高），但它的右孩子反而是 -1（左边高），说明高的是右下方的子树。此时直接左旋，把 60 的左孩子 b 拿给 30 做右孩子、30 降下来做 60 的左孩子，结果只是从"右边高"变成"左边高"，两边的高度差依然存在，再右旋又会旋回去，死循环。本质原因：单旋要求纯粹一边高，折线形状需要先旋一次把折线捋直，再旋一次恢复平衡。
以 30 右边高、60 左边高为例（即 bf(30)=2, bf(60)=-1）：先以 60 为旋转点右旋，把 60 的左子树 b 抬上来，60 降下去，此时整棵子树变成纯右边高；再以 30 为旋转点左旋，一次性恢复平衡。先右旋再左旋，所以叫右左双旋。反过来（bf(30)=-2, bf(30 左)=1）就是左右双旋。
4.2 右左双旋 RotateRL：复用单旋
双旋实现起来意外地简单：直接复用两个单旋，因为单旋已经把父子链接和根链接处理得干干净净。第一次旋转点不是 parent，而是 parent 的右孩子：
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf; // 旋转前先记录 subRL 的平衡因子
RotateR(parent->_right); // 先对右孩子右旋，把折线捋直
RotateL(parent); // 再对 parent 左旋，恢复平衡
}
4.3 双旋真正的难点：平衡因子的更新
单旋后两个节点的平衡因子直接清零，双旋不行。因为双旋涉及三个节点（parent、subR、subRL），最终 subRL 成为根，另外两个节点的平衡因子取决于插入发生在 b 子树还是 c 子树，必须分情况。区分方法是看 subRL 旋转前的平衡因子：
- bf 为 0：subRL 本身是新增节点（h 等于 0 的单独情况），旋转后三个节点平衡因子全是 0。
- bf 为 1：插入发生在 c 子树（subRL 的右子树）。旋转后 subRL 的右孩子是 subR，subR 左右都是 h，平衡因子为 0；parent 的左是 a（h）、右是 b（h-1），平衡因子是 -1。
- bf 为 -1：插入发生在 b 子树（subRL 的左子树）。旋转后 parent 左右都是 h，平衡因子为 0；subR 的左是 c（h-1）、右是 d（h），平衡因子是 1。
if (bf == 0) // subRL 是新增节点
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1) // 在 c 子树插入
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1) // 在 b 子树插入
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
对照抽象图逐个推一遍就能理解，图上有高度标识，比具象图直观得多。注意即使单旋已经把平衡因子清零，双旋也要显式处理这三类情况，目的是让双旋不依赖单旋的内部实现，逻辑解耦。
4.4 左右双旋 RotateLR
左右双旋是右左双旋的镜像：先对 parent 的左孩子左旋，再对 parent 右旋，平衡因子同样看 subLR 的三种情况
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left); // 先对左孩子左旋
RotateR(parent); // 再对 parent 右旋
if (bf == 0) // subLR 是新增节点
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1) // 在 c 子树插入
{
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1) // 在 b 子树插入
{
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else
{
assert(false);
}
}
推导方法与右左双旋对称：bf 为 -1 表示 b 子树插入，旋转后 parent 的左是 c（h-1）、右是 d（h），平衡因子为 1；bf 为 1 表示 c 子树插入，旋转后 subL 的左是 a（h）、右是 b（h-1），平衡因子为 -1。
五、AVL 树的验证与测试
5.1 判断平衡：isBalance
插入代码写完不能只靠中序遍历证明正确：中序有序只能证明它是搜索树，不能证明它平衡。一个判断平衡的递归函数，外加求高度和节点数的辅助函数：
// 求树的高度：左右子树高的那个加一
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
return leftH > rightH ? leftH + 1 : rightH + 1;
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int leftH = _Height(root->_left);
int rightH = _Height(root->_right);
if (abs(rightH - leftH) >= 2)
{
cout << "高度差异常" << endl;
return false;
}
if (rightH - leftH != root->_bf)
{
cout << "平衡因子异常" << endl;
return false;
}
return _IsBalance(root->_left) && _IsBalance(root->_right);
}
bool IsBalance()
{
return _IsBalance(_root);
}
高度差检查之外还要检查平衡因子：平衡因子是更新逻辑维护的，如果维护出错，可能树本身还平衡、平衡因子却错了，现在不出问题，继续插入后迟早会暴露。递归的左右子树各自再查一遍，才能保证整棵树每个节点都合法。另外注意递归函数要套一层，因为类外部拿不到 _root。
测试时还会用到一个统计节点数的函数，用来确认实际插入的数量（随机插入会有大量重复值）：
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1; // 左子树加右子树再加自己
}
六、删除思路
删除在逻辑上比插入复杂约三成，但大方向不变，也是三步：按搜索树规则删除节点，更新平衡因子，异常时旋转。搜索树的删除之前学过，用中序后继替代被删节点。差别在更新方向：之前右边插入平衡因子加一，现在右边删除要减一；而且删除让高度变矮，更新停止的条件与插入相反，删除后平衡因子变为 0 反而要继续向上更新（因为高度变了），变为 1 或 -1 反而停止。另外删除触发旋转后不一定就结束了，旋转只解决当前子树，可能还需要继续向上更新。
七、完整代码
#pragma once
#include <cassert>
#include <iostream>
template <class K, class V>
struct AVLTreeNode
{
K _key;
V _val;
AVLTreeNode<K, V> *_left;
AVLTreeNode<K, V> *_right;
int _bf; // 平衡因子
AVLTreeNode<K, V> *_parent; // 父节点
AVLTreeNode()
: _key(K()), _val(V()), _left(nullptr), _right(nullptr), _bf(0), _parent(nullptr)
{
}
AVLTreeNode(const K &key, const V &val)
: _key(key), _val(val), _left(nullptr), _right(nullptr), _bf(0), _parent(nullptr)
{
}
};
template <class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
typedef AVLTreeNode<K, V> *PNode;
private:
PNode _root = nullptr; // 必须初始化，否则默认构造出的 _root 是野指针
// 先序遍历
void _InOrder(PNode n)
{
if (n == nullptr)
return;
_InOrder(n->_left);
std::cout << "key: " << n->_key << " val: " << n->_val << std::endl;
_InOrder(n->_right);
}
// 拷贝子节点
PNode copy(PNode node)
{
if (node == nullptr)
return nullptr;
// 先序遍历创建节点
PNode newNode = new Node(node->_key, node->_val);
PNode left = copy(node->_left);
PNode right = copy(node->_right);
newNode->_left = left;
newNode->_right = right;
if (left) // 深拷贝也要维护三叉链，否则拷贝出的树 _parent 全为空，之后 Insert 触发旋转会误判根节点
left->_parent = newNode;
if (right)
right->_parent = newNode;
newNode->_bf = node->_bf;
return newNode;
}
// 销毁子节点
void Destory(PNode node)
{
if (node == nullptr)
return;
// 后序遍历
Destory(node->_left);
Destory(node->_right);
delete node;
}
// 左单旋: parent->_bf == 2 subR->_bf == 1
// 传递的是 平衡因子异常节点，此时能够保证parent和subR不为空
void RotateL(PNode parent)
{
PNode subR = parent->_right;
PNode subRL = subR->_left;
PNode PP = parent->_parent;
// 从subRL出发
if (subRL != nullptr) // 一定要注意 subRL 可能为空
subRL->_parent = parent;
// 从parent节点出发
parent->_right = subRL;
parent->_parent = subR;
// 从subR出发
subR->_left = parent;
subR->_parent = PP;
// 如果进行左旋的节点不是根节点（），需要改变 PP 的指向
if (PP == nullptr) // 当前节点为根节点
_root = subR;
else
{
if (PP->_left == parent)
PP->_left = subR;
else if (PP->_right == parent)
PP->_right = subR;
}
// 节点的指向解决之后，我们需要解决平衡因子的计算
parent->_bf = 0;
subR->_bf = 0;
}
// 右单旋: parent->_bf == -2 subL->_bf == -1
// 传递的是 平衡因子异常节点，此时能够保证parent和subL不为空
void RotateR(PNode parent)
{
PNode subL = parent->_left;
PNode subLR = subL->_right;
PNode PP = parent->_parent;
// 从 subLR 出发
if(subLR != nullptr)
subLR->_parent = parent;
// 从 parent 出发
parent->_left = subLR;
parent->_parent = subL;
// 从 subL 出发
subL->_right = parent;
subL->_parent = PP;
// 如果进行右旋的节点不是根节点（），需要改变 PP 的指向
if(PP == nullptr)
_root = subL;
else
{
if(PP->_left == parent)
PP->_left = subL;
else
PP->_right = subL;
}
// 修改平衡因子
parent->_bf = 0;
subL->_bf = 0;
}
// 右左旋: parent->_bf == 2 subR->_bf == -1
// 传递的是 平衡因子异常节点，此时能够保证parent和subR不为空
void RotateRL(PNode parent)
{
PNode subR = parent->_right;
PNode subRL = subR->_left;
int bf = subRL->_bf;
//先对 subR 右旋, 再对 parent 左旋
RotateR(subR);
RotateL(parent);
if(bf == 0)//如果subRL平衡因子为0
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else if(bf == -1)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else if(bf == 1)
{
subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else
assert(false);
}
// 左右旋: parent->_bf == -2 subL->_bf == 1
// 传递的是 平衡因子异常节点，此时能够保证parent和subL不为空
void RotateLR(PNode parent)
{
PNode subL = parent->_left;
PNode subLR = subL->_right;
int bf = subLR->_bf;
//先对 subL 左旋, 再对 parent 右旋
RotateL(subL);
RotateR(parent);
if(bf == 0)//如果subLR平衡因子为0
{
subLR->_bf = 0;
parent->_bf = 0;
subL->_bf = 0;
}
else if(bf == -1)
{
subLR->_bf = 0;
parent->_bf = 1;
subL->_bf = 0;
}
else if(bf == 1)
{
subLR->_bf = 0;
parent->_bf = 0;
subL->_bf = -1;
}
else
assert(false);
}
public:
AVLTree()
: _root(nullptr)
{
}
AVLTree(const AVLTree &root)
{
_root = copy(root._root);
}
AVLTree &operator=(const AVLTree &root)
{
if (this != &root) // 防止自赋值
{
Destory(_root);
_root = copy(root._root);
}
return *this;
}
~AVLTree()
{
Destory(_root);
_root = nullptr;
}
bool Insert(const K &key, const V &val)
{
// 如果根节点为空，则为根节点
if (_root == nullptr)
{
_root = new Node(key, val);
return true;
}
PNode parent = nullptr; // 新节点的父节点
PNode cur = _root;
while (cur)
{
if (cur->_key < key) // 如果类型 T 为复杂对象，则需要重载运算符
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
return false; // 去重处理，不会插入重复内容
}
cur = new Node(key, val); // cur变量的任务已经完成，这里复用了这个变量来存储新节点的值
if (parent->_key < key)
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent; // 一定要记得更新_parent的指向，这容易遗漏
// 判断是否需要旋转
while (parent)
{
// 平衡因子我们定义 右子树高度减去左子树高度
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0) // parent 是平衡的，往上的子树bf都不会改变
break;
else if (parent->_bf == -1 || parent->_bf == 1) // parent 是倾斜的，往上的子树bf可能会变
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -2 || parent->_bf == 2) // 需要旋转
{
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);
else
assert(false);
break; // 旋转后子树高度恢复原状，祖先的平衡因子均不变
}
else
assert(false); // 出现错误
}
return true;
}
bool Find(const K &key)
{
Node *cur = _root;
while (cur)
{
if (cur->_key < key)
cur = cur->_right;
else if (cur->_key > key)
cur = cur->_left;
else
return true;
}
return false;
}
void InOrder()
{
_InOrder(_root);
}
};
总结
这篇笔记补完了 AVL 树的最后一块拼图。AVL 树在搜索树的基础上用平衡因子做风向标：插入节点后沿三叉链向上更新平衡因子，变为 0 停止、变为 1 或 -1 继续、变为 2 或 -2 就旋转。旋转始终守着两条原则，保持搜索树规则和降低高度，具体图无穷无尽，但抽象图把一切收敛成四种操作：同号直线用单旋，异号折线用双旋。单旋的代码看起来只动两个指针，实际要把三叉链的三个方向的父指针都维护好，还要处理子树根和整棵树根两种情况；双旋直接复用两个单旋，难点全在平衡因子的更新上，要根据 subRL 旋转前的平衡因子区分插入发生在哪一侧，三种情况分别赋不同的值。写完代码要用 isBalance 验证，高度差和平衡因子都要查，课堂上真实发生的调试过程告诉我们，右旋漏掉两行平衡因子清零的代码，正是靠着带预期的逐步调试才被揪出来。AVL 树的删除更复杂但校招不考，了解思路即可。下一节我们将进入红黑树：它放宽了平衡条件，用颜色约束代替严格的高度差，map 和 set 的真实底层正是红黑树，模拟实现 mymap 和 myset 也将在那里展开。
一站式 AI 云服务平台
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)