AVL 树删除节点后如何恢复平衡？和插入有什么不同？

简化版

先按 BST 规则删除节点（有两个孩子时用中序后继替换），再从删除点沿路径回到根，逐个更新高度、检查平衡因子并旋转。和插入最大的不同：删除可能需要一路旋转到根（最多 O(log n) 次旋转），而插入最多一次。因为删除是「降低某侧高度」，旋转后子树可能整体变矮，导致更上层继续失衡，必须继续往上调整。

详细版

删除三步：

BST 删除：找到节点，按三种情况删（叶子直接删；一个孩子用孩子替代；两个孩子用中序后继的值替换、再删后继）。
回溯更新高度：从实际被删/替换的位置往上更新每个祖先的高度。
逐层检查并旋转：每回溯到一个节点就检查 |BF|，失衡就旋转——且不能停，要一直检查到根。

TreeNode delete(TreeNode node, int val) {
    if (node == null) return null;
    if (val < node.val)      node.left  = delete(node.left,  val);
    else if (val > node.val) node.right = delete(node.right, val);
    else {
        if (node.left == null)  return node.right;   // 0/1 个孩子
        if (node.right == null) return node.left;
        TreeNode succ = node.right;                  // 中序后继
        while (succ.left != null) succ = succ.left;
        node.val = succ.val;
        node.right = delete(node.right, succ.val);
    }
    update(node);
    return rebalance(node);          // 与插入同样的 rebalance，但每层都要做
}

完整版教学

一、删除与插入的核心区别：可能连锁旋转

这是本题的考点。回顾插入：一次旋转就能把子树高度恢复到插入前，上层不再受影响，所以最多一次旋转。

删除不同：删除会让某棵子树变矮。当我们旋转失衡节点后，旋转可能让这棵子树整体高度再减 1，于是它的父节点又可能失衡……这种「变矮」会像多米诺一样向上传导。所以删除必须从删除点一路检查、旋转到根，最坏需要 O(log n) 次旋转（每一层都可能旋转一次）。

一句话对比：插入的旋转是「补高」，一次就够；删除的旋转是「削高」，可能连锁到根。

二、删除时的旋转类型判断

删除后某节点失衡（|BF|=2），旋转类型的判断和插入略有差别——要看较高的那一侧孩子的平衡因子：

失衡节点左偏（BF=+2）：
- 左孩子 BF ≥ 0 → LL（右旋）
- 左孩子 BF < 0 → LR（左孩子左旋 + 右旋）
失衡节点右偏（BF=-2）：
- 右孩子 BF ≤ 0 → RR（左旋）
- 右孩子 BF > 0 → RL（右孩子右旋 + 左旋）

注意删除时较高孩子的 BF 可能为 0（插入时不会出现这种情况）——此时按单旋处理即可。逻辑和插入的 rebalance 基本一致，可复用同一份代码。

三、为什么用中序后继替换

删除有两个孩子的节点时，直接删会留下无法填补的洞。用中序后继（右子树最小节点） 的值替换当前节点，再去右子树删掉那个后继——后继必然至多一个孩子，删它简单。这一步和普通 BST 删除完全相同，AVL 只是在删完后多了「回溯 + 旋转」。

四、走一个例子理解连锁

在一棵较满的 AVL 树里删掉一个叶子，可能让它的父节点失衡；旋转父节点后，这棵子树高度又降了 1，导致祖父失衡，再旋转……直到根。虽然「一路旋转到根」是最坏情况、实际中不常发生，但AVL 删除不能像插入那样旋转一次就 return，必须逐层检查上去。

五、复杂度

时间 O(log n)：删除下降 O(log n) + 回溯 O(log n)，每次旋转 O(1)。
旋转次数：最坏 O(log n)（对比插入的 O(1)）。
空间 O(log n)：递归栈。

正是因为删除的旋转成本更高，加上 AVL 严格平衡整体维护开销大，很多通用场景改用旋转更少的红黑树。

六、常见误区与追问

考点	正确口径
删除后风险	高度可能继续向祖先传播变化
调整方式	沿回溯路径更新高度并旋转
和插入差异	删除可能触发多次旋转

delete node
while backtracking:
  update height
  if |balance| > 1: rotate
  continue upward

AVL 删除比插入麻烦，是因为某一层恢复平衡后，子树高度仍可能下降。

误区：AVL 删除最多旋转一次。 插入通常一次旋转即可停止，删除后高度下降可能继续影响祖先。
误区：删除两个孩子节点时可以随便替换。 仍要先按 BST 删除规则使用中序后继或前驱替换，再处理 AVL 平衡。
误区：旋转后不用更新高度。 旋转改变了父子关系，相关节点高度必须按自底向上的顺序重新计算。
追问：删除后如何判断 LL、RR、LR、RL？ 看失衡节点的 balance factor 和较高子节点的 balance factor，选择单旋或双旋。
追问：为什么删除可能连锁？ 被删除路径上的某棵子树高度减少，祖先的高度和平衡因子都可能继续变化。
追问：复杂度是多少？ 查找、删除和回溯调整都沿树高进行，AVL 高度 O(log n)，所以总复杂度 O(log n)。

七、加强记忆

AVL 删除：BST 删除（两孩子用中序后继替换）→ 自底向上更新高度 → 逐层检查 |BF| 并旋转，一直到根。与插入最大的不同：插入最多 1 次旋转（补高，一次复原），删除最坏 O(log n) 次旋转（削高，会连锁向上）。删除时较高孩子 BF 可能为 0，按单旋处理。整体仍 O(log n)。删除成本高是工程偏爱红黑树的原因之一。

简化版

详细版