AVL树的旋转操作

描述
AVL树是一种自平衡二叉搜索树，通过维护每个节点的平衡因子（左子树高度减右子树高度）在-1、0、1之间来保证操作效率。当插入或删除节点导致平衡因子超出范围时，需要通过旋转操作恢复平衡。旋转分为四种基本类型：左旋、右旋、左右旋（先左后右）和右左旋（先右后左）。

解题过程

1. 平衡因子检查

   • 从新节点（或删除位置）向上回溯到根节点，检查每个祖先节点的平衡因子。
   • 平衡因子计算公式：balance = height(left_subtree) - height(right_subtree)。
   • 若某个节点的平衡因子变为2或-2，则以此节点为根的子树需要旋转平衡。

2. 旋转类型判断
   设失衡节点为A（平衡因子为2或-2）：

   • 左左情况（LL）：A的平衡因子为2，且A的左子节点平衡因子≥0。
     • 解决方案：对A执行右旋。
   • 右右情况（RR）：A的平衡因子为-2，且A的右子节点平衡因子≤0。
     • 解决方案：对A执行左旋。
   • 左右情况（LR）：A的平衡因子为2，但A的左子节点平衡因子为-1。
     • 解决方案：先对A的左子节点执行左旋，转化为LL情况后，再对A执行右旋。
   • 右左情况（RL）：A的平衡因子为-2，但A的右子节点平衡因子为1。
     • 解决方案：先对A的右子节点执行右旋，转化为RR情况后，再对A执行左旋。

3. 旋转操作详解

   • 右旋（以节点A为例）：

     1. 将A的左子节点B提升为新的根节点。
     2. 将B的右子树挂载为A的左子树。
     3. 将A挂载为B的右子节点。
     • 示例：

        初始：    A(失衡)     右旋后：    B
                /           →         / \
              B                      C   A
             / \
            C   D
       

   • 左旋（对称操作）：

     1. 将A的右子节点B提升为新的根节点。
     2. 将B的左子树挂载为A的右子树。
     3. 将A挂载为B的左子节点。

   • 左右旋（LR）分步示例：

     1. 初始状态：

            A(平衡因子=2)
           /
          B(平衡因子=-1)
           \
            C
        

     2. 对B执行左旋（将C提升为A的左子节点）：

            A
           /
          C
         /
        B
        

     3. 对A执行右旋（将C提升为根节点）：

            C
           / \
          B   A
        

4. 更新高度与回溯

   • 旋转后需重新计算A及其子节点的高度（深度优先更新）。
   • 继续向上回溯检查祖先节点，直到根节点，确保整棵树平衡。

关键点

• 旋转后二叉搜索树的有序性保持不变。
• 插入时最多需要两次旋转（如LR/RL），删除时可能需回溯到根节点多次旋转。
• 时间复杂度：单次旋转O(1)，整体维护平衡的代价为O(log n)。