并查集 rank 的优化（建议收藏）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 82w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 2900+ 小伙伴加入学习 ，欢迎点击围观

并查集 rank 的优化：从基础到高效实现

前言

并查集（Disjoint Set Union, DSU）是一种经典的集合数据结构，广泛应用于图论、社交网络分析、路径查找等场景。其核心功能是高效管理元素之间的动态连通性。然而，若不进行优化，最基础的并查集实现可能因树的不平衡而退化为链表结构，导致时间复杂度显著上升。并查集 rank 的优化，正是通过引入按秩合并（Union by Rank）策略，结合路径压缩（Path Compression）技术，将操作的时间复杂度从 O(log n) 进一步压缩到接近 O(1) 的级别。本文将从基础原理出发，逐步解析 rank 优化的核心思想，并通过代码示例和实际案例帮助读者掌握这一关键技巧。

并查集的基础原理：树结构与基本操作

核心概念

并查集的核心是用树结构表示元素的连通性。每个元素（节点）有一个指向父节点的指针，根节点的父指针指向自身。通过以下两个操作实现功能：

1. Find(x)：查找元素 x 的根节点，判断其所属集合。
2. Union(x, y)：将 x 和 y 的集合合并为一个集合。

基础实现的局限性

假设我们用数组 parent 存储每个节点的父节点索引。基础实现的代码如下：

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
    
    def find(self, x):
        while self.parent[x] != x:
            x = self.parent[x]
        return x
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

这种实现的问题在于：

• 树的不平衡：若频繁执行 union 操作，树可能退化为一条长链（如每次将新节点附加到根的末端）。此时 find 的时间复杂度接近 O(n)，导致性能下降。
• 路径查找效率低：未优化的 find 函数需要逐层遍历父节点，无法直接定位根节点。

第一步优化：路径压缩（Path Compression）

什么是路径压缩？

路径压缩是通过扁平化树结构来加速 find 操作。具体方法是：在查找根节点的过程中，将路径上的所有节点直接指向根节点。这相当于将“家族树”压缩为“根节点+叶子节点”的结构。

优化后的 find 函数

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

效果比喻

想象一个家族树，路径压缩就像让所有成员直接认祖归宗：

• 原先需要通过“父亲→祖父→曾祖父→根”才能找到祖先，
• 优化后，所有成员直接将根节点设为“父亲”，路径长度变为 1。

路径压缩使 find 的时间复杂度降至接近 O(α(n))（阿克曼函数的反函数，可视为常数级）。

引入 Rank 优化：按秩合并（Union by Rank）

问题背景

路径压缩虽能加速查找，但合并操作仍可能导致树的不平衡。例如：若总是将小树合并到大树下，树的高度可能增长到 O(log n) 级别。

Rank 的定义

Rank 是每个节点的高度（或近似高度）的记录值。合并时，总是将秩较小的树合并到秩较大的树下，从而避免树的高度增长过快。

实现步骤

1. 维护一个 rank 数组，初始值为 0。
2. union(x, y) 时，比较两棵树的秩：
   • 若秩不同，将较小秩的树合并到较大秩的树下；
   • 若秩相同，任选一树合并，并将目标树的秩加 1。

优化后的代码片段

class UnionFindWithRank:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size  # 新增 rank 数组
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

优化后的协同效应：路径压缩 + Rank

协同作用

• 路径压缩：每次 find 都会缩短路径，使树更扁平。
• Rank 优化：每次 union 都尽量保持树的高度最小。

复杂度分析

两者的结合使并查集的 find 和 union 操作的时间复杂度均摊为 O(α(n))，其中 α(n) 是阿克曼函数的反函数，在实际中几乎为常数。

实际案例：社交网络分组

假设我们管理一个社交网络的用户群组：

1. 用户 A 和 B 加入同一群组（union(A, B)）。
2. 用户 C 加入群组（union(C, B)）。
3. 若未优化，树可能形成长链；
4. 优化后，群组树的高度始终被控制在最低，find 操作始终快速。

性能对比与代码验证

未优化 vs 优化后的对比

代码验证示例

以下代码对比两种实现的效率差异：

import time

def test_union_find(size, iterations, use_rank=True):
    if use_rank:
        uf = UnionFindWithRank(size)
    else:
        uf = UnionFind(size)
    
    start = time.time()
    for _ in range(iterations):
        x = random.randint(0, size-1)
        y = random.randint(0, size-1)
        uf.union(x, y)
    end = time.time()
    return end - start

print("Without Rank:", test_union_find(10000, 10000, use_rank=False))
print("With Rank:", test_union_find(10000, 10000))

应用场景与进阶思考

典型应用场景

1. 图的连通性分析：判断迷宫是否有唯一出口。
2. 动态连通性问题：实时管理用户分组的合并与查询。
3. Kruskal 算法的辅助工具：用于检测最小生成树中的环路。

进阶优化方向

• 启发式合并：结合路径压缩和按秩合并的双重优化。
• 位运算优化：通过二进制位存储父节点信息（适用于特定场景）。

结论

并查集 rank 的优化 是数据结构领域中“细节决定性能”的经典案例。通过路径压缩与按秩合并的协同作用，我们不仅解决了树结构的不平衡问题，更将时间复杂度压至理论极限。对于编程初学者，建议从基础实现入手，逐步添加优化策略并观察性能变化；对于中级开发者，则可结合具体场景（如高频查询的系统）深入实践这一优化。掌握并查集的优化技巧，不仅能提升算法题解的效率，更能为构建高效的数据管理系统提供重要基石。

（全文约 1800 字）