按秩合并

概述

按秩合并（Union by Rank）是不相交集合森林中的合并优化策略，类似于按高度合并。每个节点维护一个秩（rank），执行 LINK 时总是将低秩根作为高秩根的子节点，从而保持树的浅层结构。

定义

按秩合并

在不相交集合森林中，每个节点 $x$ 维护一个非负整数属性 rank[x]：

• MAKE-SET 时，rank[x] = 0
• LINK(x, y) 时（$x,y$ 为不同树的根）：
  • 若 rank[x] > rank[y]：令 $y$ 成为 $x$ 的子节点（y.parent = x）
  • 若 rank[x] < rank[y]：令 $x$ 成为 $y$ 的子节点（x.parent = y）
  • 若 rank[x] = rank[y]：任意选择（通常令 $x$ 成为 $y$ 的子节点），且 rank[y] = rank[y] + 1

秩的直观含义：rank[x] 是 $x$ 为根的子树高度的上界。

LINK 伪代码

LINK(x, y)
1  if x.rank > y.rank
2      y.parent = x
3  else x.parent = y
4      if x.rank == y.rank
5          y.rank = y.rank + 1

核心性质

引理：秩的上界

引理

若使用按秩合并（不使用路径压缩），则对任意节点 $x$，rank[x] 的值永远不会超过 $\lfloor \lg n\rfloor$，其中 $n$ 是 MAKE-SET 操作创建的元素总数。

证明思路：

对秩 $r$ 归纳，证明在任何时刻秩恰好为 $r$ 的根节点至少有 $2^r$ 个后代（包括自身）。

• 基础：$r=0$ 时，秩为 0 的根至少有 $2^0=1$ 个后代（自身），成立。
• 归纳：假设对秩 $r$ 成立。一个根获得秩 $r+1$ 的唯一方式是两个秩均为 $r$ 的根合并。由归纳假设，每个秩为 $r$ 的根至少有 $2^r$ 个后代，合并后至少有 $2^r+2^r=2^{r+1}$ 个后代。

因此秩为 $r$ 的根至少有 $2^r$ 个后代。由于总元素数为 $n$，有 $2^r\le n$，即 $r\le \lfloor \lg n\rfloor$。$■$

推论：树的高度

树高上界

使用按秩合并（不使用路径压缩）时，每棵树的高度 $h\le \lfloor \lg n\rfloor$，因此 FIND-SET 的最坏时间为 $O(\lg n)$。

引理：秩的严格递增

秩的单调性

沿任意节点到根的路径，秩严格递增（不使用路径压缩时）。即若 $y$ 是 $x$ 的真祖先，则 rank[y] > rank[x]。

证明：LINK 操作保证子节点的秩不超过父节点的秩，且只有当两个根秩相等时才会增加秩，因此父节点的秩严格大于子节点的秩。$■$

按秩合并 vs 按大小合并

特性	按秩合并	按大小合并
维护属性	rank（高度上界）	size（集合大小）
合并规则	低秩根 → 高秩根	小集合根 → 大集合根
理论复杂度	$O(m\alpha (n))$（+路径压缩）	$O(m\alpha (n))$（+路径压缩）
路径压缩后的性质	秩变为高度的上界	大小保持精确
实践表现	略优	有时更优

实践中的选择

在实际实现中，按大小合并有时表现更好，因为路径压缩后秩不再是精确的高度，而大小始终保持准确。但两者在理论上具有相同的渐近复杂度。CLRS 主要讨论按秩合并。

路径压缩对秩的影响

当同时使用路径压缩时，秩不再精确反映子树高度，而是变为高度的上界。这是因为路径压缩可能缩短某些路径，使得实际高度小于秩。然而，秩的上界性质（rank[x] ≤ ⌊lg n⌋）仍然成立，且按秩合并的 LINK 规则无需修改。

第21章：最小生成树

Kruskal算法中使用按秩合并优化并查集。每条边处理时执行两次 FIND-SET 和可能的 UNION。按秩合并保证树高度 O(α(V))，使 FIND-SET 接近常数时间，Kruskal总时间 O(E α(V))。

参见

• 不相交集合森林 — 森林表示的总览与操作伪代码
• 路径压缩 — FIND-SET 中的路径优化，与按秩合并结合达到最优复杂度
• 反阿克曼函数 — $O(m\alpha (n))$ 复杂度中的关键函数
• 加权合并启发式 — 链表表示中的类似优化思想