目录

  1. 快速查找的基本概念
  2. 路径压缩的步骤
  3. 时间复杂度分析
  4. 代码示例（伪代码）
  5. 参考资料

1. 快速查找的基本概念

在并查集中，查找（Find）操作的目标是找到元素所在集合的代表元素（根节点）。基础实现中，查找需要从元素沿父节点指针遍历到根，最坏情况下时间复杂度为 O(n)。
快速查找通过路径压缩优化，将查找路径上的所有节点直接指向根节点，从而减少后续查找的时间。

2. 路径压缩的步骤

路径压缩在查找过程中执行，具体步骤如下：

  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)。

3. 时间复杂度分析

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

4. 代码示例（伪代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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

5. 参考资料

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