第31课 - AVL树

课程：数据结构与算法

所属模块：树结构 难度：Advanced 标签：#avl #rotation #balance #height 上一课：二叉搜索树 下一课：红黑树

1. 学习目标

完成本课学习后，你将能够：

理解为什么需要平衡二叉搜索树，并能解释AVL树的定义和平衡条件。
掌握节点平衡因子的概念及其计算方法。
熟练应用 LL、RR、LR、RL四种旋转操作，以维持树的平衡。
实现一个基本的AVL树，包含插入和保持平衡的核心逻辑。
分析 AVL树插入、删除和查找操作的时间复杂度。

2. 核心概念

在上一课中，我们知道二叉搜索树在理想情况下（平衡时）有O(log n)的操作效率。但如果插入序列是顺序的（如1，2，3，4，5），它会退化成一个链表，时间复杂度恶化为O(n)。AVL树 通过“自平衡”机制，确保在任何情况下树的高度都保持在O(log n)。

核心思想： AVL树在每个节点上维护一个平衡因子。对于任意节点N： 平衡因子 = 左子树高度 - 右子树高度 AVL树要求所有节点的平衡因子绝对值必须 <= 1。如果插入或删除操作导致某个节点的平衡因子变为2或-2，我们就认为树“失衡”了，需要通过旋转来恢复平衡。

四种失衡情况及对应旋转： 想象树像一串砝码向一侧倾斜，我们需要通过旋转来“摆正”它。

LL型（左左）：向左的左子树导致失衡 -> 右旋
RR型（右右）：向右的右子树导致失衡 -> 左旋
LR型（左右）：向左的右子树导致失衡 -> 先左旋，再右旋
RL型（右左）：向右的左子树导致失衡 -> 先右旋，再左旋

3. 代码示例

下面是一个简化但完整的AVL树插入实现。我们将实现节点插入、高度计算、四种旋转以及平衡检查。

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # 新节点是叶子，高度为1

class AVLTree:
    def get_height(self, node):
        """获取节点高度，空节点高度为0"""
        if not node:
            return 0
        return node.height

    def update_height(self, node):
        """更新节点高度：左右子树最高高度+1"""
        node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))

    def get_balance(self, node):
        """计算节点的平衡因子"""
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def right_rotate(self, y):
        """
        右旋操作 (针对LL型失衡)
        旋转前:      y
                   / \
                  x   T3
                 / \
                T1  T2
        旋转后:      x
                   / \
                  T1  y
                     / \
                    T2  T3
        """
        x = y.left
        T2 = x.right

        # 执行旋转
        x.right = y
        y.left = T2

        # 更新高度（必须先更新y，再更新x，因为y现在是x的子节点）
        self.update_height(y)
        self.update_height(x)

        # 返回新的根节点
        return x

    def left_rotate(self, x):
        """
        左旋操作 (针对RR型失衡)
        旋转前:      x
                   / \
                  T1  y
                     / \
                    T2  T3
        旋转后:      y
                   / \
                  x   T3
                 / \
                T1  T2
        """
        y = x.right
        T2 = y.left

        # 执行旋转
        y.left = x
        x.right = T2

        # 更新高度
        self.update_height(x)
        self.update_height(y)

        return y

    def insert(self, root, key):
        """递归插入节点并保持平衡"""
        # 1. 标准的BST插入
        if not root:
            return AVLNode(key)
        if key < root.key:
            root.left = self.insert(root.left, key)
        elif key > root.key:
            root.right = self.insert(root.right, key)
        else:  # 不允许重复键
            return root

        # 2. 更新该节点的高度
        self.update_height(root)

        # 3. 获取平衡因子，检查是否失衡
        balance = self.get_balance(root)

        # 4. 如果失衡，根据四种情况进行旋转

        # Case 1 - Left Left (LL)
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)

        # Case 2 - Right Right (RR)
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)

        # Case 3 - Left Right (LR)
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # Case 4 - Right Left (RL)
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        # 未失衡，返回原节点
        return root

    def pre_order(self, root):
        """前序遍历打印树（用于验证）"""
        if not root:
            return
        print(f"{root.key}(H:{root.height},BF:{self.get_balance(root)})", end=" ")
        self.pre_order(root.left)
        self.pre_order(root.right)

# 测试代码
if __name__ == "__main__":
    avl = AVLTree()
    root = None

    # 按顺序插入会触发多次旋转
    keys = [10, 20, 30, 40, 50, 25]
    print("插入序列:", keys)
    for key in keys:
        root = avl.insert(root, key)

    print("\n前序遍历AVL树:")
    avl.pre_order(root)
    print()

    # 可以用工具可视化这棵树，验证它确实是平衡的

预期输出：

插入序列: [10, 20, 30, 40, 50, 25]
前序遍历AVL树:
30(H:3,BF:0) 20(H:2,BF:0) 10(H:1,BF:0) 25(H:1,BF:0) 40(H:2,BF:-1) 50(H:1,BF:0)

4. 实践练习

练习1：实现删除操作 在上面的AVLTree类中，增加一个delete(root, key)方法。删除逻辑基于二叉搜索树的删除，但在删除后必须重新计算高度并检查平衡，必要时进行旋转。 要求： 实现该方法，并用删除前文示例中某个节点来验证。

练习2：验证树是否平衡 编写一个函数is_balanced(root)，它递归地检查树中的每个节点是否都满足AVL树的平衡条件（|平衡因子| <= 1）。 要求： 对你的插入和删除操作进行自动化测试，确保生成的树始终是平衡的。

练习3：分析与思考

对比普通二叉搜索树和AVL树，插入一个有序序列[1,2,3,...,n]，观察两者树高和查找时间的差异。
思考题：AVL树的旋转操作是为了维护严格的平衡，但有时可能过于“激进”。你能说出这种严格平衡带来的最大好处和可能的缺点吗？（提示：与下一课红黑树对比）

5. 常见错误

忘记更新高度：在旋转或插入后，必须正确更新相关节点的高度。顺序很重要（通常是先更新子节点，再更新父节点）。
旋转情况判断错误：在判断key < root.left.key或key > root.right.key时，如果写反会导致错误的旋转。理解“左左”是指失衡是由“左子树的左子树”引起的。
没有处理重复键：在上述代码中，插入重复键会静默失败。根据需求，你可能需要更新值或报错。
混淆旋转函数的输入/输出：旋转函数接收失衡节点，并返回旋转后新的根节点。必须用这个返回值更新父节点的子树引用。
递归插入后未将子树赋值回来：在self.root.left = self.insert(...)这一步，如果遗漏了赋值，旋转操作将无法正确链接。

6. 小结

AVL树是最早的自平衡二叉搜索树，由Adelson-Velsky和Landis发明。
核心约束：任意节点的左右子树高度差不超过1。
实现关键：通过维护每个节点的平衡因子，并在插入/删除后检测失衡，通过旋转（LL， RR， LR， RL）来恢复平衡。
性能保证：由于严格平衡，AVL树的查找、插入、删除操作在最坏情况下均为O(log n)。
权衡：AVL树提供了最严格的平衡，查找效率高，但插入和删除时可能需要较多的旋转操作（特别是LR/RL型需要两次旋转）。这为下一课更“宽松”但综合性能常更优的红黑树埋下了伏笔。

练习编辑器

rust

AVL 树