14、AVL树的插入与删除：平衡调整的艺术
AVL树，说白了就是一种「强迫症」版的二叉搜索树。它要求每个节点的左右子树高度差不能超过1。一旦失衡，就得立刻调整。我刚开始学的时候觉得这玩意儿挺玄乎，后来在项目中写索引模块时才发现——没有平衡，性能说崩就崩。
今天我们就来聊聊AVL树的核心操作：插入后的平衡调整，以及删除后的平衡调整。这两个操作，是AVL树的灵魂。
14.1 平衡因子与失衡类型
先搞清楚一个概念：平衡因子。它等于左子树高度减去右子树高度。取值只能是 -1、0、1。一旦变成 2 或 -2，就失衡了。
失衡有四种情况：
- LL型：左子树的左子树插入节点，导致失衡
- RR型：右子树的右子树插入节点，导致失衡
- LR型：左子树的右子树插入节点，导致失衡
- RL型：右子树的左子树插入节点，导致失衡
LL和RR用单旋转解决，LR和RL用双旋转解决。记住这个口诀：「左左单右，右右单左，左右双右左，右左双左右」。
核心要点：失衡节点是第一个平衡因子绝对值达到2的节点。调整时，只调整从插入点到根路径上的第一个失衡节点即可。
14.2 插入操作后的平衡调整
插入一个节点后，我们从插入点向上回溯，更新每个祖先的平衡因子。一旦发现某个节点失衡，就根据它的失衡类型做旋转。
我个人习惯用递归实现插入，这样回溯过程天然存在，不用手动维护栈。
14.2.1 LL型失衡与右单旋
举个例子：
// 右单旋
Node* rotateRight(Node* y) {
Node* x = y->left;
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; // 新的根
}这段代码看起来简单，但有个坑：更新高度的顺序不能错。必须先更新 y，再更新 x。因为 x 的高度依赖于 y 的高度。我曾经在项目里写反了顺序，查了整整一下午的 bug……
14.2.2 RR型失衡与左单旋
对称操作，不赘述。代码就是把 rotateRight 里的 left 和 right 互换。
14.2.3 LR型失衡与左右双旋
先对左孩子做左旋，再对自己做右旋。说白了就是「先变成LL，再处理LL」。
Node* rotateLR(Node* z) {
z->left = rotateLeft(z->left);
return rotateRight(z);
}你想想看，为什么不能直接右旋？因为直接右旋的话，左孩子的右子树会跑到右边去，结构还是乱的。必须先让左孩子变成「左左」形态。
14.2.4 RL型失衡与右左双旋
对称操作，先右旋右孩子，再左旋自己。
小技巧：写双旋的时候，我习惯先画图。把每个节点的位置标清楚，再写代码。画图5分钟，省去debug两小时。
14.3 删除操作后的平衡调整
删除比插入麻烦一点。因为删除后，可能不止一个节点失衡。我们需要从删除点向上回溯，检查每个祖先，一旦失衡就调整，然后继续向上。
嗯，这里要注意：删除后的调整可能引发连锁反应。你调整完一个节点，它的父节点可能又失衡了。所以必须一直回溯到根。
14.3.1 删除的三种情况
| 情况 | 操作 | 后续处理 |
|---|---|---|
| 叶子节点 | 直接删除 | 向上回溯调整 |
| 只有一个孩子 | 用孩子替换 | 向上回溯调整 |
| 有两个孩子 | 找前驱或后继替换值，然后删除前驱/后继 | 从被删除的前驱/后继位置向上回溯 |
我个人偏爱用后继（右子树的最小节点）来替换。因为实现起来更直观，不容易出错。
14.3.2 删除后的平衡调整代码
Node* deleteNode(Node* root, int key) {
// 标准BST删除
if (root == NULL) return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// 找到要删除的节点
if (root->left == NULL || root->right == NULL) {
Node* temp = root->left ? root->left : root->right;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
Node* temp = minValueNode(root->right);
root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
}
if (root == NULL) return root;
// 更新高度
root->height = 1 + max(height(root->left), height(root->right));
// 检查平衡并调整
int balance = getBalance(root);
// 四种失衡情况
if (balance > 1 && getBalance(root->left) >= 0)
return rotateRight(root);
if (balance > 1 && getBalance(root->left) < 0) {
root->left = rotateLeft(root->left);
return rotateRight(root);
}
if (balance < -1 && getBalance(root->right) <= 0)
return rotateLeft(root);
if (balance < -1 && getBalance(root->right) > 0) {
root->right = rotateRight(root->right);
return rotateLeft(root);
}
return root;
}注意：删除后的平衡判断条件与插入略有不同。比如LL型，插入时要求左孩子的平衡因子为1，但删除后可能是0或1。代码里用 >= 0 就是为了兼容这种情况。
14.4 知识体系总览
下面这张图，把AVL树插入和删除的核心逻辑串起来了。建议你多看几遍，理解每个分支的含义。
14.5 避坑指南
最后，分享几个我踩过的坑：
- 高度更新顺序：旋转后，先更新子节点的高度，再更新父节点。顺序反了，高度就错了。
- 删除后的连锁调整：不要以为调整一次就完事了。删除可能导致多个祖先失衡，必须一路回溯到根。
- 平衡因子的判断条件：插入和删除的失衡判断条件不完全一样。删除后，LL型可能对应左孩子平衡因子为0的情况。
- 递归返回新根：每次旋转后，要返回新的子树根。递归调用时，父节点要接收这个新根并更新指针。
我的习惯：写AVL树时，我会单独写一个 updateHeight 函数和一个 rebalance 函数。这样插入和删除的代码都能复用，逻辑也更清晰。
AVL树的插入和删除，说白了就是「插入/删除 + 回溯 + 旋转」三步走。理解了这个框架，剩下的就是熟练度的问题了。多画图，多写代码，慢慢就变成肌肉记忆了。
公众号：蓝海资料掘金营，微信 deep3321