AVL树的删除操作

AVL树是一种自平衡二叉搜索树，在删除节点后需要通过旋转操作来维持平衡因子（左右子树高度差不超过1）。删除操作比插入更复杂，因为平衡可能被破坏并向上传播到根节点。

1. 基本删除步骤
首先执行标准BST删除：

• 情况1：删除叶子节点→直接删除
• 情况2：删除只有一个子节点的节点→用子节点替代
• 情况3：删除有两个子节点的节点→用前驱/后继节点值替换，然后递归删除前驱/后继

2. 平衡修复的四种情况
设被删除节点为N，从N向根回溯时遇到的第一个不平衡节点为A（平衡因子为±2）。根据A的子树结构分为：

• 左左情况（LL）：A的左子树高度更高，且左子树的左子树高度更高/相等
• 左右情况（LR）：A的左子树高度更高，但左子树的右子树高度更高
• 右右情况（RR）：A的右子树高度更高，且右子树的右子树高度更高/相等
• 右左情况（RL）：A的右子树高度更高，但右子树的左子树高度更高

3. 旋转操作详解

• LL情况：对A执行右旋转

     A(平衡因子=+2)      B(新根)
      / \             / \
     B   AR    →     BL   A
    / \                 / \
   BL  BR              BR  AR
  

• RR情况：对A执行左旋转（与LL对称）
• LR情况：先对A的左子树左旋转转换为LL，再对A右旋转
• RL情况：先对A的右子树右旋转转换为RR，再对A左旋转

4. 平衡因子更新规则
旋转后需重新计算A及其子节点的高度和平衡因子。特别注意：在LR/RL情况中，旋转后新根的平衡因子需根据原子树高度调整：

• 若原BR高度等于CR高度，旋转后A和B平衡因子均为0
• 若原BR高度大于CR高度，旋转后A平衡因子为0，B为-1
• 若原BR高度小于CR高度，旋转后A平衡因子为+1，B为0

5. 向上传播特性
删除后平衡修复可能需从删除点向上回溯到根节点，每次旋转后需继续检查父节点是否失衡。与插入不同（最多一次旋转），删除可能需O(log n)次旋转。

6. 实例演示
删除AVL树中节点5（初始树）：

      8
     / \
    5   10
   / \   \
  3   7   11
 / \
2   4

步骤：

1. 用前驱节点4替换5，变成删除叶子节点4
2. 从原5位置向上检查：节点3平衡因子=+1（右子树高度高）→无需旋转
3. 继续向上：节点8左子树高度=2，右子树高度=2→平衡
   最终树保持平衡，无需旋转。

关键点：删除后必须沿路径更新高度并检查平衡，旋转后需重新计算相关节点高度。平衡因子的精细调整是保证O(log n)时间复杂度的关键。