编辑“︁AVL树”︁（章节）

= AVL树 =

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

== 基本概念 ==

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

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

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

== 代码实现 ==

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

<syntaxhighlight lang="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)
</syntaxhighlight>

=== 示例输入输出 ===
插入序列：10, 20, 30, 40, 50, 25

最终AVL树结构：
<mermaid>
graph TD
    30((30))
    20((20)) --> 30
    40((40)) --> 30
    10((10)) --> 20
    25((25)) --> 20
    50((50)) --> 40
</mermaid>

== 实际应用 ==

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

== 时间复杂度分析 ==

由于AVL树始终保持平衡，所有操作的时间复杂度均为<math>O(\log n)</math>：
* 查找：<math>O(\log n)</math>
* 插入：<math>O(\log n)</math>（包括可能的旋转操作）
* 删除：<math>O(\log n)</math>（包括可能的旋转操作）

== 与普通二叉搜索树的比较 ==

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

== 练习问题 ==

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

== 扩展阅读 ==

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:非线性数据结构]]