AVL 树是最早的自平衡二叉搜索树:空树算 AVL;非空时左右子树都是 AVL,且左右子树高度差的绝对值不超过 1。这个结构由 Adelson-Velsky 和 Landis 在 1962 年的论文《An algorithm for the organization of information》中提出,"AVL"就是两人姓氏的首字母。
高度差为什么定成 1 而不是 0?两个结点的树,不管孩子挂在哪边,高度差只能是 1;四个结点的某些形态也一样。规则要覆盖所有规模,就不能写成"必须差 0"。
平衡因子的符号是一个约定
要让"差多少"变成能随时检查的一个数,给每个结点加一个整数:
_bf = 右子树高度 - 左子树高度按这个定义,合格结点的 _bf 只可能是 −1、0、1,出现 ±2 就说明这棵子树已经失衡。存子树高度也能判断,但要做减法;存差值把"是否失衡"和"往哪边偏"压进同一个数,看到 parent 是 ±2、再看孩子 cur 的符号,立刻能决定单旋还是双旋、往哪边转。

符号方向是约定,不同教材有写成"左减右"的。选哪一种都行,但三个地方必须一致:插入时按方向加减、判断 ±2 时按方向选旋转、校验时按同一方向算差值。任何一处反了,症状都是树转得动、转完更歪。
结点需要指向父亲的指针,因为更新平衡因子和旋转后重新挂接都要往上走:
#include <cassert>
#include <iostream>
#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;
AVLTreeNode(const std::pair<K, V>& kv)
: _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0)
{}
};课件说"AVL 树并不是必须要平衡因子",这句是对的:差值只是实现手段,也可以用"存高度"或"每次现算"来维护平衡,只是慢。
下面各节给的是 template<class K, class V> class AVLTree 的成员函数,类里有 typedef AVLTreeNode<K, V> Node;、根指针 Node* _root = nullptr;,四个旋转函数和 _Height、_IsBalanceTree 是私有成员。
插入后只有一条祖先链会变
插入本身还是二叉搜索树的走位,新结点挂到某个空位上。变化只发生在新结点到根的这一条链上:链外的结点,左右子树一个结点都没多,高度没变,平衡因子也不该动。
更新规则一句话:新结点在 parent 的右子树,_bf 加 1;在左子树,减 1。三个刹车对应三个不同的问题:
更新后 parent->_bf | 怎么来的 | 子树高度变了吗 | 怎么办 |
|---|---|---|---|
| 0 | −1→0 或 1→0 | 没变,矮的一侧被补齐 | 停 |
| ±1 | 0→±1 | 涨了 1 | 继续往上 |
| ±2 | ±1→±2 | 旋转后回到原来的高度 | 转完就停 |
第一行最容易背反:归零说明新结点补在了矮的那边,两边被拉平,子树高度还是原来那一侧的高度,上一层完全感觉不到变化。
也正因为如此,更新不需要每次重新求子树高度:高度有没有变、变高还是变矮,都由下层那一轮已经算好的结果传上来,parent 只做加减。

走最坏情况也可能一路更新到根:
bool Insert(const std::pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
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;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = 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);
}
}
return true;
}课件给的 Insert 在 ±2 分支里只有一句 break; 和注释"不平衡了,旋转处理",四个旋转函数要到后面几节才出现。两段要拼起来读,照抄前半段,插入永远不旋转,得到的只是一棵普通二叉搜索树。
±2 出现时,cur 一定是 parent 更高的那一侧的孩子。因为 parent 能从 ±1 爬到 ±2,上一轮 cur 刚被赋成这个孩子,它当时的 _bf 才从 0 变成 ±1。所以四种组合(2 配 1、−2 配 −1、2 配 −1、−2 配 1)已经穷举,没有第五种。
右单旋:把 b 子树过继给 10
旋转守两条原则:不破坏搜索树的中序;把子树高度降回插入之前。
右单旋的抽象形态:10 为根,左孩子 5,5 的左右子树是 a、b,10 的右边是 c,三棵子树高度都是 h。新结点插进 a,a 从 h 变成 h+1,10 的 _bf 从 −1 变成 −2。
b 为什么必须过继给 10?旋转前有 5 小于 b 里所有值,b 里所有值又小于 10。5 当新根、10 当 5 的右孩子之后,b 挂 5 的右边合法,挂 10 的左边也合法,正好平移过去,中序序列一个字都不变。转完子树高度回到 h+2,和插入之前一样,所以上层不用再改。

一次右单旋动六条线,每一处漏掉都会断链:
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR; // 1. b 过继给 10 的左
if (subLR)
{
subLR->_parent = parent; // 2. b 的父亲改指 10
}
Node* parentParent = parent->_parent; // 3. 先存上层,再改 parent
subL->_right = parent; // 4. 10 挂到 5 的右边
parent->_parent = subL; // 5. 10 的父亲改指 5
if (parentParent == nullptr)
{
_root = subL; // 6a. 原来就是整棵树的根
subL->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL; // 6b. 接回上层
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
parent->_bf = 0;
subL->_bf = 0;
}parentParent 必须在 parent->_parent = subL; 之前取。若先改父亲指针再读 parent->_parent,拿到的是 subL,上层直接断链——树还能查找、还能中序输出,只是某个结点的 _bf 差了 1。
左单旋与课件里残留的那句话
左单旋是镜像:10 右边太高,15 是右孩子,15 的左子树 b 夹在 10 和 15 之间,过继给 10 的右边,15 成为新根。

void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
parent->_bf = 0;
subR->_bf = 0;
}课件"左单旋"那一节的正文第一句写的是"他代表了所有右单旋的场景",和标题、以及同段后半句"10 的平衡因子从 1 变成 2,右边太高,需要往左旋转"自相矛盾。这段是从右单旋整段复制过来的,改标题时漏改了中间这句;按"左单旋"读,其余描述(15 当新根、10 变左孩子)都是对的。
方向记法一句话:哪边高,就把哪边的孩子提上来。
双旋:枢纽的旧平衡因子决定三个新值
左右双旋(LR)的触发条件是折线:10 左边高,但高的部分长在 5 的右子树 b 里。对 10 来说左边更高,对 5 来说它自己右边更高,一条折线用右单旋扳不直。做法是先对内侧做一次反向单旋,把折线捋直,再对外侧做标准单旋:先 RotateL(parent->_left),再 RotateR(parent)。
难点不在转,在转完的平衡因子。两次单旋各自把两个端点的 _bf 置零,三个结点的旧值全被覆盖,所以必须先把枢纽 subLR 的 _bf 存下来:
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
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);
}
}
三次转动之后三个结点的相对位置已经固定,各剩多少高度差,完全取决于新结点原来挂在枢纽左边、右边,还是枢纽本身。这件事恰好被枢纽旋转前的 _bf 记下来:
枢纽 subLR->_bf | subL(5) | subLR(8) | parent(10) |
|---|---|---|---|
| 0(8 自己是新结点) | 0 | 0 | 0 |
| −1(新结点在 e) | 0 | 0 | 1 |
| 1(新结点在 f) | −1 | 0 | 0 |
右左双旋(RL)完全对称:subR 是 parent 的右孩子,subRL 是枢纽,先 RotateR(parent->_right) 再 RotateL(parent),按 subRL 的旧值重建三个 _bf。

void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
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);
}
}一次插入最多做一次双旋(两次单旋),旋转后子树高度恢复,链在这里断开,不会连锁。
高度上界与校验
课件写"AVL 树整体结点数量和分布和完全二叉树类似,高度可以控制在 logN",这句不准确:log₂N 是完全二叉树的界,AVL 的界更松,要自己推。
反过来问:高度为 h 的 AVL 树最少几个结点?要让高度尽量大、结点尽量少,根的两棵子树就得尽量矮,但高度差最多 1,所以一棵高 h−1、一棵高 h−2:
N(h) = N(h-1) + N(h-2) + 1, N(1) = 1, N(2) = 2和斐波那契同形,指数增长:1、2、4、7、12、20、33、54、88、143…反解递推得到 h ≤ 1.44 log₂(N + 2)。这是 AVL 树高度上界的标准结论。
查找和普通二叉搜索树一样,O(logN):
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;
}自己实现的树是否合格,靠三件事验证:中序有序,说明旋转没破坏搜索树;每个结点真实高度差绝对值不超过 1,说明树确实平衡;每个结点存的 _bf 等于按定义算出的差值,说明账本没错。第三条最关键,前两条只能说明"现在看起来还行",第三条能指出是哪一次插入把账算错了。
void InOrder() const
{
_InOrder(_root);
std::cout << '\n';
}
int Height() const
{
return _Height(_root);
}
bool IsBalanceTree() const
{
return _IsBalanceTree(_root);
}
private:
void _InOrder(Node* root) const
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
std::cout << root->_kv.first << ' ';
_InOrder(root->_right);
}
int _Height(Node* root) const
{
if (root == nullptr)
{
return 0;
}
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
bool _IsBalanceTree(Node* root) const
{
if (root == nullptr)
{
return true;
}
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
if (diff < -1 || diff > 1)
{
std::cout << root->_kv.first << " 高度差异常\n";
return false;
}
if (root->_bf != diff)
{
std::cout << root->_kv.first << " 平衡因子异常\n";
return false;
}
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}int main()
{
AVLTree<int, int> t;
int a[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};
for (int e : a)
{
t.Insert({e, e});
}
t.InOrder(); // 1 2 3 4 5 6 7 14 15 16
std::cout << t.IsBalanceTree() << '\n'; // 1
std::cout << t.Height() << '\n'; // 4
return 0;
}_IsBalanceTree 对每个结点现场用 _Height 求左右高度,代价是 O(N·h):树平衡时 O(N logN),树塌成链就退到 O(N²)。它只能放在测试和断言里,塞进插入路径会把 AVL 的优势全部吃掉。
课件那段随机测试直接用 vector、clock()、srand、rand,摘出来单独编译时要自己补 <vector>、<ctime>、<cstdlib> 三个头文件。
删除课件明确说不讲。方向和插入对称:先按二叉搜索树删(零到一个孩子直接接上,两个孩子用后继替换),再从"实际变矮的那个结点"的父亲开始往上改平衡因子;变矮会让祖先的 _bf 往反方向走,出现 ±2 就旋转。差别在传播方式:插入的链会因为一次旋转立刻断开,删除不会,可能一路连锁到根,所以删除最坏要做 O(logN) 次旋转。两者复杂度都是 O(logN),实现难度差一个量级。
AVL 与红黑树的取舍
AVL 把左右高度差锁在 1 以内,树更矮,查找路径更短,查询略快。代价是每次插入删除都要维护这个严格的整数账本,结构变动更频繁。
红黑树只要求最长路径不超过最短路径的两倍,平衡更松,查找比 AVL 略慢,但插入最多两次旋转、删除最多三次,改结构的成本更低。标准库的 std::map/std::set 选的是红黑树,Linux 内核管虚拟内存区域和高精度定时器也用红黑树,理由一致:读写混合的场景里,改结构的稳定性比查找再快一点更值钱。
两者都是 O(logN) 的增删查,差别在成本放在哪一侧。AVL 适合读远多于写的场合;红黑树适合插入删除频繁的场合。
还没有评论 — 第一条由你来留。