目录

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

1. 基于 rank 优化的基本概念

在并查集中，合并操作可能导致树高增加，影响查找效率。基础实现随意合并集合，可能退化为链表，查找复杂度变为 O(n)。
基于 rank 的优化通过记录每个集合的“秩（rank）”——树的估计高度，在合并时将较矮的树连接到较高的树根下，从而控制树高，提升性能。

2. 按秩合并的步骤

按秩合并使用“rank”数组记录树的高度估计，具体步骤如下：

  1. 找到根节点：
  • 对两个元素 x 和 y，分别调用 Find 操作找到其根节点 rootX 和 rootY。
  1. 比较秩：
  • 检查 rootX 和 rootY 的秩（rank[rootX] 和 rank[rootY]），初始值为 0。
  1. 合并规则：
  • 如果 rank[rootX] < rank[rootY]：将 rootX 指向 rootY，秩不变。
  • 如果 rank[rootX] > rank[rootY]：将 rootY 指向 rootX，秩不变。
  • 如果 rank[rootX] = rank[rootY]：选择一个作为根，另一指向它，新根的秩加 1。
  1. 更新父指针：
  • 执行合并，更新树的结构。

示例

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

  • Union(1, 2)：
  • rank[1] = 0, 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，rank[1] = 1。

3. 时间复杂度分析

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

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. 参考资料

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