AVL树[编辑 | 编辑源代码]

AVL树（Adelson-Velsky and Landis Tree）是一种自平衡的二叉搜索树（BST），由苏联数学家G. M. Adelson-Velsky和E. M. Landis于1962年提出。它在二叉搜索树的基础上增加了平衡条件，确保树的高度始终保持在 $O (\log n)$ 级别，从而保证了高效的查找、插入和删除操作。

基本概念[编辑 | 编辑源代码]

AVL树的核心特性是每个节点的左右子树高度差（平衡因子）不超过1。平衡因子的计算公式为： $平衡因子 = 左子树高度 - 右子树高度$

如果某个节点的平衡因子绝对值大于1，则需要进行旋转操作来恢复平衡。

AVL树通过四种旋转操作来维持平衡： 1. 左旋（Left Rotation）：适用于右子树过高的情况。 2. 右旋（Right Rotation）：适用于左子树过高的情况。 3. 左右旋（Left-Right Rotation）：先左旋后右旋，适用于左子树的右子树过高的情况。 4. 右左旋（Right-Left Rotation）：先右旋后左旋，适用于右子树的左子树过高的情况。

代码实现[编辑 | 编辑源代码]

以下是一个简单的AVL树实现（使用Python）：

class AVLNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def insert(self, root, key):
        # 标准BST插入
        if not root:
            return AVLNode(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        # 更新高度
        root.height = 1 + max(self.get_height(root.left),
                            self.get_height(root.right))

        # 检查平衡因子
        balance = self.get_balance(root)

        # 不平衡情况处理
        # 左左情况（右旋）
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)
        # 右右情况（左旋）
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)
        # 左右情况（左右旋）
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        # 右左情况（右左旋）
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

    def left_rotate(self, z):
        y = z.right
        T2 = y.left

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

        # 更新高度
        z.height = 1 + max(self.get_height(z.left),
                         self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left),
                         self.get_height(y.right))

        return y

    def right_rotate(self, z):
        y = z.left
        T3 = y.right

        # 执行旋转
        y.right = z
        z.left = T3

        # 更新高度
        z.height = 1 + max(self.get_height(z.left),
                         self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left),
                         self.get_height(y.right))

        return y

    def get_height(self, root):
        if not root:
            return 0
        return root.height

    def get_balance(self, root):
        if not root:
            return 0
        return self.get_height(root.left) - self.get_height(root.right)

示例输入输出[编辑 | 编辑源代码]

插入序列：10, 20, 30, 40, 50, 25

最终AVL树结构：

实际应用[编辑 | 编辑源代码]

AVL树在需要高效查找和动态更新的场景中广泛应用： 1. 数据库索引：许多数据库系统使用AVL树或其变种来实现索引结构。 2. 内存中的有序数据结构：如C++ STL中的`std::map`和`std::set`通常使用红黑树（AVL树的变种）。 3. 文件系统：某些文件系统使用AVL树来维护目录结构。 4. 网络路由表：快速查找IP地址对应的路由信息。

时间复杂度分析[编辑 | 编辑源代码]

由于AVL树始终保持平衡，所有操作的时间复杂度均为 $O (\log n)$ ：

查找： $O (\log n)$
插入： $O (\log n)$ （包括可能的旋转操作）
删除： $O (\log n)$ （包括可能的旋转操作）

与普通二叉搜索树的比较[编辑 | 编辑源代码]

AVL树 vs 普通BST
特性	AVL树	普通BST
平衡性	严格平衡（高度差≤1）	可能退化为链表
查找效率	保证 $O (\log n)$	最坏 $O (n)$
插入/删除效率	$O (\log n)$ （需要旋转）	$O (n)$ （最坏情况）
适用场景	查找密集型应用	插入/删除密集型且数据随机

练习问题[编辑 | 编辑源代码]

1. 给定插入序列[14, 17, 11, 7, 53, 4, 13]，构建AVL树并画出最终结构。 2. 实现AVL树的删除操作。 3. 分析AVL树在内存使用方面与红黑树的差异。

扩展阅读[编辑 | 编辑源代码]

红黑树（Red-Black Tree）：另一种自平衡二叉搜索树，牺牲严格平衡性换取更少的旋转操作。
B树和B+树：适用于磁盘存储的多路平衡搜索树。
伸展树（Splay Tree）：通过"伸展"操作将最近访问的节点移动到根节点附近。