并查集 rank 的优化（实战指南）

并查集 rank 的优化：让数据结构跑得更快

在算法世界里，有些数据结构看似简单，却能在关键时刻拯救性能。并查集（Union-Find）就是其中之一。它常用于解决“动态连通性”问题——比如社交网络中判断两个人是否属于同一个朋友圈，或者图中判断两个节点是否连通。

然而，如果你只用最基础的并查集实现，当数据量变大时，性能会急剧下降。这时，并查集 rank 的优化就显得尤为重要。它能将原本可能退化到 O(N) 的操作，压缩到接近常数时间。今天我们就来深入聊聊这个优化技巧。

什么是并查集？先从基础说起

并查集是一种支持两种操作的数据结构：

• Union：合并两个集合。
• Find：查找某个元素属于哪个集合。

想象你有多个小组，每个小组有一个“组长”。当你想把两个小组合并时，只需让其中一个组长去听另一个组长的指挥。这个“组长”就是并查集中的“根节点”。

最简单的实现方式是用一个数组 parent[] 来记录每个元素的父节点。初始时，每个元素的父节点是自己，表示它们各自是一个独立的集合。

def initialize(n):
    parent = [i for i in range(n)]  # 每个元素的父节点是自己
    return parent

比如 parent = [0, 1, 2, 3]，表示有 4 个独立的集合：{0}, {1}, {2}, {3}。

为什么基础版本会变慢？树的“歪斜”问题

当不断执行 Union 操作时，如果总是把一个树接到另一个树的根上，就可能出现“链式结构”——比如：

0 → 1 → 2 → 3 → 4

这时，每次 Find(4) 都需要从 4 一路往上走，直到 0，时间复杂度变成 O(N)。当数据量大时，这会严重影响性能。

这就像是你在一个学校里找校长，但每层楼都只有一个门，而且门牌号是递增的，你必须一层层爬上去。如果楼太高，找人就特别慢。

所以，我们需要一种方式让树尽可能“扁平”，让每个节点离根的距离尽可能短。

引入 rank：用“高度”来指导合并

rank 的优化就是为每个根节点维护一个“rank”值，表示以它为根的树的“理论高度”（实际不一定是真实高度，只是一个估算值）。

合并时，我们总是把 rank 小的树接到 rank 大的树下面。如果 rank 相同，就随便接，但接完后，新根的 rank 要 +1。

这个策略可以有效避免树的“歪斜”，让整体结构更平衡。

def initialize_with_rank(n):
    parent = [i for i in range(n)]
    rank = [0] * n  # rank[i] 表示以 i 为根的树的估计高度
    return parent, rank

Union 操作中如何使用 rank？

我们来实现一个带 rank 优化的 Union 操作。

def union(parent, rank, x, y):
    root_x = find(parent, x)  # 找到 x 的根
    root_y = find(parent, y)  # 找到 y 的根

    # 如果已经在同一个集合，无需合并
    if root_x == root_y:
        return

    # 根据 rank 决定谁当新根
    if rank[root_x] < rank[root_y]:
        parent[root_x] = root_y  # 让 rank 小的挂到 rank 大的下面
    elif rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        # rank 相同，随便挂，但新根的 rank +1
        parent[root_y] = root_x
        rank[root_x] += 1

✅ 关键点：只有当两棵树 rank 相同时，才会导致新树的高度增加。这保证了树的生长是“缓慢而均衡”的。

Find 操作的路径压缩：再优化一步

虽然 rank 优化已经很好了，但我们还可以再加一个优化：路径压缩。

它的思想是：在 Find 的过程中，把沿途的所有节点直接连接到根节点上。这样以后再查找这些节点，就一步到位了。

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 递归压缩路径
    return parent[x]

💡 比喻：就像你去图书馆找书，第一次走了一圈，记住了每一步。第二次再去，直接从门口走过去，因为上次已经把路线“记下来”了。

这个优化和 rank 优化可以并行使用，效果极佳。

实际案例：判断朋友圈是否连通

我们用一个真实场景来演示。

假设有 6 个人，编号 0 到 5。已知以下关系：

• 0 和 1 是朋友
• 1 和 2 是朋友
• 3 和 4 是朋友
• 4 和 5 是朋友
• 2 和 3 是朋友

问：0 和 5 是否在同一个朋友圈？

def main():
    n = 6
    parent, rank = initialize_with_rank(n)

    # 朋友关系
    edges = [(0,1), (1,2), (3,4), (4,5), (2,3)]

    for x, y in edges:
        union(parent, rank, x, y)

    # 检查 0 和 5 是否连通
    if find(parent, 0) == find(parent, 5):
        print("0 和 5 属于同一个朋友圈")
    else:
        print("0 和 5 不在同一个朋友圈")

main()

输出结果：0 和 5 属于同一个朋友圈

这个例子中，rank 的优化确保了合并过程高效，路径压缩让后续查询极快。

rank 优化的性能对比

我们来对比一下不同策略下的性能表现。

📌 注：α(N) 是阿克曼函数的反函数，增长极其缓慢。即使 N = 2^64，α(N) 也小于 5。

这就是为什么在 LeetCode、ACM 等平台，并查集 rank 的优化是标配。

常见误区与注意事项

1. rank 不等于真实高度：rank 只是估计值，用于决策合并方向。即使树实际高度更高，也不影响正确性。
2. 不要在每次 Union 后更新所有节点的 rank：只更新根节点的 rank 即可。
3. 路径压缩不能破坏 rank 逻辑：虽然路径压缩改变了父节点，但 rank 仅用于合并决策，不影响 Find 的正确性。

总结：为什么要用 rank 优化？

并查集在处理大规模连通性问题时，性能至关重要。并查集 rank 的优化不是“锦上添花”，而是“雪中送炭”。

• 它让树结构保持平衡，避免退化成链表。
• 它与路径压缩配合，达到近乎常数时间的操作效率。
• 它逻辑清晰，实现简单，是算法面试中的高频考点。

掌握 rank 优化，不仅能让你写出更高效的代码，更能让你在面对复杂问题时，拥有更深层的数据结构思维。

如果你正在准备面试，或者在刷算法题时频繁遇到并查集，那么现在就是你深入理解并查集 rank 优化的最佳时机。

别再让一棵歪歪扭扭的树拖慢你的程序。用 rank 优化，让并查集真正“快如闪电”。