平衡树

算法概述

【平衡树】是一类特殊的二叉搜索树，它通过一定的机制保证树的高度平衡，从而确保各种操作（查找、插入、删除）的时间复杂度维持在O(log n)级别。常见的平衡树包括AVL树、红黑树、Treap、SPlay树等。

平衡树的核心思想是：在保持二叉搜索树基本性质的同时，通过自平衡操作防止树退化成链表，避免最坏情况下O(n)的操作时间复杂度。

平衡树的类型

1. AVL树

AVL树是最早被发明的自平衡二叉搜索树，其特点是任何节点的两个子树高度差不超过1。

特点：

• 严格平衡：任意节点的左右子树高度差不超过1
• 通过旋转操作维护平衡
• 查找、插入、删除操作的时间复杂度均为O(log n)
• 平衡因子：左子树高度减右子树高度的值

应用场景：

• 适合读操作较多的场景
• 需要严格平衡的场景

2. 红黑树

红黑树是一种广泛使用的平衡二叉搜索树，它通过节点染色和一系列规则维护平衡。

特点：

• 每个节点非红即黑
• 根节点和叶节点(NIL)是黑色
• 红色节点的子节点必须是黑色
• 从任一节点到其叶节点的路径上黑节点数量相同
• 平衡性不如AVL树严格，但调整开销更小

应用场景：

• C++ STL中的set、map、multiset、multimap
• Linux内核中的红黑树
• 读写操作都比较频繁的场景

3. Treap

Treap是树堆的简称，它将二叉搜索树与堆的特性结合，通过随机优先级维持平衡。

特点：

• 每个节点有两个键：一个是BST的键，另一个是随机分配的优先级
• 按BST键维护二叉搜索树性质
• 按优先级维护最大堆性质
• 实现简单，期望时间复杂度为O(log n)

应用场景：

• 需要分裂和合并操作的场景
• 实现简单但仍需保持较好平衡性的场景

4. Splay树

Splay树是一种自调整的二叉搜索树，它不严格保持平衡，但通过伸展操作使频繁访问的元素更易于访问。

特点：

• 每次操作后将被访问的节点旋转到根部
• 不保证最坏情况的O(log n)时间复杂度，但均摊复杂度为O(log n)
• 自适应性强，对连续访问相同或邻近元素效率高

应用场景：

• 有局部性的访问模式（相同或邻近元素被频繁访问）
• 缓存实现
• 需要支持区间操作的场景

平衡树在ACM竞赛中的应用

在ACM竞赛中，平衡树主要用于以下场景：

1. 动态维护有序集合：需要支持插入、删除、查找、排名等操作
2. 区间查询与修改：某些平衡树变体可以支持高效的区间操作
3. 求解第k大/小元素：维护元素顺序和数量
4. 动态维护统计信息：如区间和、最大值等
5. 可持久化数据结构：记录历史版本，支持历史查询

常见操作的实现思路

所有平衡树都支持以下基本操作，各自实现细节有所不同：

1. 查找操作

与普通二叉搜索树相同，自顶向下查找，时间复杂度O(log n)。

2. 插入操作

将新元素插入适当位置后，需要进行平衡调整：

• AVL树：更新平衡因子，必要时进行旋转
• 红黑树：染色并可能旋转以维持红黑性质
• Treap：通过旋转维持堆性质
• Splay树：将新插入的节点伸展到根部

3. 删除操作

删除节点后，同样需要进行平衡调整，算法与插入类似但通常更复杂。

4. 旋转操作

旋转是平衡树调整平衡的核心操作，主要有左旋和右旋两种：

• 左旋：将右子节点升为父节点，原父节点变为左子节点
• 右旋：将左子节点升为父节点，原父节点变为右子节点

STL中的平衡树

C++ STL中的有序关联容器（set, map, multiset, multimap）通常基于红黑树实现，提供以下操作：

// 使用set存储有序数据
set<int> s;
s.insert(5);  // 插入元素
s.erase(5);   // 删除元素
auto it = s.find(5);  // 查找元素，返回迭代器
auto it = s.lower_bound(5);  // 返回大于等于5的第一个元素迭代器
auto it = s.upper_bound(5);  // 返回大于5的第一个元素迭代器

这些容器提供了平衡树的基本功能，但在ACM竞赛中，有时候需要更多的操作，如求第k大元素、区间操作等，这时可能需要自己实现平衡树或扩展STL容器。

竞赛使用提示

1. 优先考虑STL：大多数情况下，STL的set和map已经足够高效，避免重复造轮子
2. 正确选择平衡树类型：
   • 元素操作比较均衡时，选择红黑树
   • 读操作远多于写操作时，选择AVL树
   • 需要区间操作时，考虑Splay树或线段树
3. 平衡和复杂度的权衡：实现复杂的平衡树可能不值得，有时一个简单的解决方案更可行
4. 替代选择：某些情况下，可以用其他数据结构替代平衡树，如树状数组、线段树、跳表等

比较：平衡树与其他数据结构

进阶内容：自定义平衡树

在竞赛中可能需要实现带有额外功能的平衡树，如支持求第k大元素或区间操作。这些功能可以通过在节点中维护子树大小、子树和等信息来实现。

典型例题：第k大数

问题：维护一个数据集合，支持插入、删除、查询第k大的数。

提示：可以用平衡树（如红黑树或treap）实现，在每个节点中维护以该节点为根的子树的节点数量。

总结

平衡树是一类保持平衡的二叉搜索树，它确保树的高度近似O(log n)，从而保证各种操作的对数时间复杂度。在ACM竞赛中，平衡树是处理动态有序集合的强大工具。深入了解各种平衡树的特点和实现方法，可以根据具体问题选择最合适的数据结构。

更多详细的实现和应用，请参考本章中的【红黑树】和【跳表】等具体数据结构的详细介绍。