平衡二叉树（AVL树）的旋转操作与平衡因子维护
字数 1364 2025-11-21 18:32:48

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

1. 问题背景

平衡二叉树（AVL树）是一种自平衡二叉搜索树，通过维护每个节点的平衡因子（左子树高度减右子树高度）来保证树的高度始终为 \(O(\log n)\)，从而确保插入、删除和查找操作的时间复杂度为 \(O(\log n)\)。当平衡因子超出允许范围（-1, 0, 1）时，需要通过旋转操作调整树结构。

2. 核心概念：平衡因子

  • 定义：对于任意节点，平衡因子 = 左子树高度 - 右子树高度。
  • 合法范围：-1、0、1。若平衡因子为2或-2，则需调整。
  • 高度更新：插入或删除节点后，需从操作位置向上更新祖先节点的高度，并重新计算平衡因子。

3. 旋转操作的四种类型

根据失衡节点的平衡因子和子节点的平衡因子，分为以下四种情况：

3.1 左旋（Left Rotation）

  • 适用场景：失衡节点的平衡因子为-2，且右子节点的平衡因子为-1或0（右右情况）。
  • 操作步骤：
    1. 以失衡节点A的右孩子B为新的根节点。
    2. 将B的左子树作为A的右子树。
    3. 将A作为B的左子树。
  • 示例（右右情况）： 
       A (平衡因子=-2)  
    \  
     B (平衡因子=-1)  
      \  
       C
    左旋后： 
          B  
     / \  
    A   C

3.2 右旋（Right Rotation）

  • 适用场景：失衡节点的平衡因子为2，且左子节点的平衡因子为1或0（左左情况）。
  • 操作步骤：
    1. 以失衡节点A的左孩子B为新的根节点。
    2. 将B的右子树作为A的左子树。
    3. 将A作为B的右子树。
  • 示例（左左情况）： 
           A (平衡因子=2)  
      /  
     B (平衡因子=1)  
    /  
   C
    右旋后： 
          B  
     / \  
    C   A

3.3 左右旋（Left-Right Rotation）

  • 适用场景：失衡节点A的平衡因子为2，且左孩子B的平衡因子为-1（左右情况）。
  • 操作步骤：
    1. 先对B执行左旋（将B的右孩子C提升为B的父节点）。
    2. 再对A执行右旋（将C提升为新的根节点）。
  • 示例： 
         A (平衡因子=2)  
    /  
   B (平衡因子=-1)  
    \  
     C
    先左旋B： 
         A  
    /  
   C  
  /  
 B
    再右旋A： 
          C  
     / \  
    B   A

3.4 右左旋（Right-Left Rotation）

  • 适用场景：失衡节点A的平衡因子为-2，且右孩子B的平衡因子为1（右左情况）。
  • 操作步骤：
    1. 先对B执行右旋（将B的左孩子C提升为B的父节点）。
    2. 再对A执行左旋（将C提升为新的根节点）。
  • 示例： 
       A (平衡因子=-2)  
    \  
     B (平衡因子=1)  
    /  
   C
    先右旋B： 
       A  
    \  
     C  
      \  
       B
    再左旋A： 
          C  
     / \  
    A   B

4. 插入操作中的平衡维护流程

  1. 标准BST插入：按二叉搜索树规则插入新节点。
  2. 向上更新高度：从新节点开始向上遍历祖先节点，更新每个节点的高度。
  3. 检查平衡因子：若某个节点的平衡因子变为2或-2，根据子节点平衡因子选择旋转类型：
    • 左左 → 右旋
    • 右右 → 左旋
    • 左右 → 左右旋
    • 右左 → 右左旋
  4. 调整后更新高度：旋转后重新计算相关节点的高度。

5. 实例演示

插入序列：[10, 5, 15, 3, 7, 12, 20, 1]

  1. 插入10、5、15：树平衡。
  2. 插入3： 
         10  
    /  \  
   5    15  
  /  
 3
    节点10的平衡因子=1，节点5的平衡因子=1，仍平衡。
  3. 插入7： 
         10  
    /  \  
   5    15  
  / \  
 3   7
    节点10的平衡因子=2（左子树高2，右子树高0），且节点5的平衡因子=0（左右情况），需左右旋：
    • 先左旋节点5： 
           10  
    /  \  
   7    15  
  /  
 5  
/
    3 
    - 再右旋节点10：  

       7  
  / \  
 5   10  
/     \
    3 15 
    最终树恢复平衡。

6. 总结

  • AVL树的旋转操作是维护平衡的核心，分为左旋、右旋及其组合。
  • 每次插入或删除后，需从操作点向上检查平衡因子，最多需要 \(O(\log n)\) 次调整。
  • 旋转操作的时间复杂度为 \(O(1)\)，整体插入/删除操作保持 \(O(\log n)\)。
平衡二叉树（AVL树）的旋转操作与平衡因子维护 1. 问题背景 平衡二叉树（AVL树）是一种自平衡二叉搜索树，通过维护每个节点的 平衡因子 （左子树高度减右子树高度）来保证树的高度始终为 \(O(\log n)\)，从而确保插入、删除和查找操作的时间复杂度为 \(O(\log n)\)。当平衡因子超出允许范围（-1, 0, 1）时，需要通过 旋转操作 调整树结构。 2. 核心概念：平衡因子 定义 ：对于任意节点，平衡因子 = 左子树高度 - 右子树高度。 合法范围 ：-1、0、1。若平衡因子为2或-2，则需调整。 高度更新 ：插入或删除节点后，需从操作位置向上更新祖先节点的高度，并重新计算平衡因子。 3. 旋转操作的四种类型 根据失衡节点的平衡因子和子节点的平衡因子，分为以下四种情况： 3.1 左旋（Left Rotation） 适用场景 ：失衡节点的平衡因子为-2，且右子节点的平衡因子为-1或0（右右情况）。 操作步骤 ： 以失衡节点A的右孩子B为新的根节点。 将B的左子树作为A的右子树。 将A作为B的左子树。 示例 （右右情况）： 左旋后： 3.2 右旋（Right Rotation） 适用场景 ：失衡节点的平衡因子为2，且左子节点的平衡因子为1或0（左左情况）。 操作步骤 ： 以失衡节点A的左孩子B为新的根节点。 将B的右子树作为A的左子树。 将A作为B的右子树。 示例 （左左情况）： 右旋后： 3.3 左右旋（Left-Right Rotation） 适用场景 ：失衡节点A的平衡因子为2，且左孩子B的平衡因子为-1（左右情况）。 操作步骤 ： 先对B执行左旋（将B的右孩子C提升为B的父节点）。 再对A执行右旋（将C提升为新的根节点）。 示例 ： 先左旋B： 再右旋A： 3.4 右左旋（Right-Left Rotation） 适用场景 ：失衡节点A的平衡因子为-2，且右孩子B的平衡因子为1（右左情况）。 操作步骤 ： 先对B执行右旋（将B的左孩子C提升为B的父节点）。 再对A执行左旋（将C提升为新的根节点）。 示例 ： 先右旋B： 再左旋A： 4. 插入操作中的平衡维护流程 标准BST插入 ：按二叉搜索树规则插入新节点。 向上更新高度 ：从新节点开始向上遍历祖先节点，更新每个节点的高度。 检查平衡因子 ：若某个节点的平衡因子变为2或-2，根据子节点平衡因子选择旋转类型： 左左 → 右旋 右右 → 左旋 左右 → 左右旋 右左 → 右左旋 调整后更新高度 ：旋转后重新计算相关节点的高度。 5. 实例演示 插入序列： [10, 5, 15, 3, 7, 12, 20, 1] 插入10、5、15：树平衡。 插入3： 节点10的平衡因子=1，节点5的平衡因子=1，仍平衡。 插入7： 节点10的平衡因子=2（左子树高2，右子树高0），且节点5的平衡因子=0（左右情况），需左右旋： 先左旋节点5： 3 3 15 6. 总结 AVL树的旋转操作是维护平衡的核心，分为左旋、右旋及其组合。 每次插入或删除后，需从操作点向上检查平衡因子，最多需要 \(O(\log n)\) 次调整。 旋转操作的时间复杂度为 \(O(1)\)，整体插入/删除操作保持 \(O(\log n)\)。