并查集路径压缩

目录

1. 路径压缩的步骤
2. 时间复杂度分析
3. 代码示例（伪代码）
4. 参考资料

1. 路径压缩的步骤

路径压缩在查找（Find）操作中执行，通过将查找路径上的所有节点直接指向根节点来优化后续查找效率。具体步骤如下：

1. 找到根节点：

• 从目标元素 x 开始，沿父节点指针向上遍历，直到找到根节点（parent[root] = root）。

1. 压缩路径：

• 将路径上的每个节点（包括 x）的父指针直接指向根节点。

1. 返回根节点：

• 返回根节点作为集合代表。

示例

初始树：1 ← 2 ← 3 ← 4

• Find(4)：
• 遍历：4 → 3 → 2 → 1，找到根 1。
• 压缩：将 4, 3, 2 的父节点设为 1。
• 结果：1 ← 2, 1 ← 3, 1 ← 4。
• 下次 Find(4)：直接返回 1，O(1)。

2. 时间复杂度分析

• 单次查找：
• 未优化：O(h)，h 为树高，最差 O(n)。
• 路径压缩后：均摊接近 O(1)。
• 总复杂度（m 次操作，n 个元素）：
• 仅路径压缩：O(m * log n)。
• 结合按秩合并：O(m * α(n))，α(n) 是阿克曼函数的反函数，实际近似常数。
• 空间复杂度：O(n)，仅需存储父节点数组。

3. 代码示例（伪代码）

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

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

    // 查找（带路径压缩）
    function find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])    // 递归压缩路径
        return parent[x]

    // 合并（简单版）
    function union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            parent[rootX] = rootY

4. 参考资料

• Wikipedia: Disjoint-set Data Structure – Path Compression
• GeeksforGeeks: Union-Find with Path Compression
• Baeldung: Path Compression in Union-Find

如果你需要结合按秩合并的完整优化版本，或特定语言实现，请告诉我！