AVL树的调整

在AVL树中，调整是为了保持树的平衡性，主要涉及以下四种不平衡情况，每种情况对应特定的旋转操作来恢复平衡。具体情况如下：

1. LL情况（左左不平衡）

• 特征：在插入时，某个节点的左子树的左子节点导致不平衡。

• 结构：

      A
     /
    B
   /
  C

• 调整：执行右旋转。

• 操作：

  • 将 B 提升为新的根节点，A 变为 B 的右子节点。

2. RR情况（右右不平衡）

• 特征：在插入时，某个节点的右子树的右子节点导致不平衡。

• 结构：

      A
       \
        B
         \
          C

• 调整：执行左旋转。

• 操作：

  • 将 B 提升为新的根节点，A 变为 B 的左子节点。

3. LR情况（左右不平衡）

• 特征：在插入时，某个节点的左子树的右子节点导致不平衡。

• 结构：

      A
     /
    B
     \
      C

• 调整：先对 B 左旋，然后对 A 右旋。

• 操作：

  • 先将 C 提升为 B 的父节点，再将 C 提升为新的根节点。

4. RL情况（右左不平衡）

• 特征：在插入时，某个节点的右子树的左子节点导致不平衡。

• 结构：

      A
       \
        B
       /
      C

• 调整：先对 B 右旋，然后对 A 左旋。

• 操作：

  • 先将 C 提升为 B 的父节点，再将 C 提升为新的根节点。

处理步骤总结

• 插入或删除节点后：每次插入或删除操作后，都需要从当前节点开始向上更新高度，并检查每个节点的平衡因子。

• 选择适当的旋转：根据平衡因子的值判断采取的旋转操作：

  • LL：右旋

  • RR：左旋

  • LR：先左旋后右旋

  • RL：先右旋后左旋

示例

以插入节点 30, 10, 20 为例，展示LR情况的调整：

1. 插入 30：

       30

2. 插入 10：

       30
      /
     10

3. 插入 20（造成LR不平衡）：

       30
      /
     10
       \
       20

4. 调整步骤：

   • 对 10 左旋：

       30
      /
     20
    /
   10

   • 对 30 右旋：

       20
      /  \
     10   30

总结

AVL树的调整机制确保在每次插入或删除操作后，树的平衡性能够得到维护。通过合理的旋转操作，AVL树能够始终保持对数时间复杂度的高效性能。