26. 平衡二叉树：定义与旋转调整
平衡二叉树，英文叫 AVL 树。说实话，我第一次听到这个名字时，还以为是某个汽车型号。后来才知道，这是两位苏联数学家 Adelson-Velsky 和 Landis 的缩写。
那它到底解决了什么问题？
你想想看，普通的二叉搜索树，如果插入的数据刚好是有序的，比如 1、2、3、4、5……那树就退化成了链表。查找效率直接从 O(log n) 掉到 O(n)。这在项目中是绝对不能忍的。
平衡二叉树就是为了解决这个退化问题而生的。
26.1 平衡二叉树的定义
定义其实不复杂，就两条：
- 它首先是一棵二叉搜索树（左小右大）
- 每个节点的左右子树高度差绝对值不超过 1
这个高度差，我们叫它「平衡因子」。平衡因子 = 左子树高度 - 右子树高度。取值只能是 -1、0、1。
核心要点：只要有一个节点的平衡因子绝对值大于 1，这棵树就不平衡了，需要调整。
我在项目中遇到过这样一个场景：一个实时交易系统的订单簿，需要频繁插入和查找价格。如果用普通 BST，遇到连续报价时性能直接崩了。后来换成 AVL 树，查询时间稳定在微秒级。嗯，这就是平衡的力量。
26.2 四种不平衡情况
插入节点后，树可能变得不平衡。我习惯把不平衡情况归纳为四种：
| 类型 | 描述 | 失衡节点 |
|---|---|---|
| LL | 插入在左子树的左子树 | 失衡节点的左孩子太高 |
| RR | 插入在右子树的右子树 | 失衡节点的右孩子太高 |
| LR | 插入在左子树的右子树 | 失衡节点的左孩子的右孩子太高 |
| RL | 插入在右子树的左子树 | 失衡节点的右孩子的左孩子太高 |
说白了，LL 和 RR 是「一条直线」的不平衡，LR 和 RL 是「折线」的不平衡。直线好办，一次旋转搞定；折线需要两次旋转。
26.3 四种旋转操作
26.3.1 LL 旋转（右旋）
LL 情况：新节点插入在失衡节点的左孩子的左子树上。这时候需要右旋。
右旋怎么操作？我教你一个口诀：「左孩上位，左孩的右孩给原父当左孩」。
// LL 右旋
struct Node* rotateRight(struct Node* y) {
struct Node* x = y->left;
struct Node* T2 = x->right;
// 旋转
x->right = y;
y->left = T2;
// 更新高度
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x; // 新根
}26.3.2 RR 旋转（左旋）
RR 情况是 LL 的镜像。新节点插入在失衡节点的右孩子的右子树上。左旋即可。
// RR 左旋
struct Node* rotateLeft(struct Node* x) {
struct Node* y = x->right;
struct Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}26.3.3 LR 旋转（先左旋后右旋）
LR 情况稍微麻烦一点。新节点插入在失衡节点的左孩子的右子树上。这时候是一条折线，不能直接右旋。
正确的做法是：先对左孩子做左旋（变成 LL 情况），再对失衡节点做右旋。
// LR 旋转
struct Node* rotateLR(struct Node* z) {
z->left = rotateLeft(z->left); // 先左旋左孩子
return rotateRight(z); // 再右旋自己
}我的经验：写 LR 和 RL 旋转时，最容易搞混顺序。我曾经在代码里把左右旋顺序写反了，调试了整整一个下午。后来我养成了一个习惯——在代码注释里写上「先处理孩子，再处理自己」，再也没错过。
26.3.4 RL 旋转（先右旋后左旋）
RL 是 LR 的镜像。新节点插入在失衡节点的右孩子的左子树上。
// RL 旋转
struct Node* rotateRL(struct Node* z) {
z->right = rotateRight(z->right); // 先右旋右孩子
return rotateLeft(z); // 再左旋自己
}26.4 完整插入流程
把上面的旋转组合起来，就得到了 AVL 树的插入算法：
struct Node* insert(struct Node* node, int key) {
// 1. 普通 BST 插入
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node; // 重复键不插入
// 2. 更新高度
node->height = 1 + max(height(node->left), height(node->right));
// 3. 计算平衡因子
int balance = getBalance(node);
// 4. 判断并旋转
// LL
if (balance > 1 && key < node->left->key)
return rotateRight(node);
// RR
if (balance < -1 && key > node->right->key)
return rotateLeft(node);
// LR
if (balance > 1 && key > node->left->key) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
// RL
if (balance < -1 && key < node->right->key) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node;
}避坑指南：我曾经在实现 AVL 树时，忘记在旋转后更新高度。结果树虽然旋转了，但平衡因子计算错误，导致后续插入又出问题。记住：旋转后一定要更新高度，而且要先更新子树的高度，再更新新根的高度。
26.5 知识体系总览
下面这张图总结了平衡二叉树的核心知识结构，方便你整体把握：
26.6 性能分析
AVL 树的性能，说白了就是「用旋转换平衡」：
- 查找：O(log n)。树始终保持平衡，不会退化。
- 插入：O(log n)。查找插入位置 O(log n)，最多两次旋转 O(1)。
- 删除：O(log n)。删除后可能需要多次旋转，但总体还是 O(log n)。
- 空间：每个节点多存一个高度值，额外 O(n) 空间。
实际应用建议：如果你的场景是查询远多于插入删除，AVL 树是很好的选择。但如果插入删除也很频繁，红黑树可能更合适——它牺牲了一点平衡性，换来了更少的旋转次数。
我个人习惯在内存数据库、字典实现、需要频繁范围查询的场景中使用 AVL 树。比如我之前参与的一个网络流量分析工具，用 AVL 树存储 IP 地址段，查询速度比哈希表还稳定——哈希表有冲突，AVL 树没有。
嗯，平衡二叉树的内容就这些。记住四个字：失衡则旋。只要掌握了四种旋转，AVL 树就没什么秘密了。