手写AVL树（平衡二叉搜索树）的旋转操作与平衡因子维护

题目/知识点描述
AVL树是一种自平衡二叉搜索树，其特点是任意节点的左右子树高度差（平衡因子）的绝对值不超过1。当插入或删除节点导致平衡因子超出范围时，需要通过旋转操作重新平衡。本题要求深入理解AVL树的四种旋转操作（左旋、右旋、左右旋、右左旋）的原理，并能够手动实现旋转与平衡因子的更新逻辑。

解题过程循序渐进讲解
AVL树的平衡维护是其核心，我们将分步骤拆解。

步骤1：理解AVL树的基本定义与平衡因子

1. AVL树首先是一棵二叉搜索树（BST），即对于任意节点，左子树所有节点的值 < 节点值 < 右子树所有节点的值。
2. 每个节点需要记录一个额外属性：平衡因子（Balance Factor, BF）。
   • 平衡因子 = 左子树高度 - 右子树高度。
   • 在AVL树中，每个节点的BF必须为 -1、0 或 1。
3. 如果插入或删除导致某个节点的BF变为 -2 或 2，则该节点为“失衡节点”，需要通过旋转恢复平衡。

步骤2：明确四种失衡情况与对应的旋转操作
失衡情况分为四种，设失衡节点为A：

1. 左左情况（LL）：A的BF = 2，且A的左孩子的BF >= 0。
   • 处理：对A执行一次右旋（Right Rotation）。
2. 右右情况（RR）：A的BF = -2，且A的右孩子的BF <= 0。
   • 处理：对A执行一次左旋（Left Rotation）。
3. 左右情况（LR）：A的BF = 2，且A的左孩子的BF = -1。
   • 处理：先对A的左孩子执行一次左旋，再对A执行一次右旋。
4. 右左情况（RL）：A的BF = -2，且A的右孩子的BF = 1。
   • 处理：先对A的右孩子执行一次右旋，再对A执行一次左旋。

步骤3：详细讲解每种旋转的操作步骤与平衡因子更新
我们定义节点结构，包含值（val）、左孩子（left）、右孩子（right）、高度（height，用于计算BF）。
平衡因子计算：BF(node) = height(node.left) - height(node.right)。

3.1 右旋（针对LL情况）
示例：节点A失衡，其左孩子为B，B的右子树为T2。
旋转前：

        A (BF=2)
       / \
      B   C
     / \
    D   T2
   / \
 ... ...

旋转步骤：

1. 让B的右孩子T2成为A的左孩子。
2. 让A成为B的右孩子。
3. 更新A和B的高度（重新计算）。
   旋转后：

        B
       / \
      D   A
         / \
        T2  C

关键点：旋转后，B成为新的根，A成为B的右孩子，原来B的右孩子T2挂到A的左子树。

3.2 左旋（针对RR情况）
示例：节点A失衡，其右孩子为B，B的左子树为T2。
旋转步骤：

1. 让B的左孩子T2成为A的右孩子。
2. 让A成为B的左孩子。
3. 更新A和B的高度。
   旋转后结构对称于右旋。

3.3 左右旋（针对LR情况）
示例：A失衡（BF=2），其左孩子B的BF = -1。
处理分两步：

1. 对B执行一次左旋（将B视为RR情况），转化为LL情况。
2. 对A执行一次右旋。
   旋转后平衡恢复。

3.4 右左旋（针对RL情况）
对称于左右旋：

1. 对A的右孩子执行右旋（转化为RR情况）。
2. 对A执行左旋。

步骤4：实现旋转时的平衡因子更新
旋转后必须重新计算受影响节点的高度。
高度更新方法：

height(node) = 1 + max(height(node.left), height(node.right))

然后重新计算BF = height(left) - height(right)。

步骤5：插入节点后的平衡维护流程

1. 按照BST规则插入新节点。
2. 从插入点向上回溯到根，更新沿途每个节点的高度。
3. 遇到第一个失衡节点（BF为2或-2），根据其BF和孩子的BF判断属于哪种失衡情况，执行对应旋转。
4. 旋转后，子树高度可能减少，需继续向上更新高度，但通常一次旋转即可恢复整棵树的平衡。

步骤6：示例演示插入过程
假设依次插入序列 [3, 2, 1] 到空AVL树：

• 插入3：树为 3 (BF=0)。
• 插入2：3的左孩子为2，3的BF=1，2的BF=0。
• 插入1：插入到2的左孩子，此时：
  • 节点3的BF = 高度(左子树)=2，高度(右子树)=0 → BF=2（失衡，LL情况）。
  • 对3执行右旋：2成为新根，3成为2的右孩子。
    旋转后树平衡。

总结
AVL树的旋转操作是维护平衡的关键，需要：

1. 在插入/删除后更新节点高度并计算BF。
2. 识别失衡节点的四种情况。
3. 熟练掌握四种旋转的指针调整与高度更新。
4. 注意旋转后原失衡节点的BF及其孩子BF的变化，但通常无需记忆，掌握高度重新计算即可。

通过这四类旋转，AVL树能在每次操作后保持平衡，从而保证O(log n)的查找、插入、删除复杂度。