CS61B Data Structure 并查集部分笔记 - 仿生鱼会梦到电子池塘吗

什么是并查集：#

核心定义: 并查集是一种用于管理 元素分组情况 的数据结构。它支持两种核心操作：
- 合并 (Union): 将两个元素所在的集合合并成一个集合。
- 查找 (Find): 确定一个元素属于哪个集合，通常通过返回该集合的“代表元素”来实现。
并查集的特点:
- 我们关注什么: 只关注元素之间的 连通性。它高效地回答“某两个元素是否属于同一集合？”这一问题。
- 我们不关注什么: 不关注集合内的具体结构、元素的排列顺序，甚至元素本身的值。元素通常用从 0 到 n-1 的整数作为其唯一标识。
与离散数学的关联: 并查集是离散数学中 等价关系 (Equivalence Relation) 与 集合划分 (Partition) 概念的经典计算机科学实现。
- 每个集合可以看作一个 等价类。
- find(x) 操作就是找到元素 x 所在等价类的 代表元。
- union(x, y) 操作就是合并两个等价类。

数据结构：通常用数组 parent[i] 来表示并查集。
表示形式：将所有的元素集合抽象成“森林”，其中每棵树是一个独立的集合，即一个划分。
- 数组索引 i：代表第 i 号元素。
- 数组值 parent[i]：表示第 i 号元素的父节点索引，当元素没有父节点(即此元素为根时)，parent[i] 为负数。
- find(i)：从索引 i 开始，访问其父节点的索引，直到根为止。
- union(i, j)：分别找到 i 和 j 的根节点 root_i 和 root_j，若两者相同则说明 i 和 j 处于同一个集合，若不相同，则将一颗树的根连接到另一棵树上 (通常将树根连接到另一棵树的树根上，即 parent[root_j] = root_i)。

在使用数组实现并查集时，常有一个问题：union 操作中 root_j 应该连接到 i 树的哪里？如果将 root_j 连接到 i 树的某个树叶上，会导致 union 后的树的深度大大增加，进而使得 find() 操作所需要的时间增加。

为了优化这一问题，常常采用将 root_j 与 root_i 相连的方式，这样可以使得 union 后的树深度不会发生太大的增加。但是在此又有一个问题：应该把 root_j 连到 root_i 上，还是应该把 root_i 连到 root_j 上？

为了使得链接后的树深度尽量小，有两种解决方案：加权树 (weighted tree) 和 深度树 (heighted tree)，将权重 (weight，即根下面的节点个数) 或深度 (height，树的层数) 较小的树的根连接到较大的树根上。

总的来看，深度树会比加权树更接近 find() 查找的本质，但缺点是深度树的时间比加权树更加复杂，且两者性能十分接近，几乎不存在性能差距极大的情况，因此采用 加权树 作为实现并查集的抽象结构。

(PS：加权树的引入实际上是改变了 union() 方法，从而实现了对 find() 方法的性能优化。由此可以看出，union() 方法的实现决定了并查集的抽象结构。)

核心思想: 避免出现“细高”的退化树。在合并两个集合时，永远将 小树合并到大树上。这里的“大小”通常指树中节点的数量。
实现规则: 额外记录每个集合的大小。在合并时，比较两个根节点所在树的大小，将小树的根节点连接到大树的根节点上。
本质与效果: 这个简单的规则保证了树的高度 h 和元素总数 n 之间的关系为 h = O(log n)。因为一个节点的深度每增加1，其所在树的大小至少会翻倍。这使得 find 和 union 操作的时间复杂度从 O(n) 优化到了 O(log n)。

核心思想: 在 find 操作的执行过程中，顺手将树“压平”，是一种“随手整理”的优化。
实现规则: 在从一个节点向上查找根节点的路径中，将这条路径上的 所有节点 的父指针 直接指向最终的根节点。
本质与效果: 这是一种 摊还分析 (Amortized Analysis) 意义上的优化。虽然单次 find 可能因为修改指针而稍慢，但它极大地加速了后续对该路径上所有元素的 find 操作。