AVL树的插入操作

AVL树是一种自平衡二叉搜索树，通过维护每个节点的平衡因子（左子树高度减右子树高度）来确保树的高度始终为O(log n)。插入操作需在标准BST插入基础上增加平衡调整步骤。

1. 平衡因子的定义与规则

• 平衡因子（Balance Factor, BF） = 左子树高度 - 右子树高度。
• 合法值：-1、0、1。若某个节点的BF绝对值大于1，则需通过旋转重新平衡。

2. 插入操作的基本步骤

步骤1：标准BST插入
递归地找到新节点的正确位置并插入，新节点初始为叶子节点（BF=0）。

步骤2：更新祖先节点的平衡因子
从新节点的父节点开始向上回溯，更新每个祖先节点的BF：

• 若新节点插入在祖先节点的左子树，则祖先节点的BF加1；
• 若插入在右子树，则BF减1。

步骤3：检查平衡性并旋转
在回溯过程中，若遇到某个节点的BF变为2或-2（即失衡），需根据其子节点的BF情况进行旋转调整：

• 左左情况（LL）：父节点BF=2，左子节点BF≥0 → 右旋（Right Rotation）。
• 右右情况（RR）：父节点BF=-2，右子节点BF≤0 → 左旋（Left Rotation）。
• 左右情况（LR）：父节点BF=2，左子节点BF=-1 → 先对左子节点左旋（转为LL），再对父节点右旋。
• 右左情况（RL）：父节点BF=-2，右子节点BF=1 → 先对右子节点右旋（转为RR），再对父节点左旋。

步骤4：旋转后调整平衡因子
旋转后需更新相关节点的BF，确保平衡性恢复。

3. 实例演示插入过程

假设依次插入节点：10, 20, 30, 40, 50。

插入10：
树结构：10（BF=0）。

插入20（插入到10的右子树）：

• 更新10的BF：0 → -1。
• 树结构：10(BF=-1) → 右子节点20(BF=0)。

插入30（插入到20的右子树）：

1. 更新20的BF：0 → -1。
2. 更新10的BF：-1 → -2（失衡，RR情况）。
3. 对10左旋：
   • 20成为新根，10为20的左子节点。
   • 更新BF：10(BF=0), 20(BF=0), 30(BF=0)。

插入40（插入到30的右子树）：

1. 更新30的BF：0 → -1。
2. 更新20的BF：0 → -1。

插入50（插入到40的右子树）：

1. 更新40的BF：0 → -1。
2. 更新30的BF：-1 → -2（失衡，RR情况）。
3. 对30左旋：
   • 40成为30的父节点，30成为40的左子节点。
   • 更新BF：30(BF=0), 40(BF=0), 20(BF=-2)（仍需处理）。
4. 回溯到20：BF=-2（失衡，RR情况），左旋：
   • 40成为新根，20为40的左子节点，30为20的右子节点。
   • 更新BF：20(BF=0), 30(BF=0), 40(BF=0)。

最终树结构：

    40  
   /  \  
  20  50  
 /  \  
10  30  

所有节点BF∈{-1,0,1}。

4. 旋转操作的平衡因子更新规则

• 右旋（LL情况）：
  设失衡节点为A，左子节点为B。旋转后：

  • 若B的原始BF=0：A(BF=0), B(BF=0)。
  • 若B的原始BF=1：A(BF=-1), B(BF=0)。

• 左旋（RR情况）：
  设失衡节点为A，右子节点为B。旋转后：

  • 若B的原始BF=0：A(BF=0), B(BF=0)。
  • 若B的原始BF=-1：A(BF=1), B(BF=0)。

• LR情况：先左旋再右旋，BF更新需根据B（A的左子节点）和C（B的右子节点）的原始BF分情况处理（详见标准AVL算法描述）。

5. 时间复杂度分析

• 插入操作：O(log n)（查找位置O(log n) + 回溯调整O(log n)）。
• 旋转操作：O(1)（仅涉及常数次指针修改）。

通过以上步骤，AVL树在插入后始终保持平衡，确保高效查询。