手写AVL树（平衡二叉搜索树）的实现

题目描述
实现一个自平衡的二叉搜索树（AVL树），要求支持插入、删除和查找操作。AVL树通过维护每个节点的平衡因子（左子树高度减右子树高度）在-1到1之间来保持平衡，当插入或删除操作导致树不平衡时，通过旋转操作重新平衡。

基本概念

1. 平衡因子：左子树高度 - 右子树高度
2. 四种不平衡情况：
   • 左左情况（LL）：左子树的左子树导致不平衡
   • 左右情况（LR）：左子树的右子树导致不平衡
   • 右右情况（RR）：右子树的右子树导致不平衡
   • 右左情况（RL）：右子树的左子树导致不平衡

实现步骤

1. 节点结构定义

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.height = 1  # 节点高度，初始为1
        self.left = None
        self.right = None
        self.parent = None  # 可选，用于简化操作

2. 辅助方法

def get_height(node):
    """获取节点高度，处理空节点情况"""
    if not node:
        return 0
    return node.height

def get_balance_factor(node):
    """计算平衡因子"""
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

def update_height(node):
    """更新节点高度"""
    if node:
        node.height = 1 + max(get_height(node.left), get_height(node.right))

3. 旋转操作（核心）

左旋（针对RR情况）

def left_rotate(z):
    """
    z: 不平衡节点
    y: z的右子节点
    T2: y的左子树
    """
    y = z.right
    T2 = y.left
    
    # 执行旋转
    y.left = z
    z.right = T2
    
    # 更新高度（先更新z，再更新y）
    update_height(z)
    update_height(y)
    
    return y  # 返回新的根节点

右旋（针对LL情况）

def right_rotate(z):
    """
    z: 不平衡节点  
    y: z的左子节点
    T3: y的右子树
    """
    y = z.left
    T3 = y.right
    
    # 执行旋转
    y.right = z
    z.left = T3
    
    # 更新高度
    update_height(z)
    update_height(y)
    
    return y

4. 重新平衡

def rebalance(node, key):
    """根据不平衡类型选择旋转方式"""
    balance = get_balance_factor(node)
    
    # LL情况：右旋
    if balance > 1 and key < node.left.key:
        return right_rotate(node)
    
    # RR情况：左旋  
    if balance < -1 and key > node.right.key:
        return left_rotate(node)
    
    # LR情况：先左旋再右旋
    if balance > 1 and key > node.left.key:
        node.left = left_rotate(node.left)
        return right_rotate(node)
    
    # RL情况：先右旋再左旋
    if balance < -1 and key < node.right.key:
        node.right = right_rotate(node.right)
        return left_rotate(node)
    
    return node  # 无需调整

5. 插入操作

def insert(root, key):
    # 1. 标准BST插入
    if not root:
        return AVLNode(key)
    
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    else:
        return root  # 不允许重复键
    
    # 2. 更新当前节点高度
    update_height(root)
    
    # 3. 检查平衡并重新平衡
    return rebalance(root, key)

6. 删除操作

def delete(root, key):
    # 1. 标准BST删除
    if not root:
        return root
    
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        # 找到要删除的节点
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        else:
            # 有两个子节点：用后继节点替换
            temp = get_min_value_node(root.right)
            root.key = temp.key
            root.right = delete(root.right, temp.key)
    
    # 2. 更新高度
    update_height(root)
    
    # 3. 重新平衡（需要根据子树情况判断不平衡类型）
    balance = get_balance_factor(root)
    
    # LL情况
    if balance > 1 and get_balance_factor(root.left) >= 0:
        return right_rotate(root)
    
    # LR情况  
    if balance > 1 and get_balance_factor(root.left) < 0:
        root.left = left_rotate(root.left)
        return right_rotate(root)
    
    # RR情况
    if balance < -1 and get_balance_factor(root.right) <= 0:
        return left_rotate(root)
    
    # RL情况
    if balance < -1 and get_balance_factor(root.right) > 0:
        root.right = right_rotate(root.right)
        return left_rotate(root)
    
    return root

def get_min_value_node(node):
    """获取最小节点"""
    while node.left:
        node = node.left
    return node

7. 查找操作

def search(root, key):
    """标准BST查找，时间复杂度O(log n)"""
    if not root or root.key == key:
        return root
    
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

复杂度分析

• 插入：O(log n) - 需要从插入点回溯到根节点检查平衡
• 删除：O(log n) - 类似插入，可能需要多次旋转
• 查找：O(log n) - 与普通BST相同，但保证了平衡性
• 空间：O(n) - 存储n个节点

实际应用场景

• 数据库索引（需要频繁插入删除的有序数据）
• 内存中的有序数据结构
• 实时系统（保证最坏情况下的性能）
• 字典实现（比红黑树更严格的平衡）

AVL树通过牺牲部分插入删除性能（需要更多旋转操作）来保证更严格的平衡，适合查找密集型的应用场景。