按秩合并与路径压缩定理

概述

按秩合并与路径压缩定理（Union-Find with Rank and Path Compression Theorem）：使用按秩合并（union by rank）与路径压缩（path compression）的并查集数据结构，执行 $m$ 次 MAKE-SET、UNION、FIND-SET 操作的总时间为 $O(m\alpha (n))$，其中 $\alpha (n)$ 是反 Ackermann 函数，在实际中 $\alpha (n)\le 4$（对所有实际可能的 $n$）。

定理陈述

形式化陈述

定理（CLRS 定理21.14）：一个由 $n$ 个元素构成的不相交集合森林，使用按秩合并与路径压缩，执行 $m$ 次 MAKE-SET、UNION、FIND-SET 操作的序列（其中 $n$ 次 MAKE-SET），总运行时间为 $O(m\alpha (n))$。

其中 $\alpha (n)$ 是反 Ackermann 函数（inverse Ackermann function），定义为使得 $A(k,k)\ge n$ 的最小整数 $k$，$A$ 为 Ackermann 函数： $A(0,n)=n+1$ $A(k,0)=A(k-1,1),k\ge 1$ $A(k,n)=A(k-1,A(k,n-1)),k,n\ge 1$

关键性质：$\alpha (n)$ 增长极其缓慢，对所有实际可能的输入规模（远小于宇宙原子数），$\alpha (n)\le 4$。因此，并查集的每次操作在实际中可视为 $O(1)$。

证明概要

证明思路

证明分三步：(1) 按秩合并保证树高 $O(\log n)$；(2) 路径压缩进一步优化；(3) 通过势能分析（accounting method）结合 Ackermann 函数的层级结构，得到 $O(m\alpha (n))$ 的总时间上界。

第一步：按秩合并的分析

按秩合并（union by rank）：每个节点维护一个秩（rank），初始为 0。UNION 操作时，将秩较小的树根作为秩较大的树根的子节点。若两棵树秩相同，任选一个为根，秩加 1。

引理：使用按秩合并的并查集中，每个节点的秩至多为 $\lfloor {\log }_{2}n\rfloor$。

证明：对秩 $r$ 的节点 $x$，其子树大小至少为 $2^r$（归纳可证）。由于子树大小不超过 $n$，故 $2^r\le n$，即 $r\le \lfloor {\log }_{2}n\rfloor$。

因此，不使用路径压缩时，FIND-SET 的时间为 $O(\log n)$，$m$ 次操作的总时间为 $O(m\log n)$。

第二步：路径压缩的效果

路径压缩（path compression）：在 FIND-SET($x$) 的执行过程中，将从 $x$ 到根的路径上所有节点的父指针直接指向根节点。

路径压缩使得后续的 FIND-SET 操作更快，但分析其效果非常复杂——因为路径压缩会改变树的结构，使得秩不再精确反映树高。

第三步：势能分析（核心）

定义节点的层级（level）和迭代次数（iteration count）：

• 节点 $x$ 的层级 $\ell (x)$ 是使得 $\text{rank}(x)<A(\ell (x),\text{rank}(x))$ 的最大整数 $\ell$（若不存在则为 $\alpha (n)$）。
• 节点 $x$ 在层级 $\ell$ 上的迭代次数 $i(x)$ 是使得 $\text{rank}(x)<A(\ell ,i(x))$ 的最大整数 $i$。

势能函数：为每个 FIND-SET 操作分配”记账代价”。路径上每个节点根据其层级和迭代次数被记账。

关键观察：

1. 层级 $\ell \ge \alpha (n)$ 的节点不会被记账（因为 $\alpha (n)$ 是最大可能的层级）。
2. 在层级 $\ell <\alpha (n)$ 上，每个节点的迭代次数 $i(x)\le \alpha (n)$。
3. 路径压缩使得节点的迭代次数增加，但每个节点的迭代次数最多增加 $\alpha (n)$ 次。
4. 因此，$m$ 次操作中，所有记账代价的总和为 $O(m\alpha (n))$。

参考文献：

• CLRS 第4版，第19章 “Disjoint-set data structures”，定理21.14
• Tarjan, R.E., “Efficiency of a good but not linear set union algorithm”, JACM, 22(2):215-225, 1975
• UCSD CSE 100 Notes: https://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec14/lec14-17.html
• U of Toronto CSC265 Notes: http://www.cs.toronto.edu/~anikolov/CSC265F19/DisjointSets-logstar.pdf

关键推论

• 实际常数时间：由于 $\alpha (n)\le 4$ 对所有实际输入成立，并查集操作在实际应用中可视为 $O(1)$。
• MST 算法的优化：Kruskal 算法使用并查集检测回路，$O(E\log E)$ 的时间中，排序占主导，并查集操作不增加渐近复杂度。
• 按秩合并 vs 按大小合并：按大小合并（union by size）与按秩合并效果相同，都保证树高 $O(\log n)$。
• 仅路径压缩：仅使用路径压缩（不使用按秩合并）时，$m$ 次操作的摊还时间为 $O(m{\log }^{\ast }n)$，其中 ${\log }^{\ast }n$ 是迭代对数函数。

应用场景

在算法导论中的具体应用：

1. Kruskal 最小生成树算法（Ch19）：并查集用于高效判断两个顶点是否在同一连通分量中（检测回路），是 Kruskal 算法的核心数据结构。
2. 动态连通性：维护一个不断变化的图的连通分量信息，支持”合并两个分量”和”查询两个元素是否连通”两种操作。
3. 网络连通性分析：在社交网络、计算机网络中判断两个节点是否连通。
4. 图像处理：在图像分割中，并查集用于高效合并相邻的相似区域。
5. 编译器优化：在寄存器分配和等价类分析中使用并查集管理变量间的等价关系。

参见

• 贪心算法
• 动态规划
• 图论