8 并查集之路径压缩与按秩合并

在上一篇中，我们介绍了并查集的基本操作，包括初始化、查找和合并。在本篇中，我们将深入讨论两种优化技术：路径压缩和按秩合并。这两者可以显著提高并查集的操作效率，使得在实际应用中能处理更大规模的数据。

路径压缩

路径压缩是一种优化查找操作的技术。在并查集的实现中，当我们执行查找操作时，我们会沿着节点的父指针递归查找根节点。这个过程中，如果我们把经过的每个节点的父指针直接指向根节点，就形成了路径压缩。

方法

在查找函数中，进行路径压缩的实现如下：

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])  # 递归查找同时进行路径压缩
    return parent[x]

示例

假设我们有一个并查集，其中包含以下元素及其初始父指针：

0 -> 1
1 -> 2
2 -> 3
3 -> 4

如果我们从节点 0 开始执行查找，该操作的步骤如下：

1. 查找父节点1
2. 查找父节点2
3. 查找父节点3
4. 查找父节点4

在没有路径压缩的情况下，每次查找都必须完全遍历从 0 到 4 的链。然而，通过路径压缩，我们可以将所有节点 0, 1, 2, 3 的父指针更新为 4，之后的查找将直接返回根节点。

效果

使用路径压缩后，对于大量的查找操作，平均时间复杂度降低到接近 O(1)。

按秩合并

按秩合并是另一种优化技术，用于合并两个集合时选择根节点。 秩可以理解为树的高度，合并时总是将较矮的树连接到较高的树上，从而减少树的高度，使得后续查找操作更高效。

方法

在合并函数中实现按秩合并如下：

def union(parent, rank, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    
    if rootX != rootY:
        if rank[rootX] > rank[rootY]:
            parent[rootY] = rootX
        elif rank[rootX] < rank[rootY]:
            parent[rootX] = rootY
        else:
            parent[rootY] = rootX
            rank[rootX] += 1  # 合并后树的秩增加

示例

考虑以下元素与其秩：

不断合并的过程中可能会出现以下情况：
- 0 和 1 -> 秩(0) = 0, 秩(1) = 0
- 2 和 3 -> 秩(2) = 0, 秩(3) = 0

当我们将 1 合并到 0，并将 3 合并到 2 时，两个树的秩都为 0。根据按秩合并的规则，我们会将 1 的根设为 0，并将 3 的根设为 2。

如果我们继续合并 0 和 2，由于秩相等，将 2 的根设为 0，并将 0 的秩增加到 1。

效果

使用按秩合并后，树的高度不会超过 $\log(n)$，这进一步提高了查找和合并操作的性能。

合并路径压缩与按秩合并

当我们将路径压缩与按秩合并结合使用时，我们能够获得接近线性的效率，具体表现在时间复杂度为 $\alpha(n)$，其中 $\alpha$ 是阿克曼函数的反函数，增长极为缓慢。因此，这种组合方法在处理大量并查集操作时非常高效。

小结

在这一节中，我们深入讨论了路径压缩和按秩合并两种优化方法。合理运用这些技术可以极大提高并查集的性能，尤其是在处理大规模数据时。本篇内容为下一篇关于并查集在网络连接中的应用打下了基础，希望读者能够熟练掌握这两种技巧，以便在实际应用中得心应手。