admin管理员组文章数量:1442966
【数据结构】? 并查集优化全解：从链式退化到近O(1)的性能飞跃
导读
大家好，很高兴又和大家见面啦！！！
在上一篇内容中我们正确认识了并查集，并通过数据元素与其双亲指针的映射关系实现了并查集的查找与合并的。
但是上一篇的算法实现中，算法的最坏时间复杂度可以达到O(N)，这并不能很好的满足高效处理动态连通性问题。
在今天的内容中，我们将通过路径优化与按秩合并两种优化方式对并查集实现进一步的优化，大大提高处理动态连通性的效率。
一、合并优化
在并查集中，影响其时间复杂度的操作在查找上，而树的高度h是影响查找时间复杂度的重要因素。那么我们要对并查集的算法进行优化，那就得从树高下手。
下面我们就来看一下如何通过优化不同子集的合并从而优化整个并查集的算法。
1.1 基本原理
当两个树高不同的子集进行合并时，会存在两种合并方案：
- 小树合并到大树
- 大树合并到小树
不难发现，当大树将小树合并时并不会影响大树的树高，但是当小树将大树合并时，则会增加树高。
试想一下，如果我们要完成n棵树的合并，如果将n-1棵小树合并到大树上，这样我们就能保证在进行查找时，能够尽可能的降低查找时间复杂度。
但是当我们在进行合并时，是将大树合并到小树上，则会不断地增加树高，这样每一次合并，都会增加查找的时间复杂度。
因此为了尽可能优化并查集，那么我们在进行合并操作时，应该在每一次合并操作时，都保证是小树合并到大树上。
今天我们介绍两种优化方案——按大小合并、按秩合并。
1.2 按大小合并
按大小合并指的是根据树的大小，将小树合并到大树。
树的大小由树的结点数量决定，结点多的树为大树，结点少的树为小数。通过树的根结点的绝对值表示树的大小。
这里我们以大写字符为例，我们通过一个整型数组parent来存放每个元素的双亲位置信息：
该算法的实现比较简单，我们只需要在合并算法中加入一个对根结点大小的判断，并且在完成合并后，修改根结点的值：
代码语言：javascript代码运行次数：0运行复制//按大小合并优化
void Union_by_Size(DSU* s, int root1, int root2) {
if (root1 != root2) {
//根结点为负数，值越大，结点数量越少
if (s->parent[root1] > s->parent[root2]) {
s->parent[root2] += s->parent[root1];//修改大树根结点
s->parent[root1] = root2;//修改小树根结点
}
else {
s->parent[root1] += s->parent[root2];
s->parent[root2] = root1;
}
}
}通过按大小合并的方式优化，可以极大可能的降低合并后的树高，但是也不一定。
比如结点多但高度低的大树与结点少但高度高的小树进行合并，此时如果按照大小来进行合并，则会增加合并后树的高度。
那有没有不会影响高度的优化方式呢？这就是我们接下来要介绍的按秩合并；
1.3 按秩合并
所谓的秩（Rank）代表的是树合并前的最大高度。
按秩合并实际上就是根据树高进行合并，将矮树合并到高树中，从而确保在完成合并后的树高最小。
合并的规则如下：
- 所有结点的初始高度为0，即根结点的高度为0
- 将秩小的树合并到秩大的树下，秩保持不变
- 将秩相同的两棵树进行合并，合并后，根结点的秩加1
在按秩合并中，我们需要维护两个数组：
- parent数组——记录结点的双亲位置
- rank数组——记录根结点的秩
对应的实现也很简单，如下所示：
代码语言：javascript代码运行次数：0运行复制//按秩合并
void Union_by_Rank(DSU* s, int root1, int root2) {
if (root1 != root2) {
if (s->rank[root1] > s->rank[root2]) {
s->parent[root2] = root1;//低秩合并到高秩中
}
else {
s->parent[root1] = root2;
if (s->rank[root1] == s->rank[root2]) {
s->rank[root2] += 1;//同秩合并，根结点秩+1
}
}
}
}1.4 两种合并的区别
1.4.1 核心目标
特性 | 按秩合并（Union by Rank） | 按大小合并（Union by Size） |
|---|---|---|
优化目标 | 最小化树的高度，优化查询路径长度 | 控制集合规模，优先合并小集合到大集合 |
核心思想 | 通过树高控制，减少路径压缩后的深度 | 通过集合大小控制，降低合并后树高增长的概率 |
1.4.2 数据存储
特性 | 按秩合并 | 按大小合并 |
|---|---|---|
存储信息 | 每个根节点维护一个 rank 值（树高的上界） | 每个根节点维护一个 size 值（集合的节点总数） |
初始值 | rank[x] = 0（单节点树高度为0） | size[x] = 1（单节点集合大小为1） |
存储方式 | 需要独立的 rank[] 数组 | 可复用父节点数组（如父节点为负时表示大小） |
1.4.3 合并逻辑
特性 | 按秩合并 | 按大小合并 |
|---|---|---|
合并方向 | 较矮的树合并到较高的树下 | 较小的集合合并到较大的集合下 |
更新规则 | 若两树秩相同，合并后根节点的秩加1 | 合并后根节点的 size 累加两集合大小 |
代码示例 | if (rank[root1] > rank[root2]) { ... } | if (size[root1] < size[root2]) { ... } |
1.4.4 树高控制
特性 | 按秩合并 | 按大小合并 |
|---|---|---|
树高增长条件 | 仅在合并两棵高度相同的树时，树高+1 | 若小集合树高 > 大集合树高，合并后树高可能增加 |
示例 | 树A（高度2）合并到树B（高度3），树高仍为3 | 树A（高度2，大小10）合并树B（高度3，大小3），树高增至4 |
1.4.5 适用场景
特性 | 按秩合并 | 按大小合并 |
|---|---|---|
典型场景 | 高频查询（如连通性检查、Kruskal算法） | 需要统计集合大小（如社群分析、最大连通图统计） |
内存占用 | 需额外维护 rank[] 数组 | 可复用父节点数组，内存更高效 |
性能优势 | 严格控高，查询效率更稳定 | 直接获取集合大小，适合动态统计需求 |
1.4.6 路径压缩兼容性
路径压缩会在后续的内容继续介绍，这里我们先来初步了解一下这两种合并方式与路径压缩之间的关系：
特性 | 按秩合并 | 按大小合并 |
|---|---|---|
路径压缩影响 | 实际树高可能降低，但 rank 值不更新 | 实际树高可能降低，但 size 值保持准确 |
示例 | 路径压缩后树高为1，但 rank 仍记录为合并前的2 | 路径压缩不影响 size，合并后大小仍为两集合之和 |
1.4.7 极端案例对比
场景：
- 树A：大小100，高度2
- 树B：大小5，高度4
策略 | 合并方向 | 合并后树高 | 树高增长原因 |
|---|---|---|---|
按秩合并 | 树A→树B（秩4） | 4 | 树B高度更高，直接保留原高 |
按大小合并 | 树B→树A | 5 | 树B高度+1（4+1）超过树A高度（2） |
1.4.8 小结
两种优化方式各有优缺点，下面我们就来做个简单的总结：
策略 | 优点 | 缺点 |
|---|---|---|
按秩合并 | 严格控高，查询效率高，适合高频操作 | 无法直接统计集合大小 |
按大小合并 | 内存高效，直接统计大小，适合动态分析场景 | 树高可能失控，查询效率不稳定 |
选择建议： 上述两种优化方式都是可取的，但是需要在不同的情况下采用不同的优化方式：
- 优先 按秩合并：高频查询场景（如算法题、图算法）。
- 先 按大小合并：需统计集合大小或内存敏感的场景。
二、查找优化
2.1 路径压缩
路径压缩是并查集中的一种优化技术，旨在减少查找（Find）操作的时间复杂度。
其核心思想是通过修改树的结构，使得每个节点在查找根节点的过程中，直接或尽可能接近根节点，从而缩短后续操作的路径长度。
什么意思呢？这里我们以前面的例子来说明：
在这个例子中，我们通过路径压缩的方式，让结点G直接指向了根结点，这样当我们在下一次对结点G进行查找操作时，我们只需要查找1次即可完成查找操作；
在原树中，如果我们要对结点G进行查找操作，此时五门需要查找3次才能找到根结点。因此路径压缩能够有效的提高结点在并查集中的查找效率。
2.2 算法实现
路径压缩从上图中我们不难发现，实际上就是将查找结点的双亲指针指向根结点以达到后续的快速查找操作，因此我们在实现路径压缩时，需要执行已下操作：
- 获取根结点的信息
- 改变当前结点的双亲结点指针
- 返回根结点的位置
//路径优化
int Find_by_Path(DSU* s, char ch) {
int key = GetKey(ch);
int root = key;
//查找根结点
while (s->parent[root] != -1) {
root = s->parent[root];
}
//路径压缩
while (key != root) {
int tmp = s->parent[key];//记录父结点
s->parent[key] = root;//将当前结点指向父结点
key = tmp;//继续压缩下一个结点
}
return root;
}三、算法评估
这里我们就不再对该算法进行测试了，有兴趣的朋友可以复制代码后自行测试。下面我们直接来看一下不同的优化方式对算法效率的影响；
3.1时间复杂度
3.1.1 按大小合并（Union by Size）
单独使用时，通过将小集合合并到大集合下，能有效减少树的高度增长概率，但无法完全避免树的高度增加（例如当小集合的树高较大时）。此时，每次操作的时间复杂度为 O(log n)。
当结合路径压缩后，查找操作会将路径上的节点直接指向根节点，使得后续操作的路径长度大幅缩短。此时的时间复杂度被优化到 O(\alpha(n))（阿克曼函数的反函数），在实际应用中可视为常数时间。
注：\alpha(n) 的特性：对 n ≤ 10^{600}，\alpha(n) ≤ 4。
3.1.2 按秩合并（Union by Rank）
单独使用时，通过比较树高（秩）来决定合并方向，严格保证合并后的树高最小化。例如，将较矮的树合并到较高的树下，或仅在树高相同时增加秩。此时的时间复杂度为O(\log n)。
与路径压缩结合后，路径的扁平化进一步将时间复杂度降低到 O(\alpha(n))，与按大小合并的效率一致。
3.1.3 路径压缩（Path Compression）
单独使用路径压缩时，虽然能缩短某些路径的长度，但由于缺乏合并策略的配合，树的高度仍可能因随机合并而增长。因此，路径压缩必须与按大小合并或按秩合并结合使用，才能发挥最大效果，将整体时间复杂度降至接近常数级。
3.2 空间复杂度
3.2.1 按大小合并
按大小合并实际上有两种方式：
- 额外维护一个大小数组size[]，通过该数组记录每个子集的大小，此时会在原有空间消耗的基础上增加一倍的空间消耗，如parent数组的大小为 n，采用该size数组后，空间消耗变成的 2n；
- 直接通过根结点的
parent值来记录子集的大小，这样不会在原有空间消耗的基础上产生额外的空间消耗；
3.2.2 按秩合并
需要额外维护一个 rank[] 数组，用于记录每个根节点的秩（树高的上界）。例如，根节点的秩初始为0（单节点树）。这也需要 O(n)的额外空间，与按大小合并的空间开销类似。
3.2.3 路径压缩
无需任何额外空间，仅通过修改父指针来实现路径的扁平化，因此空间复杂度仍为 O(n)（仅双亲数组的开销）。
3.3 优化策略的协同作用
3.3.1 按大小合并 + 路径压缩
适用于需要统计集合大小的场景（如社交网络中的社群分析）。虽然合并后树高可能因小集合的较高树而增加，但路径压缩会在后续查找中动态缩短路径，最终实现高效操作。
3.3.2 按秩合并 + 路径压缩
适用于高频查询场景（如算法竞赛中的连通性问题）。按秩合并严格控高，路径压缩进一步优化路径长度，两者结合后效率最优。
3.4 极端场景示例
假设存在两棵树：
- 树A：大小100，高度2（大集合矮树）。
- 树B：大小5，高度4（小集合高树）。
3.4.1 按大小合并
将树B合并到树A下，合并后树高为 max(2, 4+1) = 5。路径压缩后，后续查询树B中的节点路径会从5层缩短到2层（树A的根直接指向树B的根）。
3.4.2 按秩合并
将树A合并到树B下（因树B高度更高），合并后树高保持4。路径压缩后，所有节点直接指向根，后续查询仅需1步。
3.5 小结
- 时间复杂度： 单独使用合并策略时为 O(\log n)，结合路径压缩后优化至接近常数的 O(\alpha(n))。
- 空间复杂度： 按大小合并和按秩合并需要额外 O(n) 空间，路径压缩无需额外空间。
- 选择建议：
- 优先按秩合并 + 路径压缩：严格控高，适合高频查询。
- 优先按大小合并 + 路径压缩：适合需统计集合大小的场景。
- 核心理论：路径压缩通过动态修改父指针，与合并策略共同保证了并查集的高效性。
本文标签： 数据结构 并查集优化全解从链式退化到近O(1)的性能飞跃
版权声明：本文标题：【数据结构】? 并查集优化全解：从链式退化到近O(1)的性能飞跃 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/biancheng/1748087684a2804583.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论