AVL树（自平衡二叉搜索树）原理与实现

AVL树是一种自平衡二叉搜索树，通过旋转操作维护树的平衡，确保左右子树高度差不超过1，从而保证查询、插入和删除操作的时间复杂度为O(log n)。下面逐步讲解其核心原理和操作。

1. 平衡因子的定义

AVL树中每个节点的平衡因子定义为：

平衡因子 = 左子树高度 - 右子树高度  

平衡因子只能为 -1、0 或 1。若某个节点的平衡因子绝对值大于1，则需要进行平衡调整。

2. 失衡的四种情况

当插入或删除节点导致平衡因子超出范围时，会出现以下四种失衡情况（假设节点A为失衡点）：

1. 左左情况（LL）

   • 失衡原因：在A的左子树（L）的左子树（L）插入节点，A的平衡因子变为2。
   • 修复操作：右旋（以A为轴顺时针旋转）。

2. 右右情况（RR）

   • 失衡原因：在A的右子树（R）的右子树（R）插入节点，A的平衡因子变为-2。
   • 修复操作：左旋（以A为轴逆时针旋转）。

3. 左右情况（LR）

   • 失衡原因：在A的左子树（L）的右子树（R）插入节点。
   • 修复操作：先对A的左子树左旋（转为LL情况），再对A右旋。

4. 右左情况（RL）

   • 失衡原因：在A的右子树（R）的左子树（L）插入节点。
   • 修复操作：先对A的右子树右旋（转为RR情况），再对A左旋。

3. 旋转操作详解

（1）右旋（LL情况）

示例：节点A平衡因子为2，且其左子树B的平衡因子为0或1（左子树更高）。

     A（失衡点）
    / \
   B   T3
  / \
 T1  T2

右旋步骤：

1. 将B的右子树T2作为A的左子树。
2. 将A作为B的右子树。
   结果：

       B
      / \
     T1  A
        / \
       T2  T3

（2）左旋（RR情况）

示例：节点A平衡因子为-2，且其右子树B的平衡因子为0或-1（右子树更高）。

   A
  / \
 T1  B
    / \
   T2 T3

左旋步骤：

1. 将B的左子树T2作为A的右子树。
2. 将A作为B的左子树。
   结果：

     B
    / \
   A  T3
  / \
 T1 T2

（3）LR情况：先左旋后右旋

示例：在A的左子树B的右子树C插入节点。

     A
    / \
   B   T4
  / \
 T1  C
    / \
   T2 T3

步骤：

1. 对B进行左旋（将C提升为B的父节点）：

     A
    / \
   C   T4
  / \
  B  T3
 / \
T1 T2

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

       C
      / \
     B   A
    / \   \
   T1 T2   T4
         \
         T3

（4）RL情况：先右旋后左旋

类比LR情况，方向相反。

4. 插入操作的完整流程

1. 按二叉搜索树规则插入节点。
2. 从插入点向上回溯，更新每个祖先节点的高度。
3. 检查每个节点的平衡因子：
   • 若平衡因子为2或-2，根据上述四种情况旋转。
   • 若平衡因子正常，继续回溯至根节点。

5. 删除操作的平衡维护

删除节点后，同样从删除点向上回溯，若发现失衡则进行旋转调整。与插入不同的是，删除可能需多次旋转（失衡可能向上传播）。

6. 时间复杂度分析

• 查询：O(log n)（树高度平衡）。
• 插入/删除：O(log n)（旋转操作耗时O(1)）。

7. 代码实现关键步骤（伪代码）

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1  # 节点高度

def get_height(node):
    return node.height if node else 0

def update_height(node):
    node.height = 1 + max(get_height(node.left), get_height(node.right))

def get_balance(node):
    return get_height(node.left) - get_height(node.right) if node else 0

def left_rotate(z):
    y = z.right
    T2 = y.left
    y.left = z
    z.right = T2
    update_height(z)
    update_height(y)
    return y  # 返回新的根节点

def right_rotate(z):
    y = z.left
    T3 = y.right
    y.right = z
    z.left = T3
    update_height(z)
    update_height(y)
    return y

def insert(root, val):
    # 1. 标准BST插入
    if not root:
        return AVLNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    
    # 2. 更新高度并检查平衡
    update_height(root)
    balance = get_balance(root)
    
    # 3. 处理失衡
    if balance > 1 and val < root.left.val:  # LL
        return right_rotate(root)
    if balance < -1 and val > root.right.val:  # RR
        return left_rotate(root)
    if balance > 1 and val > root.left.val:  # LR
        root.left = left_rotate(root.left)
        return right_rotate(root)
    if balance < -1 and val < root.right.val:  # RL
        root.right = right_rotate(root.right)
        return left_rotate(root)
    return root  # 平衡则直接返回

8. 对比红黑树

• AVL树：严格平衡，查询效率更高，适合读多写少的场景（如数据库索引）。
• 红黑树：近似平衡，插入/删除效率更高，适合频繁修改的场景（如语言标准库的Map）。

通过以上步骤，你可以理解AVL树如何通过旋转保持平衡，并实现高效动态维护的二叉搜索树。