树系列第 10 篇：AVL 树的删除、复杂度与对比

欢迎来到“树系列”第 10 篇。第 9 篇我们完成了 AVL 树最经典的章节：插入。我们认识了平衡因子，学会了在插入之后定位“最小失衡子树”，并且把 LL、RR、LR、RL 四种旋转拆成了一套可以照章执行的流程。这一篇要把另一半补上：删除。几乎所有讲 AVL 的资料都会警告读者：删除比插入麻烦。麻烦在哪里？一句话概括就是——插入失衡只修一次，删除失衡可能修完一层又冒出一层，一路修到根。本文就把这件事彻底讲透：先回顾插入修复为什么“只需要修一处”；再给删除设计一条“BST 删除 → 回溯更新 → 逐层检查 → 失衡旋转 → 继续上溯”的流水线；然后图解删除场景下的四种失衡，重点攻克一个高频易错点——当失衡节点的孩子平衡因子为 0 时，单旋就够了，千万不要盲目做双旋；接着用一个具体序列构建 AVL 树，逐个删除叶子、单孩子节点、双孩子节点，并完整演示一次“删一个节点、转两次旋、一路修到根”的级联修复；再给出完整可运行的 TypeScript 实现并逐行解释；随后用递推直觉说明 AVL 树高度为什么被锁死在 1.44 log₂(n + 2) 这个量级；最后把 AVL 和普通 BST 放进同一张对比表，并为第 12 篇的红黑树对比埋下伏笔。

正文路线图：第 0 节快速回顾插入与旋转，并解释删除为什么更麻烦；第 1 节给出删除修复的完整步骤总览；第 2 节图解四种失衡并专门剖析“bf = 0 时选单旋还是双旋”的易错点；第 3 节用具体序列做六个删除案例，包括叶子、单孩子、双孩子、双旋和级联旋转；第 4 节给出完整的 TypeScript 删除实现与逐行讲解；第 5 节用最少节点递推 F_h 建立高度上界 1.44 log₂(n + 2) 的直觉，并汇总三种操作的复杂度；第 6 节把 AVL 与普通 BST 全面对比；第 7 节预告红黑树，解释“AVL 更矮但红黑树旋转更少”的工程权衡；最后附上删除修复速查表、七道自测题（含答案）与第 11 篇的预告。

全篇沿用第 9 篇的符号约定：h 表示子树高度（空子树为 -1），bf 表示平衡因子（左高减右高），T₀、T₁ 等表示删除过程中的中间树状态。所有示例数据都经过程序验证，文中给出的“旋转次数”“是否级联”等结论可以直接复现。如果你在第 9 篇之后已经写过一遍插入代码，建议在阅读第 4 节之前先自己尝试给删除补上 rebalance——你会发现最难的不是代码，而是“为什么删除的旋转有时不止一次”这个心智模型。

0 回顾：插入的修复方式，以及删除为什么更麻烦

0.1 把第 9 篇的“扳手”再摆出来

第 9 篇我们建立了这样一套心智模型：AVL 树是一棵二叉搜索树，额外约束是任意节点的左右子树高度差不超过 1。用“左高减右高”定义平衡因子 bf，那么合法状态就是每个节点的 bf 只可能是 -1、0、+1。一旦某个节点出现 bf = ±2，就说明以它为根的最小子树“失衡”了，需要用旋转把它修回来。

旋转是 AVL 唯一的修理工具，一共四种。当失衡节点与引发路径上的孩子同向偏斜时，做一次单旋：bf = +2 且左孩子 bf = +1，做右旋（LL 型）；bf = -2 且右孩子 bf = -1，做左旋（RR 型）。当路径先拐弯再直行时，做一次双旋：bf = +2 且左孩子 bf = -1，先左旋左孩子、再右旋失衡节点（LR 型）；bf = -2 且右孩子 bf = +1，先右旋右孩子、再左旋失衡节点（RL 型）。旋转的本质是三个节点、四个子树的“搬家”：把中间大小的键提上来当根，剩下两个孩子分别挂到两侧，BST 的中序顺序在旋转前后完全不变，因此旋转永远不破坏二叉搜索树的性质。

还需要复习两个口径：空子树高度为 -1，叶子高度为 0，任意节点高度 = 1 + max(左子树高度, 右子树高度)。这两个口径直接决定了 bf 能否正确反映“只有单孩子”的偏斜。第 9 篇里我们反复强调过：更新高度的顺序必须是自底向上，从新插入节点一路更新到根；不能先更新祖先再更新孩子，否则高度算出来是错的。

在删除语境里，-1 这个口径还有一个更实际的用途：删除叶子后，父节点的一侧会变成“空子树”，如果空子树高度按 0 算，父节点的 bf 就会少算 1，该触发旋转时不触发，树就悄悄坏了。比如案例二里 30 的右子树从“叶子 40”变成“空”，高度从 0 掉到 -1，bf 从 +1 跳到 +2——只有 -1 口径能让这个变化被正确感知。写代码时最容易忽略的正是这种“从有到无”的高度变化。

0.2 插入为什么“只修一处”

插入时，新节点只会让祖先链上某些节点的高度增加 1。一个节点的 bf 最多因此变化 1：插入在左子树，bf +1；插入在右子树，bf -1。所以失衡节点第一次出现时，bf 必然是 ±2，绝不可能是 ±3 或更大。找到最底层那个失衡节点后，对它做一次旋转，这棵子树的高度会恰好恢复成插入前的高度。既然高度恢复了，它上面所有祖先“看到的”左/右子树高度与插入前完全一致，自然不需要任何进一步修复。

这就是插入的幸运之处：一次插入最多触发一次旋转，而且旋转只发生在最低的失衡节点上。回溯虽然要走到根，但大部分祖先只是更新高度、检查 bf，并不真的动手。旋转的总次数是常数，这让插入的最坏复杂度依然是 O(log n)，而不是 O(n log n) 或更糟。

把这句话再精确化一点：插入时，最低失衡节点旋转后，其子树高度恢复原状，于是“这棵子树对外表现”和插入前完全一样——上面的祖先甚至不需要知道自己下面发生过旋转。删除没有这个待遇，因为删除后的旋转可能不恢复高度；子树对外“矮了一层”，祖先就必须重新审视自己的平衡。一个是“修复即复位”，一个是“修复后可能继续传播”，这就是两篇文章全部差异的根源。

0.3 删除的麻烦：高度可能一路往下掉

删除不一样。插入只往树里“加高度”，删除却会“减高度”。一个节点被删掉后，从它父亲开始的祖先链上，每个节点都可能因为某棵子树变矮而失衡。更关键的是：第一次旋转不一定能止血。删除场景下的旋转，有时会让子树高度恢复原状（于是可以停止），有时却会让子树高度再减 1（于是上面的祖先突然失衡，必须继续修）。一次删除完全可能触发两次、三次甚至更多次旋转，失衡点一层一层向上冒，直到根。

右半边的循环是删除与插入最本质的分野：只要某次旋转让子树高度再减 1，失衡就会向上传染，所以退出条件必须包含“高度恢复”或“已经到达根”。

上图中右边的循环就是删除与插入最大的分野：删除的修复流程天然是一个“检查—旋转—再检查”的循环，循环的退出条件是“某一次旋转后子树高度不再下降”或者“已经走到根”。为什么旋转有时能恢复高度、有时不能？这取决于失衡节点那个“偏高孩子”的平衡因子是 0 还是 ±1，正是第 2 节要讲透的细节。现在先记住结论：删除修复 = 一次 BST 删除 + 沿回溯路径重复“更新、检查、旋转”，最坏情况下旋转次数与树高同阶，也就是 O(log n)。

0.4 删除“更麻烦”的三个层次

在进入正题之前，值得把“删除为什么更麻烦”拆成三个层次，后面每一节都会对应到其中一个。

第一层是结构麻烦：BST 删除有三种情况，其中双孩子节点不能直接摘除，必须用中序后继或前驱做值替换，把问题化归为删叶子或删单孩子。这一层和“平衡”无关，是所有二叉搜索树删除共有的复杂度。

第二层是传播麻烦：删除可能让子树高度下降，而旋转有时恢复高度、有时继续降高度。只要高度在降，失衡就可能像多米诺骨牌一样一层层向上传导，直到根。这一层是 AVL 特有的，也是“级联旋转”这个名字的由来。

第三层是判断麻烦：删除场景里，失衡节点的孩子 bf 可能是 0，导致“单旋还是双旋”多出一个分支。插入教材里“孩子 ±1 单旋、异号双旋”的简化规则在删除场景必须修正为“同号（含 0）单旋、异号双旋”。这一层最容易在考试和面试里翻车。

第 1 节解决第一层，第 1 至 3 节解决第二层，第 2.6、2.7 节解决第三层。带着这三层“麻烦清单”往下读，你会清楚地知道每一段在解决哪个问题。

1 删除步骤总览：一条五步流水线

1.1 把复杂流程拆成五个明确步骤

删除表面上很吓人，但拆开之后只有五个步骤，每一步都和第 9 篇的工具直接相关：

1. BST 删除：按二叉搜索树的规则找到目标节点，分“叶子、单孩子、双孩子”三种情况把它从结构上移除；
2. 回溯更新：从被删节点的父节点开始，自底向上重新计算每个祖先的高度与平衡因子；
3. 逐层检查：每到一层，检查 bf 是否越界（|bf| = 2）；
4. 失衡旋转：一旦发现失衡，根据该节点与偏高孩子、偏高孙子的方向关系选择 LL/RR/LR/RL 中的一种旋转；
5. 继续上溯：旋转后判断这棵子树的高度是否恢复原状——恢复了就停止，没恢复就带着新高度继续往父节点走，重复步骤 2 到 5，直到根。

注意步骤 5 里的分支就是上一节说的“循环退出条件”。很多初学者把删除理解成“找到节点 → 删掉 → 修一次”，如果这棵树恰好只需要修一次，那确实如此；但只要旋转让子树高度又减了 1，就必须沿着回溯路径继续。这也是为什么递归删除的代码看起来只是“删完再 rebalance 一下”，实际却天然完成了整个循环——递归返回的过程中，每一层都在做更新与检查。

还有一个值得点破的对称性：五个步骤里，只有步骤 1 真正改变树的结构，步骤 2 到 5 全部发生在“回溯”这条已经走出来的路径上。换句话说，删除的复杂度等于“一次查找（O(log n)）+ 回溯路径上每层 O(1) 的更新与旋转（O(log n)）”，两者加起来还是 O(log n)。理解了这个对称性，你就不会再问“删除为什么比查找慢那么多”——它本质上就是查找加了一段回程检查。

还要强调一点：步骤 5 的“高度恢复即停止”不是可选的优化，而是正确性的一部分。如果旋转后高度仍然减 1，你却提前停止，上面那些祖先的 bf 就是按旧高度算出来的，可能漏掉一个真实的失衡点；如果旋转后高度已经恢复，你继续上溯，结果虽然正确（因为各层高度没变、不会误判），但白白多走 O(log n) 步。所以严谨的说法是：判断必须做，做判断的代价是 O(1)，而“停止”本身省不了复杂度，只省常数。

1.2 BST 删除的三情况

不管是不是 AVL，BST 的删除本身只有三种情况，这是所有平衡树（红黑树、B 树）共用的地基。

情况一：删除叶子。 目标节点没有孩子，直接把父节点指向它的指针置空即可。比如删除节点 25：父节点 20 的右指针从“指向 25”变成“指向空”，25 就从树上消失了。

情况二：删除只有一个孩子的节点。 目标节点有一个左孩子或一个右孩子，用这个孩子顶替目标节点原来的位置。比如删除只有左孩子的节点 30，让左孩子直接“坐上”30 的位置，父节点的指针改为指向这个孩子。

情况三：删除有两个孩子的节点。 这是唯一需要动脑筋的情况。直接删掉它会让两棵子树都失去挂接点，所以标准做法是值替换：用中序后继（右子树的最小节点）或中序前驱（左子树的最大节点）的值覆盖目标节点，然后把那个后继/前驱节点从它原来的位置删掉。因为后继/前驱至多只有一个孩子（想想看：右子树的最小节点不可能有左孩子），删它就回到了情况一或情况二。值替换保证了 BST 的中序顺序不变，而且把“删双孩子”化归为“删单孩子/删叶子”。

为什么“右子树的最小节点不可能有左孩子”值得单独证明一下：设 s 是右子树的最小节点，如果 s 有左孩子，那么左孩子里存的值必然小于 s 的值，于是右子树里存在比 s 更小的节点，与“s 是最小节点”矛盾。所以 s 最多只能有右孩子；同理，左子树的最大节点最多只能有左孩子。这个“至多一个孩子”的性质是值替换策略成立的地基——它保证删除后继时永远落在简单分支，不会递归出第二个双孩子问题。

1.3 回溯更新：自底向上的唯一正确顺序

删除完成后，结构上“少了一个节点”，但高度信息已经全部过期。受影响的范围只有从被删节点（或后继节点）的父节点到根的那条祖先链，兄弟子树一个字节都没变。更新的顺序必须自底向上：先更新最靠近删除点的祖先，再逐层向上。每到一个节点，先算新高度，再算新 bf，然后决定是继续上溯、停止还是旋转。

图中标红的是删除点，标绿的是完全不受影响的兄弟子树。更新路径就是红色链上从 A 到根的每一层。有一个可以偷懒的优化：如果某一层重新计算后高度没变，那么它上面的祖先高度一定也没变，bf 自然也没变，可以提前停止上溯。插入场景里这个优化偶尔生效；删除场景里它更常见——因为很多删除根本不影响祖先高度。但注意：这个优化只在“高度没变”时成立，不能因为“bf 没变”就提前停。

2 删除引发的四种失衡：与插入同构，但有一个关键差异

2.1 四种形态与命名

删除之后，某个祖先可能变成 bf = +2（左子树比右子树高两层）或 bf = -2（右子树比左子树高两层）。具体选择哪种旋转，取决于失衡节点、它偏高的孩子、以及再往下一层的孙子这三者之间的走向：

• LL（左-左）：失衡节点 bf = +2，左孩子 bf = +1（或 0）。失衡点在左孩子的左侧更深处，做一次右旋；
• RR（右-右）：失衡节点 bf = -2，右孩子 bf = -1（或 0）。失衡点在右孩子的右侧更深处，做一次左旋；
• LR（左-右）：失衡节点 bf = +2，左孩子 bf = -1。失衡点在左孩子的右侧，先左旋左孩子，再右旋失衡节点；
• RL（右-左）：失衡节点 bf = -2，右孩子 bf = +1。失衡点在右孩子的左侧，先右旋右孩子，再左旋失衡节点。

注意括号里我写了“或 0”。这正是删除与插入不同的地方：插入时，失衡节点的偏高孩子 bf 只可能是 ±1（因为孩子的高度刚增加过）；删除时，孩子的高度根本没变，它的 bf 完全可能是 0。0 属于哪一类？答案：单旋。这个细节第 2.6 节专门讲。

2.2 LL：右旋，左孩子提上来当根

考虑删除发生在右子树深处，导致节点 P 变成 bf = +2，而 P 的左孩子 L 本身也是左高（bf = +1）。整棵子树的形状像一根向左倒的“之”字直棍。修复方式是右旋：把 L 提为子树根，P 降为 L 的右孩子，L 原来的右子树 T₂ 改挂到 P 的左边。

旋转前后，T₁、T₂、T₃ 的相对位置没有变，中序遍历依然是 T₁、L、T₂、P、T₃，BST 性质安然无恙。旋转后 P 的新高度取决于 T₂ 与 T₃ 中较高者，L 的新高度取决于 T₁ 与 P 中较高者。

把高度算一遍能更清楚地看到“级联是否继续”的机制。设 P 失衡前 bf = +2，右子树 T₃ 高 a，那么左子树（以 L 为根）高 a + 2，P 本身高 a + 3。若 L 的 bf = +1，则 T₁ 高 a + 1、T₂ 高 a；右旋后 P 的左右子树分别高 a 和 a，新 P 高 a + 1，新 L 高 a + 2——子树总高度从 a + 3 降到 a + 2，正好减 1，级联继续。若 L 的 bf = 0，则 T₁、T₂ 都高 a + 1；右旋后新 P 高 a + 2，新 L 高 a + 3——总高度 a + 3 保持不变，级联停止。同样的两个算式，删一次、验一次，比背结论牢靠得多。

2.3 RR：左旋，镜像对称

RR 是 LL 的镜像：失衡节点 P 的 bf = -2，右孩子 R 的 bf = -1，整棵子树向右倒。把 R 提为根，P 降为 R 的左孩子，R 原来的左子树 T₂ 改挂到 P 的右边。

删除场景下 RR 的典型触发方式：左子树变矮（例如删掉左子树里的叶子），右子树维持原高，P 就从 bf = -1 掉到 -2。方向与 LL 完全对称，代码上就是把 left/right 互换。

2.4 LR：先左旋孩子，再右旋失衡节点

LR 的形状是“失衡节点向左倒，但偏高孩子向右弯”。比如 P 的 bf = +2，左孩子 L 的 bf = -1，最深处多出来的节点在 L 的右子树里。如果直接右旋 P，L 的右子树 T₂ 会挂到 P 左边，但 T₂ 本身可能很高，旋转后 P 依然可能失衡，而且子树形状会变成另一侧歪。正确的做法是分两步：先把 L 左旋（把 L 的右孩子 M 提上来当 L 的父节点），让子树变成真正的“左-左”直棍；再对 P 右旋。

最终 M 成为子树根，L 在左、P 在右，四棵子树 T₇、T₈a、T₈b、T₉ 从左到右保持中序顺序。双旋名字里带“双”，但本质就是两次单旋组合，代码里依次调用两次旋转函数即可。

双旋之后的高度变化也可以用一句话概括：把“折线”拉成“直棍”的那次预备旋转，先把孩子的高度压平一层，再对失衡节点做单旋，总高度必然减 1。因此在 2.8 的归纳表里，LR 和 RL 两行永远和“级联继续”绑定。工程实现里，双旋的顺序也不能写反：必须先旋孩子再旋失衡节点。先旋失衡节点再旋孩子，得到的是另一棵树，虽然中序顺序依然正确，但形状和高度都不对，树会悄悄失去 AVL 性质。

2.5 RL：先右旋孩子，再左旋失衡节点

RL 是 LR 的镜像：P 的 bf = -2，右孩子 R 的 bf = +1，最深处在 R 的左子树。第一步右旋 R，把 R 的左孩子 M 提上来；第二步左旋 P，让 M 成为子树根。过程与 2.4 完全对称，这里不再重复搬树，直接给出前后对照：

到这里，四种旋转的“形状识别”和“旋转方向”都和插入一模一样，唯一的新问题就是第 2.1 节提到的那个“或 0”。

2.6 易错点：删除场景里，孩子 bf = 0 时该选单旋还是双旋？

这是删除场景下最经典的陷阱，值得单独开一节讲透。

先说结论：当失衡节点的偏高孩子 bf = 0 时，单旋即可，不要做双旋。 为什么这个结论在插入里从来没人强调？因为插入场景中，失衡节点的孩子高度刚被“拔高”过，它的 bf 只可能是与失衡方向同号的 ±1，或者是 0（对应同号），绝不可能是异号 0 之外的第三种状态；换句话说，插入代码里“孩子 bf 与失衡方向相反就双旋、否则单旋”的判断永远不会遇到“孩子 bf = 0 却需要双旋”的情况。而删除场景里，孩子的高度没有变，bf = 0 是常见状态：左子树和右子树一样高，完全合法。

现在设 P 失衡为 bf = +2（左子树比右子树高两层），左孩子 L 的 bf = 0（L 的左右子树一样高，高度都是 h）。删除发生在 P 的右子树里，让右子树从 h 掉到 h - 1。注意 L 完全没被碰过，它的左右子树依然各高 h。对 P 做一次右旋：L 成为根，P 成为 L 的右孩子，L 原来的右子树 T₂（高度 h）挂到 P 的左边。旋转后，P 的左子树高 h、右子树高 h - 1，bf = +1，高度 h + 1；L 的左子树高 h、右子树高 h + 1，bf = -1，高度 h + 2。子树总高度从原来的 h + 2（P 的左孩子 L 高 h + 1）变为 h + 2，高度不变。

等等，上段最后一句要仔细算：P 的左孩子 L 的高度是 h + 1，P 的右子树高度是 h - 1，所以 P 的高度 = 1 + max(h + 1, h - 1) = h + 2。旋转后 L 的高度 = 1 + max(h, h + 1) = h + 2。你看，整棵子树的高度恰好恢复成旋转前的高度。高度不变意味着什么？意味着 P 上面的祖先看到的左/右子树高度与删除前完全一致，它们不需要任何修复——旋转一次，级联停止。

再对比另一个状态：还是 P 的 bf = +2，但左孩子 L 的 bf = +1（L 的左子树高 h + 1、右子树高 h，于是 h(L) = h + 2）。右旋之后，P 的左子树（T₂，高 h）与右子树（高 h - 1）只差 1，P 的 bf = +1，高度 h + 1；L 的左右子树分别高 h + 1 和 h + 1，L 的 bf = 0，高度 h + 2。子树总高度从 h + 3 变成 h + 2，减少了 1。这一减，上面的祖先就可能突然失衡，必须继续上溯。

判断逻辑因此非常干净：看偏高孩子的 bf，与失衡方向同号（含 0）就单旋，异号才双旋；对 bf=0 的孩子做双旋“依然合法但多余”，还会干扰“高度恢复即停止”的流程。

所以判断逻辑非常干净：看偏高孩子的 bf——与失衡方向同号（含 0）就单旋，异号才双旋。写代码时最容易犯的错有两个：一是沿袭插入教材里的简化说法“孩子 bf = ±1 时单旋”，把 0 漏掉；二是把“孩子 bf 不是异号”机械地当成双旋。如果对 bf = 0 的孩子做双旋会怎样？结果通常还是一棵合法的 AVL 树，因为双旋把中间节点提上来后依然平衡，但旋转次数白白多了一次，而且对于“子树高度”的判断会改变修复流程的走向，代码逻辑容易和“高度恢复即停止”的优化打架。更重要的是，面试和考试里这道题几乎必考：删除后孩子 bf = 0，问该单旋还是双旋——答案是单旋。

为什么对 bf = 0 的孩子做双旋“依然合法但多余”？可以这样看：双旋的本质是把孩子的另一个孩子（中间节点）提上来当根，而单旋是把孩子自己提上来当根。当孩子 bf = 0 时，它的两个子树一样高，无论提哪一个上来，树的形状和高度都是一样的——双旋只是多转了一圈，最终结果等价于单旋。这个“等价但浪费”的性质是删除独有的：插入场景根本不存在 bf = 0 的失衡孩子，所以插入代码不会遇到这个问题；删除代码如果写错，行为依然是平衡的，靠“跑一遍没崩”根本测不出来，必须靠旋转计数或对照测试才能发现。这也是 4.7 节建议暴露旋转计数的原因。

2.7 插入与删除的“孩子 bf 状态空间”对照

把失衡节点、偏高孩子的 bf 所有可能组合摆成一张表，插入与删除的差异就一览无余：

失衡节点 bf	孩子 bf	旋转类型	插入场景	删除场景
+2	+1	LL 单旋	出现	出现
+2	0	LL 单旋	不出现	常见
+2	-1	LR 双旋	出现	出现
-2	-1	RR 单旋	出现	出现
-2	0	RR 单旋	不出现	常见
-2	+1	RL 双旋	出现	出现

为什么插入不会出现“孩子 bf = 0”？因为插入场景里，这个孩子恰好是新节点所在的子树根，它的高度刚刚增加过 1，bf 也随之改变了 1。假如孩子原来的 bf 是 -1，插入发生在它的左子树，那么新 bf 变成 0——但此时孩子的“高个子子树”是右子树，高度根本没变，孩子的总高度也就没变，于是失衡节点 P 的左子树高度不会增加，P 根本不会变成 +2。反过来，如果孩子原来的 bf 是 +1，插入发生在它的左子树，孩子自己会先变成 +2 并率先失衡，被更低层的 rebalance 修好，等轮到 P 时形状已经改变。所以当 P 真正以 bf = +2 站到你面前时，孩子的 bf 只可能是 +1 或 -1，0 那一格在插入里永远是空的。

删除则完全相反：孩子根本没被碰过，它的高度和 bf 保持删除前的值，而 bf = 0 本来就是合法状态，所以“P = +2、孩子 = 0”不仅可能出现，而且相当常见——任何一棵左右子树等高的子树，在另一侧被删掉一层后，都会把这种状态送到你面前。记住这张表，等于把易错点从“背结论”升级成“看状态空间”：同号含零单旋、异号双旋，一句话覆盖全部六格。

2.8 删除后子树高度变化的归纳

旋转选对之后，级联是否继续由“子树高度变没变”决定。把全部六种情形归纳成一张表（设失衡节点 P 原来的高度为 H）：

失衡节点 bf	孩子 bf	旋转	旋转后子树高度	级联
+2	+1	右旋（LL）	H - 1，减 1	继续上溯
+2	0	右旋（LL）	H，不变	停止
+2	-1	左旋孩子 + 右旋（LR）	H - 1，减 1	继续上溯
-2	-1	左旋（RR）	H - 1，减 1	继续上溯
-2	0	左旋（RR）	H，不变	停止
-2	+1	右旋孩子 + 左旋（RL）	H - 1，减 1	继续上溯

这张表的记忆锚点有两个。第一个锚点是“只有孩子 bf = 0 的那一行，高度不变”：因为孩子两侧一样高，无论把它旋到哪一侧，新根都只是“平移”了高度，没有损失任何一层。第二个锚点是“其余五行全部减 1”：单旋把偏高孩子提上来时，原来位于下层的一棵子树被“垫”到失衡节点下方，总高度少了一层；双旋本质上也是两次单旋的组合，最终高度同样减 1。这两个锚点合起来就是级联的全部真相：高度减 1 才会惊动祖先，高度不变则天下太平。

还有一点要澄清：表中的“H”是失衡节点的子树高度，不是整棵树的高度。旋转只影响这棵子树，它上面的祖先是否失衡，取决于这棵子树的新高度与祖先另一侧子树高度的差值。减 1 后仍然平衡，说明祖先的偏斜余量够大；减 1 后恰好跌到 ±2，就轮到祖先登场。案例六就是“每一层都恰好不够”的极端情况。

3 完整示例：构建一棵 AVL，然后逐个删除

这一节用具体的数字把删除流程完整走一遍。为了和上一篇文章衔接，我们沿用第 9 篇的经典序列 50, 30, 70, 20, 40, 60, 80, 10, 25 构建初始树。第 9 篇已经逐步验证过：这个序列插入时不需要任何旋转，得到的树就是一棵标准的 AVL 树，我们把它的高度和平衡因子标在节点旁，作为下面所有案例的起点 T₀。

3.1 起点 T₀：9 个节点，两处“左高”

从下往上验算一遍：10、25、40、60、80 都是叶子，高度 0、bf 0；20 的左右孩子 10、25 都是叶子，所以 h(20) = 1、bf = 0；30 的左子树以 20 为根高 1、右子树 40 高 0，所以 h(30) = 2、bf = +1；70 的左右孩子都是叶子，h(70) = 1、bf = 0；50 的左子树高 2、右子树高 1，所以 h(50) = 3、bf = +1。所有节点的 bf 都在 {-1, 0, +1} 内，合法。注意 30 和 50 的 bf 都是 +1：它们“左比右高一格”，这是 AVL 允许的状态，但也意味着它们的左子树里一旦再少一个节点，就可能直接掉到 +2。

顺带交代一下构建过程：序列 50, 30, 70, 20, 40, 60, 80, 10, 25 是一个“分层有序”的序列——先插根，再插根的左右孩子，再插孙辈，最后补漏。按这个顺序插入时，每一个新节点都落在当时树的“最外层”，任何祖先的左右高度差都不会超过 1，因此九次插入零旋转就完成了构建。这不是巧合，而是“按层插入”这种输入形态对 AVL 特别友好；换个顺序（比如升序）插入，第 9 篇的旋转就会立刻登场。构建过程本身不是本篇重点，但如果你想亲手验证，可以在纸上按插入顺序逐步更新高度，每步检查 |bf| ≤ 1。

3.2 案例一：删叶子 25——最简单的删除

先删叶子 25。BST 删除规则里它是情况一：直接把 20 的右指针置空。随后回溯：20 重新计算后只有左孩子 10，h(20) = 1、bf = +1，高度没变；30 的左子树高度仍为 1、右子树仍为 0，h(30) = 2、bf = +1，也没变；50 同理不变。三层全部检查完毕，没有任何节点失衡，删除结束。

这个案例看起来平淡，但它揭示了删除与插入的另一个对比：删除不一定让任何节点变矮。25 被删后，20 依然靠 10 维持高度 1，整条祖先链的高度全部保持不变，因此这次删除对树的形状几乎没影响。很多实际删除都属于这一类。

3.3 案例二：删叶子 40——触发“孩子 bf = 0 的单旋”

接下来重放 T₀，删除叶子 40。40 在 30 的右子树里，删掉后 30 的右子树从“叶子 40（高度 0）”变成“空（高度 -1）”，于是 h(30) = 1 + max(1, -1) = 2、bf = 1 - (-1) = +2——失衡了。它的左孩子是谁？20，而 20 的左右孩子 10、25 都是叶子，bf = 0。

这正是 2.6 节那个易错点：孩子 bf = 0，选择单旋。对 30 做一次右旋：20 提为子树根，30 降为 20 的右孩子，20 原来的右子树（空）挂到 30 的左边。旋转后，30 只有左孩子 25，h(30) = 1、bf = +1；20 的左右子树分别以 10 和 30 为根，高度都是 1，所以 h(20) = 2、bf = 0。整棵子树的“总高度”从 2 变成 2——高度不变。按照 1.1 的流水线，高度不变意味着上面的祖先安全，50 只需把左子树高度记为 2，h(50) = 3、bf = +1，检查完毕，一次旋转收工。

注意这里的一个细节：因为孩子 bf = 0，这次旋转没有让子树高度下降，所以级联在第一时间停止。如果面试官追问“删除的旋转会不会像插入一样必然让高度恢复”，答案是否定的——只有孩子 bf = 0 时才会恢复；孩子 bf = ±1 时高度反而会下降，级联继续。下一节的级联案例会演示后一种情况。

3.4 案例三：删单孩子 20——孩子直接顶替

回到 T₁（删掉 25 之后的树）。此时 20 只有左孩子 10，是标准的“单孩子”节点。删除 20，情况二：让 10 直接顶替 20 的位置。回溯：30 的左子树从“以 20 为根、高 1”变成“叶子 10、高 0”，右子树 40 高度 0，所以 h(30) = 1、bf = 0；50 的左子树高度从 2 变成 1、右子树仍为 1，h(50) = 2、bf = 0。全树无失衡。

单孩子删除的代码实现非常短：“return 唯一的孩子”。关键是把“顶替”这件事交给父节点——递归返回时父节点用返回值覆盖原来的指针，孩子就自然坐上了被删节点的位置。这个案例再次说明：结构上的删除永远发生在叶子层（或等价于叶子层），真正复杂的永远是之后的回溯修复。

3.5 案例四：删双孩子 30——值替换后同样可能失衡

再重放 T₀，删除双孩子节点 30。步骤：找中序后继——30 的右子树是 40，40 没有左孩子，所以后继就是 40；把 40 的值覆盖到 30 的位置；然后删除原来位置上的 40（叶子，情况一）。删除 40 后，新节点 40（继承了两棵子树）的左孩子是 20、高度 1，右孩子为空、高度 -1，所以 h(40) = 2、bf = +2——失衡了！

注意失衡点是“值替换后的 40”，而不是原来的 30。它的左孩子 20 的 bf 是 0（左右各一个叶子），于是又是单旋：右旋 40，20 提为根，40 降为右孩子，20 原来的右子树 25 挂到 40 左边。旋转后 40 只有左孩子 25，bf = +1；20 的左右子树各高 1，bf = 0；子树总高度从 2 变成 2，高度不变，级联停止。

这个案例有三个值得记住的点：第一，双孩子删除通过值替换化归为删叶子，代码里不需要处理“把两棵子树并起来”这种复杂操作；第二，值替换之后的新节点照样可能失衡，回溯修复的流程一视同仁；第三，这又是一个孩子 bf = 0 的单旋，证明 2.6 节的结论不是孤例，而是删除场景里的常态。

3.6 案例五：LR 双旋——异号才需要两步

下面单独看一个需要双旋的删除。用序列 13, 22, 11, 16, 23, 1, 18, 12, 5 构建一棵 AVL（同样不需要任何插入旋转），然后删除 22。22 是双孩子节点：左子树以 16 为根（16 的右孩子是 18），右孩子是 23。中序后继是 23，把 23 覆盖到 22 的位置，然后删除叶子 23。此时新节点 23 的左孩子 16 高度 1、右子树为空，bf = +2——失衡。关键看它的左孩子 16：16 的左子树为空、右孩子 18 高 0，所以 bf = -1，与失衡方向异号，必须双旋。

第一步，左旋 16：把 18 提上来，16 变成 18 的左孩子，子树变成“23 → 18 → 16”的向左直棍。第二步，右旋 23：把 18 提为子树根，23 降为 18 的右孩子。最终以 18 为根的子树是 18(16, 23)，高度从 2 降到 1，上面 13 的左子树高 2、右子树高 1，bf = +1，合法，无需再修。

对照案例二和案例四：那里孩子 bf = 0，单旋后子树高度不变；这里孩子 bf = -1，双旋后子树高度减 1。高度减了，理论上要继续上溯——幸好 13 本来左右高度只差 0，减完之后变成 +1，仍然合格。如果 13 的右子树再高一点，就会引出下一节的级联场景。

3.7 案例六：级联旋转——删一个节点，转两次旋

终于到了删除最“名场面”的部分：一次删除引发两次旋转，失衡点从深层一路冒到根。用序列 6, 2, 9, 7, 3, 1, 13, 12, 15, 4, 8, 10 构建一棵 12 节点的 AVL 树（依旧零插入旋转），然后删除叶子 1。

删除 1 之后，先回溯到节点 2：左子树变成空，右子树以 3 为根、高度 1，所以 h(2) = 2、bf = -2，第一处失衡出现。看右孩子 3：左子树为空、右孩子 4 高 0，bf = -1，与失衡方向同号——RR 单旋。左旋 2：3 提为根，2 降为左孩子，3 原来的左子树（空）挂到 2 右边。旋转后，2 的左右孩子都为空，h(2) = 0；3 的左子树高 0、右子树高 0，h(3) = 1、bf = 0。以 2 为根的原子树高度从 2 降到 1——高度下降了，级联不能停！

带着“左子树高度从 2 变成 1”的新事实继续上溯到根 6：左子树高 1、右子树以 9 为根高 3，所以 h(6) = 4、bf = -2——第二处失衡，而且失衡点真的就是根。看右孩子 9：左子树以 7 为根高 1、右子树以 13 为根高 2，bf = -1，同号，继续 RR 单旋。左旋 6：9 成为新根，6 降为 9 的左孩子，9 原来的左子树 7 挂到 6 的右边。旋转后 6 的左右子树分别以 3 和 7 为根、高度都是 1，h(6) = 2、bf = 0；9 的左子树高 2、右子树高 2，h(9) = 3、bf = 0。修复完成：

两次旋转的链路是：第一轮把 2 的子树压矮一层，根 6 因此从 bf=-1 跌到 -2；第二轮左旋 6 后，9 成为新根，整棵树才恢复平衡。层数更多时，这种“每层都恰好减一”的传播可以重复更多次。

这就是“删除可能一路失衡到根”的完整现场：一次叶子删除，第一层旋转把子树高度压矮了一层，根因此被“暴露”成新的失衡点，第二层旋转才把整棵树修平。如果树的层数更多、且每一层旋转后高度都下降，理论上可以出现更多次旋转——最坏情况下旋转次数等于回溯经过的层数，也就是 O(log n)。

如果想亲手构造“每一层都失衡”的最坏树，思路是让整棵树几乎每个节点都保持 bf = ±1 的临界状态（就是 5.1 节的斐波那契树），然后在最深处删除一个会让路径上每层都“减一层”的节点。这类构造在随机测试里几乎不会自然出现，所以很多实现“跑了几万次都没问题”，却在一次精心构造的删除面前暴露 bug。这也是为什么本文反复强调：验证 AVL 删除，不能只靠随机数据，必须包含刻意构造的最坏输入。

把六个案例放在一起看：叶子删除可能完全无感（案例一），也可能触发孩子 bf = 0 的单旋且级联立即停止（案例二）；单孩子删除靠“顶替”完成（案例三）；双孩子删除用值替换化归，替换后照样可能失衡并触发 bf = 0 的单旋（案例四）；异号失衡需要双旋，且旋转后高度会下降（案例五）；高度下降一旦传导到更高层，就形成多旋转的级联（案例六）。删除的全部面貌，到此就齐了。

3.8 收尾实验：把级联后的树一路删到空

级联案例修复完成后，我们得到一棵 11 节点的 AVL 树。如果继续按顺序删除 4、8、10、15、2、7、12、3、13、6、9，会发生什么？答案可能出乎意料：这 11 次删除一次旋转都不需要。每删一个节点，回溯路径上的祖先高度要么不变，要么减 1 后依然平衡，始终没有节点跌破 ±2。我们用程序验证过这一点，它很好地提醒我们：删除“可能”级联旋转，不代表“经常”级联旋转。平均情况下，大多数删除都像案例一那样波澜不惊，只有结构刚好走到临界状态时，才会触发一次或多次旋转。

这也解释了为什么实际工程里 AVL 的删除并不比插入“慢得离谱”：虽然最坏情况是 O(log n) 次旋转，但这个最坏情况要求每一层都恰好处于“临界偏斜”状态，出现的概率很低。更精细的分析（本文只给直觉）表明，删除触发的旋转次数在平均意义上是常数级，只是常数比插入大。把“最坏保证”和“平均表现”分开记，就不会被“删除最坏 O(log n) 旋转”吓住：上限是数学事实，频率是统计事实，两者不矛盾。

还有一个小问题值得注意：删到最后一个节点时，树变成空，root 指针正确地变回 null。递归实现不需要特判“删空”，因为每一层返回 null 最终都会传回入口，this.root = this.deleteNode(this.root, key) 自然把根置空。这个“一路返回 null”的过程也是理解递归删除的绝佳练习：在纸上把最后一个节点的调用栈画出来，你会发现它其实就是最普通的叶子删除，只是恰好发生在根上。

3.9 边界情况：删除不存在的键、删除根、删到空树

除了三种结构情况，删除还有三个边界值得单独说。第一个是删除不存在的键：递归一路走到空节点返回 null，各层 rebalance 计算后高度不变，整棵树原样返回。实现上不需要任何特判，正确性是递归结构白送的；但要注意“删除成功与否”的返回值设计——如果调用方需要知道是否删掉了，可以返回一个“是否找到”的标记，而不是用返回 null 表示“没找到”，因为删除叶子时正常的返回值也是 null，两者会混淆。

第二个是删除根：根可能属于三种情况中的任意一种。删叶子根，树变空，root 置 null；删单孩子根，孩子成为新根；删双孩子根，值替换后真正的删除发生在子树里，root 指针通过递归返回值更新。递归版里这一切都是自然的，唯一的坑是迭代版里要单独处理“path 为空”的情形——4.6 节的伪代码里已经标出。

第三个是删到空树再继续删：这时 root 为 null，delete 直接返回，不报错、不改状态。对数据库索引这类“删除可能追上插入”的系统，空树的幂等行为很重要。把这三个边界写进测试，删除实现才算真正闭环。

4 代码实现：delete + rebalance 的完整 TypeScript 实现

4.1 节点结构与辅助函数

下面给出完整的 TypeScript 实现。节点与第 9 篇插入实现完全同构：每个节点保存键、左右孩子指针和高度；平衡因子不单独存储，而是需要时由左右子树高度现场计算。这样做的最大好处是永远不会出现“存了 bf 却忘了更新”的经典 bug——高度是旋转与重平衡共同维护的唯一状态，bf 只是它的一个投影。

type AVLNode<T> = {
  key: T;
  left: AVLNode<T> | null;
  right: AVLNode<T> | null;
  height: number;
};

class AVLTree<T> {
  root: AVLNode<T> | null = null;

  private height(node: AVLNode<T> | null): number {
    return node ? node.height : -1;
  }

  private updateHeight(node: AVLNode<T>): void {
    node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
  }

  private balanceFactor(node: AVLNode<T> | null): number {
    return node ? this.height(node.left) - this.height(node.right) : 0;
  }

  private rotateRight(y: AVLNode<T>): AVLNode<T> {
    const x = y.left!;
    const t2 = x.right;
    x.right = y;
    y.left = t2;
    this.updateHeight(y);
    this.updateHeight(x);
    return x;
  }

  private rotateLeft(x: AVLNode<T>): AVLNode<T> {
    const y = x.right!;
    const t2 = y.left;
    y.left = x;
    x.right = t2;
    this.updateHeight(x);
    this.updateHeight(y);
    return y;
  }

  private rebalance(node: AVLNode<T>): AVLNode<T> {
    this.updateHeight(node);
    const bf = this.balanceFactor(node);

    if (bf > 1) {
      if (this.balanceFactor(node.left!) < 0) {
        node.left = this.rotateLeft(node.left!);
      }
      return this.rotateRight(node);
    }

    if (bf < -1) {
      if (this.balanceFactor(node.right!) > 0) {
        node.right = this.rotateRight(node.right!);
      }
      return this.rotateLeft(node);
    }

    return node;
  }

  delete(key: T): void {
    this.root = this.deleteNode(this.root, key);
  }

  private deleteNode(node: AVLNode<T> | null, key: T): AVLNode<T> | null {
    if (node === null) return null;

    if (key < node.key) {
      node.left = this.deleteNode(node.left, key);
    } else if (key > node.key) {
      node.right = this.deleteNode(node.right, key);
    } else {
      if (node.left === null || node.right === null) {
        return node.left ?? node.right;
      }
      const successor = this.minNode(node.right);
      node.key = successor.key;
      node.right = this.deleteNode(node.right, successor.key);
    }

    return this.rebalance(node);
  }

  private minNode(node: AVLNode<T>): AVLNode<T> {
    let cur = node;
    while (cur.left !== null) cur = cur.left;
    return cur;
  }
}

4.2 逐行解释：删除的核心路径

入口 delete(key)。 公开方法只做一件事：把根替换为递归删除的返回值。递归函数的返回值语义是“以 node 为根的子树在删除并重平衡之后的新根”。这个返回值可能是原节点（没删到、或删到但平衡没变）、可能是孩子的顶替、也可能是旋转后的新根。所有修改都通过返回值逐层向上传播，父节点只要执行 node.left = deleteNode(node.left, key) 就能拿到正确的新子树。

递归查找分支。 key < node.key 时目标在左子树，递归结果写回 node.left；key > node.key 时对称。这两行代码完成了“查找 + 删除 + 修复”三件事，因为递归返回前已经对整棵子树完成了 rebalance。

命中分支。 node.left === null || node.right === null 覆盖了 BST 删除的情况一和情况二：叶子返回 null（父指针被置空），单孩子返回唯一的孩子（孩子顶替）。node.left ?? node.right 是“取非空的那一个，都空则取 null”的简洁写法，等价于“有左返左，否则返右”。注意这里没有调用 rebalance——被删节点自己已经退场，不需要再平衡自己；它的父节点会在自己的 rebalance 里处理。

双孩子分支。 minNode(node.right) 找到右子树的最小节点，也就是中序后继；用它的键覆盖当前节点，然后递归删除右子树里的那个后继。为什么一定是后继而不是随便挑一个？因为中序后继是“下一个比当前节点大的键”，覆盖后中序序列不变；而右子树的最小节点没有左孩子，删除它必然落到上面的叶子/单孩子分支，问题规模就被化归了。这里也可以换用中序前驱（左子树的最大节点），实现镜像对称，效果等价。

重平衡：rebalance(node)。 这是删除实现的心脏，也是与插入实现唯一实质相同的部分。进入函数先更新自己的高度，再算 bf。bf > 1 表示左重，检查左孩子：若左孩子 bf < 0，说明方向是“先左后右”，需要先左旋左孩子（LR 的第一步）；无论左孩子是 +1 还是 0，最后都右旋（LL）。bf < -1 对称：右孩子 bf > 0 时先右旋右孩子（RL 的第一步），再左旋（RR）。注意这个判断对 bf = 0 的孩子自动选择单旋——这正是 2.6 节强调的易错点，代码里一行注释都没有，行为却完全正确：因为 bf(child) < 0 为假，直接进入右旋。

级联是怎么自动完成的。 递归返回的每一层都执行一次 return this.rebalance(node)，等价于流水线里的“回溯 → 更新高度 → 检查 → 失衡旋转”。如果某一层旋转后子树高度不变，上面各层重新计算后会发现高度不变、bf 不变，什么也不做；如果高度下降，上面某层会算出 bf = ±2，继续旋转。所以代码不需要显式地写循环，递归栈本身就是回溯路径，每一层都做一次检查。这也是递归实现最优雅的地方：流程的“继续上溯”是语言机制送的，而不是手动维护的。

minNode。 一路向左走到底，返回最左节点。因为二叉搜索树的性质，它就是子树中的最小键。

4.3 几个实现层面的注意事项

第一，旋转后必须更新高度，且顺序是先孩子后新根。rotateRight 里先 updateHeight(y) 再 updateHeight(x)：y 现在是 x 的子树，必须先把 y 的高度算准，x 才能用 y 的新高度算自己。顺序写反是旋转代码最常见的 bug，症状是“删几次之后树悄悄失衡”。第二，rebalance 里先 updateHeight 再算 bf，不能在递归修改子树后直接使用旧 bf。第三，递归实现的深度等于树高，AVL 树高是 O(log n)，所以不会爆栈；如果你坚持用迭代实现，需要自己维护一个显式栈来保存回溯路径，并在弹栈时依次重平衡——逻辑完全等价，但代码量明显增加。第四，删除不存在的键时，递归一路走到 null 返回，各层 rebalance 计算后高度不变，整棵树原样返回，行为是安全的幂等操作。

4.4 从删除到完整的操作集

把第 9 篇的插入、查找和本篇的删除放在一起，AVL 树的核心操作就齐全了：查找不修改树，沿路径比较即可；插入在递归返回时重平衡，一次插入至多一次旋转；删除在递归返回时重平衡，一次删除可能多次旋转，最坏为 O(log n) 次。三段代码共享同一套 height/updateHeight/balanceFactor/rotateRight/rotateLeft/rebalance 基础设施——这正是“旋转是唯一扳手”这句话在工程上的体现：基础设施只写一遍，插入和删除各写一份递归外壳。

还有一句关于 rebalance 的补充：函数里不需要显式判断“旋转后高度是否恢复、要不要继续上溯”，因为“继续上溯”已经由递归返回隐含完成——每一层返回前都执行一次 rebalance，该转就转，不该转就原样返回。如果你把“高度是否恢复”的判断硬塞进 rebalance，反而会让代码变得绕：那本是调用者（递归壳）的职责，而递归壳已经用“每层都调用”的方式把它做完了。

4.5 常见 bug 清单

把删除实现里最容易踩的坑列成清单，写代码时逐条对照：

1. 旋转后高度更新顺序颠倒：先更新新根、再更新子树根，导致高度算错。规则：先 updateHeight 孩子（现在位于下层的节点），再 updateHeight 新根。
2. rebalance 之前忘了 updateHeight：递归修改子树后直接用旧高度算 bf，失衡方向可能被误判，进而选错旋转。
3. 双孩子分支忘了递归删除后继：只覆盖了键，却没有删掉原来位置上的后继，树里出现两个相同键，中序序列被破坏。
4. 叶子/单孩子分支返回后没有让父节点重平衡：递归壳写对的话不会发生，但如果你把删除拆成“先找到再手动改指针”的迭代版，很容易漏掉回溯这一整段。
5. 把 bf = 0 的孩子误判成双旋：删除场景必须记住“0 走单旋”，否则旋转次数翻倍，而且对“高度是否恢复”的判断会错，级联行为随之出错。
6. 用 bf 字段缓存却忘了更新：本文实现用“高度现场算 bf”规避了这个坑；如果你单独存 bf，每次旋转和每次高度变化都要同步更新，漏一处就埋一个雷。
7. minNode 找错方向：中序后继是右子树一路向左，中序前驱是左子树一路向右，方向写反会破坏 BST 性质。
8. 递归返回值没有赋给父指针：写了 deleteNode(node.left, key) 却忘了 node.left = ...，删除结果会“丢在半路”，树甚至可能出现悬空指针。

这份清单同样适用于插入实现，但删除特别容易中 5、6、8 三条，因为删除路径上要同时处理“结构移除”和“级联修复”两件事，心智负担更重。建议写完代码后用三组测试自检：删叶子、删单孩子、删双孩子各跑一遍；再按升序插入、降序删除构造最坏输入，最后用随机序列做几百次插入删除，每一步都断言全树 |bf| ≤ 1。能自动验证的平衡性质，就不要依赖肉眼检查。

4.6 迭代实现思路：显式栈版

递归实现靠调用栈保存回溯路径，简洁但有两个现实问题：一是有些环境对递归深度有限制（AVL 树高是 O(log n)，一般没事，但极端场景可能踩到栈深度配置）；二是面试里常被要求“能不能不用递归”。迭代版的核心是把“回溯路径”显式地存下来：

deleteIterative(key):
  path = []                 // 显式栈，保存从根到目标路径上的节点
  cur = root
  while cur != null && cur.key != key:
    path.push(cur)
    if key < cur.key: cur = cur.left
    else: cur = cur.right
  if cur == null: return    // 没找到，直接结束

  // 1. 结构删除（叶子 / 单孩子 / 双孩子）
  if cur.left == null || cur.right == null:
    child = cur.left ?? cur.right
    if path 为空: root = child          // 删的是根
    else: 把 child 挂到 path 栈顶对应的指针上
  else:
    successor = minNode(cur.right)
    cur.key = successor.key
    // 从 cur.right 一路向左走到 successor，把这段路径也压栈
    p = cur.right
    while p != successor:
      path.push(p)
      p = p.left
    // 现在按“叶子/单孩子”规则删除 successor

  // 2. 弹栈重平衡
  while path 不为空:
    node = path.pop()
    node = rebalance(node)   // 返回值写回父指针（或 root）

伪代码里最容易出错的地方在双孩子分支：值替换后，真正被删的是右子树里的后继，所以“路径”必须重新拼接——从原来的目标节点继续走到后继，把这段新路径也压栈，否则弹栈时漏掉了目标节点到后继之间的祖先。相比递归版，迭代版的优势是流程完全可见（每一步都能断点观察），代价是路径管理代码变长、出错面变大。工程上，除非有明确理由（例如递归深度受限、需要无栈版本），优先用递归版；递归版把“回溯”交给语言，你只需要保证 rebalance 正确。

4.7 测试与验证：怎么证明删除实现是对的

平衡树的 bug 往往“当时没事、删着删着才炸”，所以一定要用自动验证代替肉眼检查。最实用的验证器是一个递归函数：检查每个节点的 |bf| ≤ 1，同时检查左右子树各自合法、以及“孩子高度 + 1 等于父节点高度”。任何一个违反都立刻抛错。有了验证器，测试就变成三组脚本：

第一组，结构覆盖测试：用一棵小树分别删除叶子、单孩子、双孩子（包括删根），每次删除后跑验证器，再跑中序遍历检查顺序仍然递增。第二组，退化输入测试：按升序插入 1 到 n，再按降序删除；再按降序插入、升序删除；再交替插入删除。这些输入会把旋转路径全部逼出来，尤其是删除的级联分支。第三组，随机对拍测试：维护一个有序数组作为“标准答案”，随机执行几千次插入/删除，每步用验证器检查树结构，并用中序遍历与数组内容比对。对拍测试通常能在一个晚上抓出所有边界 bug——包括最容易漏的“删除不存在键”和“删空树”。

还有一个小技巧：把旋转计数暴露出来。插入时断言“单次插入旋转次数 ≤ 2”，删除时断言“单次删除旋转次数 ≤ 树高”。这个断言不是复杂度优化，而是行为契约：一旦实现把 bf = 0 误判成双旋，旋转计数立刻报警，比等树失衡再查快得多。

5 复杂度：为什么 AVL 树的高度被锁死在 O(log n)

5.1 反问题：高度为 h 的 AVL 树至少有几个节点

要证明 AVL 树的操作都是 O(log n)，核心是证明一个事实：高度为 h 的 AVL 树至少有“指数级”个节点。反过来，n 个节点的 AVL 树高度至多是某个关于 log n 的量级。怎么证明？用反证思路很难，用递推却非常直接。

设 F(h) 为“高度恰好为 h 的 AVL 树最少有多少个节点”。为了最小化节点数，根的两个子树应该尽量不平衡——但 AVL 规则只允许差 1，所以一棵子树取“高度 h - 1 的最少节点树”，另一棵取“高度 h - 2 的最少节点树”，再加上根自己，就得到递推：

F(0) = 1
F(1) = 2
F(h) = 1 + F(h - 1) + F(h - 2)   （h ≥ 2）

这个递推长得几乎和斐波那契数列一样，只是多了“+1”。前几项：F(0) = 1，F(1) = 2，F(2) = 1 + 2 + 1 = 4，F(3) = 1 + 4 + 2 = 7，F(4) = 1 + 7 + 4 = 12，F(5) = 1 + 12 + 7 = 20。把前 11 项列成表：

高度 h	0	1	2	3	4	5	6	7	8	9	10
最少节点 F(h)	1	2	4	7	12	20	33	54	88	143	232

可以看到节点数增长得飞快：高度 10 的“最瘦 AVL 树”也有 232 个节点，高度 20 就有几十万个。换句话说，想用 AVL 规则把树造得又高又瘦是做不到的，高度每加一层，节点数至少要乘上约 1.618。反过来念更有用：n 个节点能容忍的最坏高度，被这张表死死压在对数量级上。

这张表还有一个很实用的反向用法：想判断一棵树的形状有多“临界”，就看它的节点数落在 F(h) 的哪个位置。一棵高度为 5 的树如果有 20 个节点，它就是“最瘦”的那一档——每个节点都顶着最大偏斜，稍微删一个叶子就可能引发级联；如果它有 30 个节点，说明内部有不少节点 bf = 0，删除的容错空间更大。这个“形状余量”的直觉，比记住任何公式都更能帮你预判一次删除会不会触发旋转。

5.2 黄金比例与 1.44 log₂(n + 2)

斐波那契数列的相邻项之比趋近黄金比例 φ ≈ 1.618，而 F(h) 几乎就是斐波那契数的平移，所以同样满足 F(h) ≥ φᵏ 这种指数下界。取对数就能翻过来：h 至多是某个常数乘以 log_φ(n)，换算成以 2 为底，就得到著名的 AVL 高度上界：

h ≤ 1.44 log₂(n + 2) - 1.33

这里的 1.44 不是魔法，它的来源就是 1 / log₂(φ) ≈ 1.44：因为每增加一层高度，最少节点数至少乘 φ，所以层数最多是节点数的“φ 进制对数”，换算到二进制对数就要乘上这个系数。想亲眼看到这个系数，可以把递推式与斐波那契数列 Fᵢ = Fᵢ₋₁ + Fᵢ₋₂ 对照：F(h) = F(h - 1) + F(h - 2) + 1 的解可以写成 φ 的幂次加上常数项，取对数后“+1”和“-1.33”只影响低阶项，主导项就是 1 / log₂(φ)。直觉上可以这样记：AVL 树的高度不超过同节点数完全二叉树高度的约 1.44 倍。n = 100 万时，log₂(n + 2) ≈ 19.9，最坏高度约 27；对比普通 BST 退化成链时的 100 万，差距是四到五个数量级。这也是第 8 篇“退化”问题最彻底的解法：不是祈祷输入均匀，而是用规则把最坏形状直接禁掉。

上面两张图就是递推的直观模样：为了最瘦，根的左右子树分别取“高度 h - 1 和 h - 2 的最瘦树”，一层层长成斐波那契树。这种树每个节点都顶着规则允许的最大偏斜（bf = ±1），是 AVL 家族里的“瘦子天花板”。

5.3 三种操作的最坏复杂度

有了高度上界，一切复杂度水到渠成：

查找：O(h) = O(log n)
插入：O(h) 找位置 + O(h) 回溯更新 + 常数次旋转 = O(log n)
删除：O(h) 找目标 + O(h) 回溯更新 + O(h) 次旋转 = O(log n)

插入与删除都包含一次“沿根到目标的路径往返”，往返长度就是树高 O(log n)。旋转的差别只体现在常数上：插入至多两次旋转（一次双旋拆成两次单旋），删除最坏 O(log n) 次单旋——但每次旋转都是 O(1) 的指针调整，所以总代价依然是 O(log n)。空间上，每个节点只多存一个高度字段，整棵树额外空间 O(n) 且常数极小。

空间开销还有一个容易被忽略的细节：如果节点用对象/结构体实现，多一个数字字段往往会让结构体变大到下一个对齐边界，实际增量可能不是“一个整数”而是“一个指针宽度”。对百万级节点，这就是几 MB 到几十 MB 的差别；对十亿级节点，可能决定内存是否够用。如果内存极其紧张，可以改用高度压缩编码（比如只存 4 位）甚至用左右子树深度差代替完整高度，但这些优化会让代码可读性显著下降——除非有实测数据支撑，一般不建议过早做。

5.4 删除旋转次数的实证直觉

1.44 log₂(n + 2) 是高度的上限，但删除的旋转次数还依赖“树里到底有多少临界节点”。什么叫临界节点？就是 bf = ±1 的节点：它的子树在删除后可能从 ±1 掉到 ±2；bf = 0 的节点反而安全，删掉一侧后最多变成 ±1。一棵满的、完全平衡的 AVL 树里，绝大多数节点 bf = 0，所以随便删一个节点，回溯路径上真正需要旋转的节点很少——案例一、案例三就是这种“大多数”。只有当你精心构造一棵“全部节点都顶着最大偏斜”的斐波那契树，删除才可能触发 O(log n) 次旋转。换句话说，AVL 的最坏高度和最坏旋转次数都是“真实存在但需要刻意构造”的上界，这恰恰是平衡树的价值：它们把最坏情况从“普通输入随手触发”降级为“刻意构造才能触发”。

另一个值得记住的对比是插入与删除的不对称：插入至多两次旋转，删除最坏 O(log n) 次，但插入的旋转在有序输入里几乎“步步惊心”，删除的旋转则往往“绕道走”。所以复杂度的教学顺序总是“先插入后删除”——插入把旋转机制讲透了，删除只是在同一个机制上加一层“可能重复”的循环。面试里如果被追问“删除最坏 O(log n) 次旋转，那为什么不选红黑树”，答案正是第 7 节的铺垫：红黑树把每次删除的旋转次数压到常数，代价是树更高、查找常数略大。

5.5 复杂度常见疑问

疑问一：递归删除的调用栈深度是多少？会不会 O(n)？ 不会。递归深度等于回溯路径长度，即从根到目标节点的距离，而 AVL 树高恒为 O(log n)，所以调用栈深度也是 O(log n)。这正是“平衡”带来的免费礼物：连递归都不会爆栈。

疑问二：旋转是 O(1) 的吗？双旋呢？ 是。单旋只重排三个指针、更新两个高度；双旋调用两次单旋，仍是常数次指针操作。复杂度分析里常说的“删除 O(log n) 次旋转”，每次旋转 O(1)，总代价 O(log n)。

疑问三：为什么要分“最坏”和“平均”？ 因为 AVL 的卖点就是最坏保证。BST 平均也是 O(log n)，但那个平均建立在“输入随机”的假设上；AVL 的 O(log n) 不依赖任何假设，恶意输入、有序输入、随机输入一视同仁。系统的实时性、安全性要求“最坏也能接受”时，平均分析是不合格的。

疑问四：高度字段用 int 够吗？ 够。高度 ≤ 1.44 log₂(n + 2)，即使节点数达到 2³²，高度也不超过 47，一个字节（带符号）都装得下。工程实现里用 int 只是图省事，用 int8 也完全不会溢出。

疑问五：为什么很少见到“删除专用”的 AVL 变体？ 因为删除与插入共用同一套旋转，变体只能优化“什么时候停止检查”这类常数细节，无法改变 O(log n) 的渐进上界。相比之下，红黑树通过放松平衡条件换来的“旋转次数从 O(log n) 降到常数”是渐进层面的改进，所以工程上更常见“插入删除都快的红黑树”，而不是“专门优化删除的 AVL”。这个对比到第 12 篇还会用数据展开。

6 AVL vs 普通 BST：一场全面的对比

6.1 同一组键，两种命运

把 1 到 7 这 7 个键分别放进普通 BST 和 AVL 树，对比立刻变得直观。普通 BST 在升序插入下会长成一根 6 层高的右倾链，查找 7 要比较 7 次；AVL 树用旋转强制自己长成矮胖形状，同样查找 7 只需要 3 次比较。内容完全相同（中序遍历都是 1, 2, …, 7），形状却天差地别：

这个对比在第 8 篇已经出现过，但放在删除语境下它还有一层新含义：删除同样会影响形状。BST 的删除完全不考虑形状，删着删着可能把一棵均匀的树删成歪树；AVL 的删除则每删一次就回溯检查一次，任何“歪”的苗头都在下一次操作前被修掉。BST 的退化是渐进的、无感知的，AVL 的修复是即时的、可预期的。

6.2 核心对比表

维度	普通 BST	AVL 树
高度（最好）	O(log n)，依赖插入顺序	O(log n)，最坏也如此
高度（最坏）	O(n)，升序/降序插入即退化	≈ 1.44 log₂(n + 2)，被规则锁死
查找代价	最好 O(log n)，最坏 O(n)	稳定 O(log n)
插入代价	找到位置后 O(1) 挂接，无回溯	回溯更新 O(log n)，至多两次旋转
删除代价	找到后指针操作 O(1)，无回溯	回溯更新 O(log n)，最坏 O(log n) 次旋转
旋转机制	没有	四种旋转（两种单旋、两种双旋）
平衡因子/高度字段	不需要	每个节点一个 height 字段
空间开销	节点 = 键 + 左右指针	额外一个整数，常数级增加
实现难度	简单，几天可写完	中上，旋转与双旋边界易错
对输入顺序的敏感度	极其敏感	完全不敏感
中序遍历	有序	有序（旋转不改变中序）
典型适用	教学、小数据、已知随机输入	需要稳定最坏时间保证的场景

表格里最值得玩味的一行是“高度（最坏）”：BST 的最坏高度 O(n) 不是理论上的极端案例，而是有序数据插入的日常；AVL 的最坏高度 1.44 log₂(n + 2) 却是“即使故意刁难也到不了更差”的硬保证。一个把“最坏情况”写进规格，另一个把“最坏情况”当成偶然事故。

关于“删除”这一行还有一个微妙的差别：BST 的删除不需要回溯，因为根本没有平衡可维护；但正因如此，BST 无法感知删除造成的偏斜累积。设想你反复插入、删除同一个键，BST 的形状可能在几十次操作后悄悄恶化，而每次单独操作看起来都“没问题”；AVL 则在每次删除后强制检查，把偏斜累积扼杀在萌芽里。所以“AVL 删除更贵”这句话要加上后半句：贵在每次操作，省在长期健康。

反过来也要问一句：什么场景下 BST 反而更合适？如果你的键集合是静态的——建好之后几乎不增删，只做查询——那么完全可以离线构造一棵“完美平衡”的 BST（类似二分查找顺序建树），它的高度就是 ⌈log₂(n + 1)⌉，比 AVL 还要矮，而且不需要任何旋转与高度字段。静态数据配静态构造，动态数据配自平衡，这个分工比“AVL 一定优于 BST”更接近工程真相。同样，如果数据量小到几十个节点，树高差一两层根本没有意义，BST 的简单反而更值钱。

6.3 代价不是免费的：AVL 多花的钱花在哪

AVL 的三个代价要诚实地说清楚。第一是旋转：插入和删除不再只是“挂一个节点、拆一个节点”，而是每次操作都可能动到指针，最坏情况下删除要沿着回溯路径转多次。旋转本身是 O(1) 的，所以复杂度没变，但常数变大了——同样的 100 万次随机操作，AVL 的 CPU 时间通常会比 BST 多个常数倍。第二是空间：每个节点多存一个高度（在 JS/TS 里是一个数字属性，在 C/C++ 里可能是一个字节的位域），在节点极小的场景下（比如只存一个整数键）内存开销比例不小。第三是实现复杂度：插入的四种旋转、删除的双旋判断、级联修复，每个都是 bug 的高发区，维护成本比 BST 高。

那为什么还要用 AVL？因为这三笔钱买来的是确定性：无论输入是有序的、倒序的、还是精心构造的恶意序列，所有操作都在 O(log n) 内完成。对实时系统、数据库查询计划、以及任何“最坏情况不能接受”的场景，确定性比平均性能更值钱。反过来，如果你的数据量很小、或者明确知道输入近似随机，BST 甚至更快的跳表都可能是更务实的选择——这就是为什么第 8 篇说“BST 没有错，错的是假设输入总是友好”。

还有一个常被忽略的经验数字：在随机插入、随机删除的长周期测试里，BST 的平均高度大约与随机二叉搜索树的期望高度同阶，也就是约 4.3 log₂n，和 AVL 的 1.44 log₂n 相比差一个 3 倍左右的常数。对百万级数据，这个常数意味着几十次比较的差距；对十亿级数据，意味着上百次比较的差距。如果这些比较背后是磁盘 I/O 或网络 RTT，差距会被放大成数量级；如果只是内存里的整数比较，差距则可能淹没在指令流水线里。选型永远要带着数据规模和访问成本一起算，这是比“谁更高级”重要得多的工程判断。

6.4 内存布局与缓存的现实视角

对比表里还有两个常被忽略的现实维度：内存与缓存。BST 的节点通常比 AVL 少一个字段，在节点数量极大时，这一点内存可能意味着“能否把更多节点装进缓存行”的差别；但现代语言里节点往往按引用分配，多一个数字字段的实际开销常常小于对齐填充造成的浪费，所以这个优势通常没有教科书渲染得那么大。更重要的是局部性：BST、AVL、红黑树都是指针跳跃式访问，树高越高，一次查找平均跳过的节点越多，缓存未命中越多。在这一点上，AVL 的矮树对缓存是友好的——这正是“读多选 AVL”论点的另一层支撑。

反过来，如果数据量大到内存装不下，任何内存树都会输给 B 树：B 树的节点是一个磁盘块大小的“桶”，一次 I/O 能读进几十上百个键，树高直接降成两三层。这个道理树系列后面的篇章会用到，这里先埋个伏笔：平衡思想是通用的，但工程载体（指针、缓存行、磁盘块）决定最终形态。

7 预告：AVL vs 红黑树，工程上的终极二选一

7.1 红黑树：用“颜色”换更少的旋转

AVL 用“高度差不超过 1”换来矮树，代价是删除时可能一路旋转。红黑树换了个思路：不追求严格平衡，只要求最长路径不超过最短路径的两倍。它给每个节点涂上红色或黑色，并用五条性质约束颜色的分布，从而把树高限制在 O(log n)——但系数比 AVL 的 1.44 更大。具体是哪五条性质、每条性质到底在约束什么、颜色翻转和旋转怎么配合，我们留到第 12 篇用一整篇的篇幅细讲。这里只需要建立两个直觉。

第一，红黑树允许更“歪”的形状。因为约束从“高度差 ≤ 1”放松成“路径长度比 ≤ 2”，同样的节点数下，红黑树通常比 AVL 树高一些，查找的常数略大。第二，红黑树插入和删除的旋转次数更少。严格平衡意味着“一点就修”，而红黑树把“容忍度”放宽后，很多小偏斜根本不需要动指针——删除场景尤其明显：AVL 最坏要 O(log n) 次旋转，红黑树删除最坏只要三次旋转（颜色调整分摊后仍然是 O(log n) 但常数小得多）。这就是工程界经典的“以高度换旋转”权衡。

先剧透一下红黑树的五条性质，方便你在下一篇里对照着看：第一条，每个节点非红即黑；第二条，根是黑色的；第三条，所有叶子（空节点）都是黑色的；第四条，红色节点的两个孩子必须是黑色的（也就是“红不连红”）；第五条，从任一节点到它每个后代叶子的路径上，黑色节点数必须相同。五条性质合在一起，就推出了“最长路径不超过最短路径的两倍”这个平衡保证。你可以在读完下一篇之后回看本文的删除流程，会发现红黑树的删除同样要处理双孩子化归、同样要回溯修复，只是“失衡”的判据从高度差换成了颜色约束。

再预告一个更深的视角：红黑树其实可以看成“2-3-4 树”的二叉化表示——把三节点、四节点拆成带颜色的二叉结构，红色节点就是“被折叠进同一层”的标记。这个视角解释了为什么红黑树允许一定的不平衡：它的平衡不是在二叉树上直接定义的，而是在底层的 2-3-4 树上定义的。第 12 篇会从这条线索讲起，你会发现“为什么是红色和黑色”终于有了一个不靠死记硬背的答案。

7.2 工程上通常怎么选

“谁更好”没有绝对答案，工程惯例是按操作画像选：

• 读多写少、追求极致查找速度：选 AVL。矮树 = 更少的比较次数，查询密集型场景（比如只读缓存、路由表）里这 1.44 与 2 的系数差是实打实的；
• 写多（插入删除频繁）：选红黑树。旋转少、颜色调整分摊成本低，动态更新的吞吐量通常更高；
• 需要区间遍历、前驱后继、排名查询：两种都支持，但红黑树因为“不那么紧”的平衡，实现里常把节点再挂上子树大小等统计字段，工程生态更成熟；
• 语言标准库：C++ 的 std::map、Java 的 TreeMap、Linux 内核的 rbtree 都是红黑树，说明在“通用场景”下红黑树的综合性价比更受欢迎；
• 数据库索引：内存里的平衡树用红黑树/AVL 都行，磁盘上则是 B 树家族的天下——这是树系列后面会展开的另一条线。

举两个具体的工程例子帮助建立体感。场景一：一个高频读、低频写的配置服务，读延迟是核心指标，节点数几十万——AVL 的矮树每次查询少比较几层，即使只差两三次比较，在每秒百万次查询的规模下也值得。场景二：一个消息队列的定时器管理，每秒大量插入和删除到期任务——旋转次数直接影响吞吐，红黑树“删除最坏三次旋转”的保证在这里就比 AVL 的“最坏 O(log n) 次”更有吸引力。两个场景用的都是平衡树，但操作画像完全不同，选型结论也完全不同。

一句话总结这节的铺垫：AVL 是“矮”的代名词，红黑树是“稳”的代名词。你不需要现在就决定用谁，第 12 篇会给出一张与本文同款的对比表，把五条性质、颜色翻转、插入删除流程和工程选型一次讲完。

7.3 动手体验：在可视化实验室里自己删一次

光看文章不如亲手操作。下面的可视化实验室支持对搜索树进行插入与删除，你可以输入本文的序列 [50, 30, 70, 20, 40, 60, 80, 10, 25]，然后依次删除 40、30，观察平衡因子从 +2 变回 +1 的过程；也可以试试 [6, 2, 9, 7, 3, 1, 13, 12, 15, 4, 8, 10] 之后删除 1，亲眼看看两次旋转是怎么沿着回溯路径级联到根的：

8 收尾：删除修复速查表、自测题与下一篇预告

8.2 自测题（先自己做，再看答案）

8.3 结语：一棵树的自律

AVL 树的故事到这里真正完整了。第 7 篇我们认识了二叉搜索树的“自由”，第 8 篇目睹了自由如何变成退化，第 9 篇给它装上了第一套纪律——插入时绝不允许任何节点左右失衡超过一层，第 10 篇则补上了最严苛的考验：删除。删除比插入麻烦，不是因为删除本身复杂，而是因为删除之后，树必须主动检查自己的每一层，而不是等到下一次插入时才发现问题。这种“每次变更后都自觉体检”的纪律，正是平衡树与裸 BST 的分水岭。

回看本文，你会发现自己真正掌握的其实不是某个算法，而是一套可以迁移的思维：把复杂问题拆成“结构变更 + 回溯维护 + 局部修复”的流水线；用不变量（|bf| ≤ 1）驱动修复，而不是靠“感觉平衡了”；用递推而不是枚举证明高度上界；用最坏情况而不是平均值做工程决策。这套思维在红黑树、B 树、跳表、堆里会反复出现。所以下一站不是告别平衡树，而是认识它的另一个形态。

8.4 下一篇预告

AVL 树的故事讲到这里就完整了：插入、删除、复杂度、对比，一个不少。但“自平衡二叉搜索树”这个家族还有一位成员等着我们——《树系列第 11 篇：红黑树——五条性质背后的直觉》。红黑树用红黑两种颜色定义了一套比 AVL 更“宽容”的平衡规则，换来更少的旋转和更稳的工程表现。下一篇我们会从“为什么是红色和黑色”讲起，逐条拆解五条性质到底在防止什么形状，再给出完整的插入删除流程。下一篇见！