并查集 rank 的优化
关键要点
- 研究表明，并查集的 rank 优化通过维护集合的秩（rank）来保持树的高度较低，适合动态连通性问题。
- 证据倾向于 rank 优化将秩较小的树连接到秩较大的树上，平均时间复杂度接近常数 (O(\alpha(n)))。
- 存在争议：rank 优化与 size 优化效果相似，具体选择可能因场景而异。
什么是 rank 优化？
并查集（Union-Find）是一种用于管理不相交集合的数据结构，主要支持查找和合并操作。rank 优化是一种提高合并效率的方法，通过维护每个集合的秩（rank，通常是树的高度或其上界）来决定合并方向，确保树结构平衡。
如何工作？
- 维护一个 rank 数组，
rank[i]表示以 (i) 为根节点的树的秩。 - 合并时，比较两个集合的秩：
– 如果一个集合的秩小于另一个，则将秩小的集合连接到秩大的集合。
– 如果秩相等，则任意选择一个作为父节点，并将新根节点的秩增加1。 - 这种方法减少了树的高度，使查找操作更快。
为什么有用？
研究表明，rank 优化结合路径压缩后，操作时间复杂度接近常数 (O(\alpha(n)))，非常适合处理大规模动态连通性问题，如图的连通分量判断。
应用场景
常用于最小生成树算法（如 Kruskal 算法）和社交网络的连通性判断。
参考资料：
并查集 rank 优化的详细报告
背景与定义
并查集（Union-Find），也称为不相交集合数据结构，是一种树形的数据结构，主要用于处理动态连通性问题，如判断图中两个节点是否属于同一个连通分量，或在最小生成树算法（如 Kruskal 算法）中检测循环。研究表明，它通过一个数组表示一组森林，每棵树代表一个集合，树的根节点作为集合的代表元。
rank 优化，具体来说是“按秩合并”（Union by Rank），是一种优化 Union 操作的方法，旨在通过维护集合的秩（rank）来保持树的平衡，从而提高查找和合并的效率。多个来源（如 OI Wiki、CSDN 博客和菜鸟教程）指出，这种优化与路径压缩（Path Compression）和按大小合并（Union by Size）一起，是并查集高效性的关键。
从菜鸟教程（web:0）、CSDN 博客（web:1, web:2）等来源可以看出，rank 优化的核心思想是通过维护树的高度或其上界，确保合并操作后树的高度不会显著增加，从而减少后续查找操作的深度。
并查集的基本操作
并查集支持以下主要操作：
- 初始化（Initialization）：
– 每个元素最初自成一个集合，形成一棵只有根节点的树。
– 实现上，使用数组parent，初始时parent[i] = i，表示每个元素是自己的父节点。
– 同时，初始化 rank 数组，rank[i] = 1，表示每个集合初始为单层树。 - 查找（Find）：
– 查找操作的目标是找到某个元素的根节点，即集合的代表元。
– 基本实现是通过递归或迭代向上遍历父节点，直到找到根节点（即parent[x] == x）。
– 示例代码（C++）：
cpp int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); // 路径压缩 } - 合并（Union）：
– 合并操作将两个集合合并成一个，通常是将一个集合的根节点连接到另一个集合的根节点。
– 基本实现：
cpp void unite(int x, int y) { int px = find(x); int py = find(y); if (px == py) return; parent[px] = py; // 简单合并 }
– 未优化时，如果树深度过高，合并操作可能需要 (O(n)) 时间。
rank 优化的原理
rank 优化的核心思想是：在合并两个集合时，总是将秩较小的集合（即树高度较低的集合）连接到秩较大的集合（即树高度较高的集合）上，从而保持树的平衡，减少树的高度。
具体实现步骤：
- 维护一个 rank 数组，其中
rank[i]表示以 (i) 为根节点的树的秩（通常是树的高度或其上界）。 - 在合并操作时：
– 找到两个集合的根节点 (root1 = find(x))，(root2 = find(y))。
– 比较rank[root1]和rank[root2]：
– 如果rank[root1] < rank[root2]，则将 (root1) 连接到 (root2) 上，即parent[root1] = root2。
– 如果rank[root1] > rank[root2]，则将 (root2) 连接到 (root1) 上，即parent[root2] = root1。
– 如果rank[root1] == rank[root2]，则任意选择一个作为父节点（例如，将 (root2) 连接到 (root1) 上），并更新rank[root1] += 1。 - 确保合并后，树的高度不会显著增加。
例如，从菜鸟教程（web:0）中可以看到，rank 优化通过维护 rank 数组，确保小树连接到大树上，减少树的高度。例如，合并时选择方法二（小树挂大树）比方法一（大树挂小树）更优，因为树的高度从 4 层减少到 3 层。
示例分析
假设有一个并查集，初始状态为 5 个独立的集合：{0}, {1}, {2}, {3}, {4}，对应的父节点数组 parent 为 [0, 1, 2, 3, 4]，rank 数组为 [1, 1, 1, 1, 1]。
- 步骤 1：合并 {0} 和 {1}。
–rank[0] = 1，rank[1] = 1。
– 由于相等，可以任意选择，假设将 0 连接到 1 上：parent[0] = 1，rank[1] = 2。
– 现在，parent = [1, 1, 2, 3, 4]，rank = [1, 2, 1, 1, 1]。 - 步骤 2：合并 {1} 和 {2}。
–rank[1] = 2，rank[2] = 1。
–rank[2] < rank[1]，将 2 连接到 1 上：parent[2] = 1，rank[1]保持为 2（因为高度未增加）。
– 现在，parent = [1, 1, 1, 3, 4]，rank = [1, 2, 1, 1, 1]。 - 步骤 3：查找 2 的根节点。
– 通过parent数组，2 的父节点是 1，1 的父节点是 1（根节点）。
– 因此，2 的根节点是 1，时间复杂度为 (O(1))。
通过 rank 优化，树的高度被控制在较低水平，确保了查找操作的高效性。
性能分析
- 未优化时：
– 合并操作：最坏情况下 (O(n))（例如，形成一条长链）。
– 查找操作：最坏情况下 (O(n))。 - rank 优化后：
– 合并和查找操作的平均时间复杂度为 (O(\alpha(n)))，其中 (\alpha(n)) 是逆阿克曼函数（几乎为常数）。
– 空间复杂度为 (O(n))，用于存储父节点数组和 rank 数组。
从 CSDN 博客（web:1）中可以看到，rank 优化结合路径压缩后，可以使并查集在处理大规模动态连通性问题时表现更稳定，运行时间显著减少。
与其他优化的比较
- 路径压缩（Path Compression）：在查找过程中，将路径上的所有节点直接指向根节点，进一步减少树的高度。
- 按大小合并（Union by Size）：类似于 rank 优化，但使用集合的大小来决定合并方向。
研究表明，rank 优化和 size 优化在效果上相似，但 rank 优化更关注树的高度，而 size 优化关注集合大小。OI Wiki（web:6）提到，这两种方法都能有效控制树的高度，但具体选择可能因场景而异。
应用场景
rank 优化广泛应用于以下场景：
- 动态连通性问题：判断图中两个节点是否连通，例如在无向图中查找连通分量。
- 最小生成树：在 Kruskal 算法中，用于检测添加边是否会形成循环。
- 社交网络：判断两个人是否通过朋友关系间接相连。
- 其他问题：如 NOI2001 的食物链问题、NOI2015 的程序自动分析等。
从 Runoob（web:0）中可以看到，rank 优化能更高概率生成层数较低的树，特别适合处理大规模数据。
争议与局限
研究表明，并查集在合并和查询操作上非常高效，但存在一些争议：
- 未优化时，合并操作可能退化为 (O(n))，尤其在树深度过高时。
- 关于是否使用 rank 优化还是 size 优化，研究没有绝对共识，实际应用中两者效果相似，通常选择 rank 优化更关注树的高度。
- 并查集不支持高效的集合分割操作，分割集合的复杂度较高。
表格总结
以下表格总结了 rank 优化的主要特性：
| 特性 | 描述 |
|---|---|
| 优化目标 | 通过维护集合的秩（rank），保持树的高度较低 |
| 实现方法 | 维护 rank 数组，合并时秩小的集合连接到秩大的集合，更新 rank 值 |
| 时间复杂度 | 平均 (O(\alpha(n)))，最坏 (O(n))（未优化） |
| 空间复杂度 | (O(n)) |
| 典型应用 | 动态连通性问题、最小生成树、社交网络连通性判断 |
参考资料
总结
并查集的 rank 优化是一种简单有效的技术，通过在合并操作时优先将秩小的集合合并到秩大的集合中，保持树结构的平衡，显著提高了并查集的性能。这种优化结合路径压缩（path compression）技术，可以使并查集的操作效率接近常数级别，非常适合处理大规模动态连通性问题。