Data Structure-7-Disjoint Sets

#CS225

Disjoint Sets

等价关系 (Equivalence Relation)

这是理解不相交集的一个数学前提。

定义: 一个在集合 $S$ 上的二元关系 $R$ 如果满足以下三个性质，则称为等价关系：
1. 自反性 (Reflexive): 对于所有 $s \in S$, $(s, s) \in R$ (每个元素都与自身相关)。
2. 对称性 (Symmetric): 对于所有 $s, t \in S$, 如果 $(s, t) \in R$，则 $(t, s) \in R$ (如果 s 与 t 相关，则 t 与 s 相关)。
3. 传递性 (Transitive): 对于所有 $s, t, u \in S$, 如果 $(s, t) \in R$ 且 $(t, u) \in R$，则 $(s, u) \in R$ (如果 s 与 t 相关，t 与 u 相关，则 s 与 u 相关)。
等价类 (Equivalence Class): 等价关系会将集合 $S$ 划分成若干个互不相交的子集，每个子集称为一个等价类。同一个等价类中的所有元素都互相等价。
- 例子：如果关系 $R$ 定义为“两个人 $s$ 和 $t$ 有相同的最喜欢的选项 (A, B, C, D, E, F 中的一个)”，那么所有喜欢 A 的人组成一个等价类，所有喜欢 B 的人组成另一个等价类，以此类推。
- $[s]_R$ 表示元素 $s$ 所在的等价类。例如，如果学生 3 和学生 4 都最喜欢 B，那么 $[3]_R = [4]_R$。

不相交集 (Disjoint Sets)

不相交集数据结构，也常被称为 并查集 (Union-Find)，用于维护一个包含 $n$ 个元素的集合，并将这些元素划分成若干个不相交的子集。

核心概念:
- 集合中的每个元素都只属于一个特定的子集。
- 每个子集都有一个 代表元 (Representative Member)，用来唯一标识这个子集。

主要操作 (Operations):

makeSet(x): 创建一个新的集合，其中只包含元素 x。x 成为这个新集合的代表元。
find(x): 返回包含元素 x 的集合的代表元。通过比较 find(x) 和 find(y) 的结果，可以判断 x 和 y 是否在同一个集合中。
- 例如，find(4) == find(8) 意味着元素 4 和元素 8 属于同一个集合。

union(x, y): 合并包含元素 x 和元素 y 的两个集合。如果它们已经在同一个集合中，则不进行任何操作。通常，合并操作是基于它们的代表元进行的。

示例

if (find(elem1) != find(elem2)){
// If the two elements are not in the set
// Union their sets through the representative element
union (find(elem1), find(elem2));
}

不相交集抽象数据类型 (Disjoint Sets ADT):
- 维护一个集合 $S = {s_0, s_1, …, s_k}$。
- 每个子集有一个代表元。
- API (接口):
  - void makeSet(const T & t);
  - void union(const T & k1, const T & k2); (更准确地，这里应该是 unionSets，参数是两个集合中的任意元素，或者直接是两个集合的代表元)
  - T & find(const T & k);

实现方案 (Implementations)

实现1:朴素数组表示

思路: 使用一个数组，数组的索引代表元素，数组的值代表该元素所在集合的代表元。
- 例如: 元素: 0 1 2 3 4 5 6 7 代表元: 0 0 2 3 0 3 3 2
  - 集合1: {0, 1, 4} (代表元是 0)
  - 集合2: {2, 7} (代表元是 2)
  - 集合3: {3, 5, 6} (代表元是 3)
操作复杂度:
- Find(k): 直接返回数组在索引 k 处的值。时间复杂度 $O(1)$ (Slide 27)。
  - 例如 Find(4) 返回 0。
- Union(k1, k2): (假设 k1 和 k2 是两个集合的代表元) 要合并代表元为 k1 和 k2 的两个集合，例如将所有代表元为 k2 的元素的代表元改为 k1。这需要遍历整个数组。时间复杂度 $O(N)$，其中 $N$ 是元素的总数。
  - 例如 Union(0, 2): 将所有代表元为 2 的元素 (即元素 2 和 7) 的代表元改为 0。数组变为: 0 0 0 3 0 3 3 0

这种实现中 Union 操作太慢，不实用。

实现2: Uptrees

这是更高效和常用的实现方式。

思路:
- 仍然使用数组，数组的索引是 键 (key) (即元素本身)。
- 数组的值 (value) 的含义：
  - 如果值是 -1 (或者其他特殊负数，表示大小或高度时)，则表示当前索引是其所在集合的代表元 (即树的根节点)。
  - 如果值是非负数，则表示当前索引的 父节点的索引 (index of the parent)。
- 这样，每个集合都表示为一个树形结构，树的根节点就是这个集合的代表元。所有边都从子节点指向父节点，因此称为 “UpTree”。
初始化 (makeSet):
- 开始时，每个元素都是一个独立的集合，即每个元素都是一个根。
- 数组 arr: 索引: 0 1 2 3 值: -1 -1 -1 -1 (所有元素都是根)
union(root1, root2) 操作 (简单版本):
- 假设 root1 和 root2 是两个不同集合的根。
- 使一个根成为另一个根的子节点。例如，arr[root2] = root1 (使 root2 指向 root1)。
- 例子: union(1, 2) (这里假设 1 和 2 是根) 初始: arr = [-1, -1, -1, -1] (元素 0, 1, 2, 3) find(1) 返回 1, find(2) 返回 2。执行 arr[2] = 1 (让 2 的父节点是 1)。 arr 变为 [-1, -1, 1, -1] 可视化: 0, 3 还是根；1 也是根，2 指向 1。
```
1
2
3
4

  0   1   3
      ^
      |
      2
```
- 例子: union(0, 3) arr 当前为 [-1, -1, 1, -1] find(0) 返回 0, find(3) 返回 3。执行 arr[0] = 3 (让 0 的父节点是 3)。 arr 变为 [3, -1, 1, -1] 可视化:
```
1
2
3
4

  3   1
  ^   ^
  |   |
  0   2
```
- 例子: union(3, 1) (此时 3 和 1 都是根) arr 当前为 [3, -1, 1, -1] find(3) 返回 3, find(1) 返回 1。执行 arr[3] = 1 (让 3 的父节点是 1)。 arr 变为 [3, -1, 1, 1] 可视化:
```
1
2
3
4
5
6
7

      1
    / | \
   /  |  \
  2   3   (原来1的孩子)
      ^
      |
      0   (原来3的孩子)
```
  此时根是 1，元素 0,2,3 都最终指向 1。

find(i) 操作:

从索引 i 开始，沿着父节点指针向上查找，直到找到一个值为负数 (或特定标记) 的节点，该节点即为根。

C++ 实现:

int DisjointSets::find(int i) {
  if ( s[i] < 0 ) { // s[i] < 0 表示 i 是根节点
    return i;
  } else {
    return find( s[i] ); // 递归查找父节点的根
  }
}

运行时间 (Running time): 在最坏情况下 (例如，树退化成一个链表)，find 操作可能需要 $O(N)$ 时间。
理想的 UpTree (Ideal UpTree): 树应该尽可能地“扁平”或“茂密”，这样从任何节点到根的路径都很短。目标是 $O(1)$ 或接近 $O(1)$ 的查找时间。

优化 UpTrees (Optimizations for UpTrees)

朴素的 union 操作 (简单地将一个根指向另一个根) 可能导致树变得很高，从而使得 find 操作变慢。因此需要优化 union 操作。

1. 按高度/秩合并 (Union by Height / Union by Rank)

思路: 在合并两个集合时，总是将较矮的树的根连接到较高的树的根上。
记录高度: 每个根节点需要存储其对应树的高度。通常，我们将高度存为负值在数组中 (例如，如果根 r 的树高度为 h，则 arr[r] = -h，但为了区分根，通常是 - (height + 1) 或者用一个单独的数组来存高度)。
- 当合并两个高度相同的树时，新树的高度会增加 1。
- 当合并两个高度不同的树时，新树的高度等于原来较高的那个树的高度。
效果: 这种策略能保证树的高度最多为 $O(\log N)$ 。
幻灯片中的例子:
- 树 T1 (根7): 高度 $h=2$。arr[7] 可能存 -3 (表示高度2)。
- 树 T2 (根4): 高度 $h=3$。arr[4] 可能存 -4 (表示高度3)。
- union(7, 4): 因为 T1 (高度2) 比 T2 (高度3) 矮，所以将 T1 的根 7 指向 T2 的根 4。arr[7] = 4。合并后树的根仍然是 4，高度仍然是 3。arr[4] 保持 -4。
- 如果两个树高度相同，例如都是 $h$，合并后新根的高度变为 $h+1$。例如，arr[new_root] 变为 -( (h+1) + 1 )。

2. 按大小合并 (Union by Size)

思路: 在合并两个集合时，总是将元素较少的树的根连接到元素较多的树的根上。
记录大小: 每个根节点需要存储其对应树中元素的数量 (即集合的大小)。通常，我们将大小存为负值在数组中 (例如，如果根 r 的集合大小为 size，则 arr[r] = -size)。
效果: 这种策略也能保证树的高度最多为 $O(\log N)$ (Slide 82)。
幻灯片中的例子:
- 树 T1 (根7): 大小 $ T_1 =8$。arr[7] 存 -8。
- 树 T2 (根4): 大小 $ T_2 =4$。arr[4] 存 -4。
- union(7, 4): 因为 T2 (大小4) 比 T1 (大小8) 小，所以将 T2 的根 4 指向 T1 的根 7。arr[4] = 7。合并后树的根是 7，新大小是 $8+4=12$。arr[7] 更新为 -12。
C++ 实现 unionBySize:
- 函数原型: void DisjointSets::unionBySize(int root1, int root2)
  - 前提: root1 和 root2 必须是它们各自集合的根。这意味着在调用 unionBySize 之前，已经对原始元素执行了 find 操作。
- 数组 arr_: arr_[i] 如果为负，表示 i 是根，且 -arr_[i] 是该集合的大小。
- 步骤:
  1. int newSize = arr_[root1] + arr_[root2]; (因为大小是负数存储的，所以直接相加)。
  2. 比较 arr_[root1] 和 arr_[root2]。值越小 (即负得越多)，表示集合越大。
  3. 如果 arr_[root1] < arr_[root2] (即 root1 对应的集合更大)：
    - arr_[root2] = root1; (将 root2 指向 root1)
    - arr_[root1] = newSize; (更新 root1 的大小)
  4. 否则 (即 root2 对应的集合更大或一样大)：
    - arr_[root1] = root2; (将 root1 指向 root2)
    - arr_[root2] = newSize; (更新 root2 的大小)
- 时间复杂度: 由于 root1 和 root2 已经是根，这个函数本身的操作是 $O(1)$ 。但是，调用它的 union 操作还需要两次 find，所以总的 union 操作时间取决于 find。

3. 路径压缩 (Path Compression)

这是对 find 操作的优化，与 union by size/height 配合使用效果极佳。

思路: 在执行 find(i) 操作，从 i 向上走到根的路径上，将路径上的所有节点直接连接到根节点。这样可以使树变得更扁平，从而加速后续的 find 操作。
例子:
- 假设执行 find(4)。路径是 $4 \to 2 \to 7 \to 9 \to 10$ (10是根)。
- 在找到根 10 之后，路径压缩会修改指针，使得 4, 2, 7, 9 都直接指向 10。
- arr[4] = 10, arr[2] = 10, arr[7] = 10, arr[9] = 10。

C++ 实现 find (带路径压缩):

int DisjointSets::find(int i) {
  if ( arr_[i] < 0 ) { // i 是根节点
    return i;
  } else {
    // 递归查找父节点的根，并将 arr_[i] 直接指向最终的根
    arr_[i] = find( arr_[i] );
    return arr_[i];
  }
}

效果: 路径压缩并不会改变树的实际高度或秩 (对于 Union by Height/Rank 来说)，但它能显著降低平均查找时间。

时间复杂度分析 (Time Complexity Analysis)

1. 迭代对数函数 (Iterated Logarithm Function)

符号: $log^* n$ (读作 “log star n”)
定义: $log^* n$ 是需要对 $n$ 反复取对数 (通常以 2 为底) 多少次，结果才会小于或等于 1。 $$ log^* n = \begin{cases} 0 & \text{if } n \le 1 \\ 1 + log^*(\log n) & \text{if } n > 1 \end{cases} $$
例子: $log^*(2^{65536})$
1. $2^{65536}$ (原始数)
2. $\log(2^{65536}) = 65536$ (第一次取 log)
3. $\log(65536) = \log(2^{16}) = 16$ (第二次取 log)
4. $\log(16) = \log(2^4) = 4$ (第三次取 log)
5. $\log(4) = \log(2^2) = 2$ (第四次取 log)
6. $\log(2) = 1$ (第五次取 log, 结果 $\le 1$) 所以，$log^*(2^{65536}) = 5$。
$log^* n$ 是一个增长极其缓慢的函数。对于所有在宇宙中可观测到的原子数量（大约 $10^{80}$），$log^* (10^{80})$ 也只是一个非常小的数字 (大约是 5)。在实践中，可以认为它几乎是一个常数 (通常 $\le 5$)。

2. 结合优化的并查集性能

当同时使用 智能合并 (Smart Unions) (即 Union by Size 或 Union by Height) 和 路径压缩 (Path Compression) 时：
- 任何 $m$ 次 union 或 find 操作序列的总时间复杂度是 $O(m \cdot \alpha(N))$，其中 $N$ 是元素数量，$m$ 是操作次数。
- $\alpha(N)$ 是 反阿克曼函数 (Inverse Ackermann function)，它的增长比 $log^* N$ 还要慢，对于所有实际的 $N$ 值，$\alpha(N)$ 不会超过 5。
- 因此，单次操作的 均摊时间复杂度 (Amortized Time Complexity) 几乎是常数，即 $O(\alpha(N))$ 或近似为 $O(log^* N)$。
- 幻灯片中写作 $O(m \cdot \text{lg}^* N)$，这在实践中非常接近 $O(m)$。

UpTree 总结

UpTree 用数组实现。
代表一个集合 (或者说，一个 UpTree 的森林代表了一系列不相交集合/等价类)。
通过路径压缩和按大小/秩合并，查找代表元的操作接近 $O(1)$ (均摊)。
一个缺点: 不能快速找到集合中的所有元素。如果需要这个功能，需要额外的数据结构或遍历。

其他数据结构回顾

Array (数组):
- Sorted Array (有序数组): 查找 $O(\log N)$ (二分查找)，插入/删除 $O(N)$。
- Unsorted Array (无序数组): 查找 $O(N)$，端点插入/删除 $O(1)$ (均摊，考虑resize)。
- Stacks (栈 - LIFO): 基于数组实现，操作 $O(1)$。
- Queues (队列 - FIFO): 基于数组实现 (循环数组)，操作 $O(1)$。
- Hashing (哈希表): 平均 $O(1)$ 查找/插入/删除。
- Heaps (堆): 通常用于 Priority Queues (优先队列)。插入/删除最高优先级 $O(\log N)$。
- UpTrees / Disjoint Sets (不相交集)。
List (链表):
- Doubly Linked List (双向链表): 插入/删除 (如果知道节点) $O(1)$，查找 $O(N)$。
- Skip List (跳表): 平均 $O(\log N)$ 查找/插入/删除。
- Trees (树):
  - BTree (B树): 用于磁盘存储，多路查找树。
  - Binary Tree (二叉树): 包括二叉搜索树 (BST)。
  - Huffman Encoding (霍夫曼编码): 用于数据压缩的树。
  - kd-Tree (k维树): 用于多维空间数据查找。
  - AVL Tree (AVL树): 自平衡二叉搜索树，操作 $O(\log N)$。
Graphs (图): 广义的连接关系结构。