并查集快速合并

目录

1. 快速合并的基本概念
2. 按秩合并的步骤
3. 时间复杂度分析
4. 代码示例（伪代码）
5. 参考资料

1. 快速合并的基本概念

在并查集中，合并（Union）操作的目标是将两个集合合并为一个。基础实现中，合并直接将一个集合的根指向另一个集合的根，可能导致树高增加，最坏情况下退化为链表，查找复杂度变为 O(n)。
快速合并通过按秩合并优化，总是将较矮的树连接到较高的树根下，从而控制树高，保持查找效率。

2. 按秩合并的步骤

按秩合并使用“秩（rank）”表示树的估计高度，具体步骤如下：

1. 找到根节点：

• 对两个元素 x 和 y，分别调用 Find 操作找到其根节点 rootX 和 rootY。

1. 比较秩：

• 检查 rootX 和 rootY 的秩（rank），秩通常初始化为 0。

1. 合并规则：

• 如果 rank[rootX] < rank[rootY]：将 rootX 指向 rootY，秩不变。
• 如果 rank[rootX] > rank[rootY]：将 rootY 指向 rootX，秩不变。
• 如果 rank[rootX] = rank[rootY]：任意选择一个作为根，另一指向它，新根的秩加 1。

1. 更新父指针：

• 执行合并，更新树的结构。

示例

初始：1 和 2 独立，rank[1] = 0, rank[2] = 0。

• Union(1, 2)：
• rank[1] = rank[2] = 0，相等。
• 设 1 为根，parent[2] = 1，rank[1] = 1。
• 结果：1 ← 2，rank[1] = 1, rank[2] = 0。
• Union(1, 3)：
• rank[1] = 1, rank[3] = 0。
• parent[3] = 1，rank 不变。
• 结果：1 ← 2, 1 ← 3。

3. 时间复杂度分析

• 单次合并：
• 未优化：O(h)，h 为树高，最差 O(n)。
• 按秩合并后：O(1)（不含查找时间）。
• 查找影响：
• 树高被限制为 O(log n)，因为每次合并时秩相等才增 1。
• 总复杂度（m 次操作，n 个元素）：
• 仅按秩合并：O(m * log n)。
• 结合路径压缩：O(m * α(n))，α(n) 是阿克曼函数反函数，近似常数。
• 空间复杂度：O(n)，需存储父节点和秩数组。

4. 代码示例（伪代码）

class UnionFind:
    parent[]      // 父节点数组
    rank[]        // 秩数组
    size          // 元素总数

    // 初始化
    function init(n):
        size = n
        for i = 0 to n-1:
            parent[i] = i
            rank[i] = 0

    // 查找（简单版）
    function find(x):
        while parent[x] != x:
            x = parent[x]
        return x

    // 合并（按秩）
    function union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            if rank[rootX] < rank[rootY]:
                parent[rootX] = rootY
            else if rank[rootX] > rank[rootY]:
                parent[rootY] = rootX
            else:
                parent[rootY] = rootX
                rank[rootX] = rank[rootX] + 1

5. 参考资料

• Wikipedia: Disjoint-set Data Structure – Union by Rank
• GeeksforGeeks: Union by Rank
• Baeldung: Union by Rank in Union-Find

如果你需要结合路径压缩的完整优化版本，或特定语言实现，请告诉我！