2.1.1. 父指针树¶

父指针表示最常用于维护一个 不相交集合 的集合。 两个不相交集合没有共同的成员（它们的交集为空）。 不相交集合的集合把一些对象划分开，使得每个对象恰好属于其中 一个不相交集合。 我们希望支持两种基本操作：

1. 判断两个对象是否在同一个集合中（FIND 操作），以及

2. 把两个集合合并在一起。

由于两个被合并的集合联合在一起，合并操作被称为 合并 ， 而判断两个对象是否在同一集合中、然后合并这些集合的整个过程 则称为 合并/查找 。

为了实现 UNION/FIND，我们用一棵单独的一般树来表示每个不相交集合。 如果两个对象在同一棵树中，它们就在同一个不相交集合中。 树的每个结点（根结点除外）都恰好有一个父结点。 因此，每个结点表示它所需的空间都相同。 对象集合通常存储在一个数组中，数组的每个元素对应一个对象， 每个元素存储该对象的值（或一个指向该对象的指针）。 这些对象也对应各棵不相交树中的结点（每个不相交集合一棵树）， 因此我们还在数组中随每个对象一起存储其父结点值。 那些是其所在树根的结点存储一个适当的标记。 注意，这种表示意味着用单个数组来实现一个树的集合。 这使得用 UNION 操作把树合并在一起变得容易。

下面是父指针树和 UNION/FIND 过程的一个实现。

// General Tree implementation for UNION/FIND
public class ParPtrTree {
  private int[] array;     // Node array

  ParPtrTree(int size) {
    array = new int[size]; // Create node array
    for (int i=0; i<size; i++) {
      array[i] = -1;       // Each node is its own root to start
    }
  }

  // Merge two subtrees if they are different
  public void UNION(int a, int b) {
    int root1 = FIND(a);     // Find root of node a
    int root2 = FIND(b);     // Find root of node b
    if (root1 != root2) {          // Merge two trees
      array[root1] = root2;
    }
  }

  // Return the root of curr's tree
  public int FIND(int curr) {
    while (array[curr] != -1) {
      curr = array[curr];
    }
    return curr; // Now at root
  }
}

ParPtrTree 类有一个数组，其中每个数组位置对应某个集合中的一个对象。 每个数组元素存储其父结点的数组下标。 有两个要实现的主要方法。 方法 UNION 把两个集合合并在一起，其中每个集合对应一棵树。 方法 FIND 用于为一个结点找到最终根。

使用 UNION/FIND 操作的应用程序应当存储一个含 \(n\) 个对象的集合， 其中每个对象被赋予 0 到 \(n-1\) 范围内的唯一一个下标。 这些下标指向数组中对应的父指针。 类 ParPtrTree 创建并初始化 UNION/FIND 数组， 方法 UNION 和 FIND 以数组下标作为输入。

2.1.2. 等价类¶

考虑把集合的成员划分到称为 等价类 的 不相交子集中的问题。 回忆一下， 等价关系 是 自反的 、 对称的 和 传递的 的。 因此，如果对象 \(A\) 和 \(B\) 等价，对象 \(B\) 和 \(C\) 等价，那么我们必须能够识别出对象 \(A\) 和 \(C\) 也等价。 在这种表示中，由于 \(A\) 和 \(B\) 等价，它们必定在同一棵树中。 \(B\) 和 \(C\) 同理。 我们能够识别出 \(A\) 和 \(C\) 等价，因为它们也必定在同一棵树中。

不相交集合以及表示等价关系有许多实际用途。 例如，考虑这个有十个结点的图，结点标记为 \(A\) 到 \(J\) 。

注意，对于结点 \(A\) 到 \(I\) ，存在某种边序列把这些结点中 的任意一对连接起来，但结点 \(J\) 与其余结点断开。 这样的图可以用来表示连接，例如电路板上元件之间的导线， 或者城市之间的道路。 如果图的任意两个结点之间存在一条路径，我们就可以认为它们等价。 因此，结点 \(A\) 、 \(H\) 和 \(E\) 会被认为是等价的， 而 \(J\) 与任何其他结点都不等价。 图中一个等价（连通）边的子集称为 连通分量 。 目标是把这些对象快速分类到与连通分量相对应的不相交集合中。

UNION/FIND 的另一个用途出现在 Kruskal 算法 中， 它用于计算 图 的 最小代价生成树 。 该算法试图选出仍能连接图中所有结点的最廉价边子集。 它的做法是按从短到长的顺序处理图中的所有边， 只有当一条边所连接的两个结点之间尚不存在某种边序列时， 才把这条边加入连接子集。

UNION/FIND 算法的输入通常是一系列等价对。 在连通分量这个例子中，等价对就只是图中的边集合。 一个等价对可能表示对象 \(C\) 与对象 \(A\) 等价。 如果是这样， \(C\) 和 \(A\) 就被放入同一个子集。 如果后面的某个等价关系把 \(A\) 和 \(B\) 联系起来， 那么由蕴含关系可知 \(C\) 也与 \(B\) 等价。 因此，一个等价对可能使两个子集合并，而其中每个子集都包含若干对象。

用 UNION/FIND 算法可以高效地管理等价类。 初始时，每个对象都是它自己那棵树的根。 处理一个等价对的方法是，对其中两个对象分别调用 FIND ， 检查它们是否在同一棵树中。 如果它们的根相同，则无需做任何改动， 因为这些对象已经在同一个等价类中。 否则，应当用 UNION 方法把这两个等价类合并。

父指针表示对可以共享同一个父结点的结点数目没有任何限制。 为了使等价处理尽可能高效，每个结点到其所在树的根的距离应当尽可能小。 因此，在合并两个等价类时，我们希望使树的高度保持很小。 理想情况下，每棵树的所有结点都直接指向根。 要始终做到这一点需要太多额外处理，得不偿失， 所以我们只能退而求其次，尽量接近这一目标。

2.1.3. 加权合并¶

降低高度的一种低成本方法是，巧妙地处理两棵树的连接方式。 一种简单的技术称为 加权合并规则 ， 它把结点较少的树接到结点较多的树上， 方法是让较小树的根指向较大树的根。 这将把树的总深度限制为 \(O(\log n)\) ， 因为只存在于较小树中的结点深度现在会增加一， 而合并后树中最深结点的深度最多只比合并前的最深结点深一。 因此，合并后树中的结点总数至少是较小子树中结点数的两倍。 于是，在处理 \(n\) 个等价关系时，任何结点的深度最多增加 \(\log n\) 次（因为深度每增加一次，都必然伴随着树的规模 至少翻倍）。

下面是使用加权合并时 UNION 方法的一个实现。

  public void UNION(int a, int b) {
    int root1 = FIND(a);     // Find root of node a
    int root2 = FIND(b);     // Find root of node b
    if (root1 != root2) {          // Merge with weighted union
      if (weights[root2] > weights[root1]) {
        array[root1] = root2;
        weights[root2] += weights[root1];
      } else {
        array[root2] = root1;
        weights[root1] += weights[root2];
      }
    }
  }

下面的幻灯片演示了使用加权合并的一系列 UNION 操作。

Settings

Saving...
Server Error
Resubmit

2.1.4. 路径压缩¶

加权合并规则有助于把树的深度降到最小，但我们还能做得更好。 路径压缩 是一种往往会生成极浅树的方法。 路径压缩在为一个给定结点 \(X\) 寻找根的过程中进行。 把这个根称为 \(R\) 。 路径压缩会把从 \(X\) 到 \(R\) 这条路径上每个结点的父结点 都重置为直接指向 \(R\) 。 实现时可以首先找到 \(R\) 。 然后沿着从 \(X\) 到 \(R\) 的路径再走一趟， 把遇到的每个结点的父结点字段赋值为 \(R\) 。 另一种做法是实现如下的递归算法。 这个版本的 FIND 不仅返回当前结点的根， 还会让当前结点的所有祖先都指向根。

  // Return the root of curr's tree with path compression
  public int FIND(int curr) {
    if (array[curr] == -1) return curr; // At root
    array[curr] = FIND(array[curr]);
    return array[curr];
  }

下面的幻灯片用上一个例子中的最后一步演示路径压缩。

Settings

Saving...
Server Error
Resubmit

路径压缩使每次 FIND 操作的开销非常接近常数。

要更精确地说明"非常接近常数"是什么意思： 对 \(n\) 个结点执行 \(n\) 次 FIND 操作时， 路径压缩的开销（与用于连接集合的加权合并规则结合使用时） 大约是 \(\Theta(n \log^* n)\) 。 记号 \(\log^* n\) 表示在 \(n \leq 1\) 之前必须对 \(n\) 取对数的次数。 例如， \(\log^* 65536\) 等于 4，因为 \(\log 65536 = 16, \log 16 = 4, \log 4 = 2\) ，最后 \(\log 2 = 1\) 。 因此， \(\log^* n\) 增长得 非常 慢， 所以对 \(n\) 次 FIND 操作这一系列而言，开销非常接近 \(n\) 。

注意，这并不意味着处理 \(n\) 个等价对后得到的树必定具有 \(\Theta(\log^* n)\) 的深度。 人们可以设计出一系列等价操作，使得到的树具有 \(\Theta(\log n)\) 的深度。 然而，这样一系列等价操作中的许多等价关系只会查看被合并树的根， 所需的处理时间很少。 \(n\) 次操作所需的 总 处理时间是 \(\Theta(n \log^* n)\) ，从而每次等价操作的时间接近常数。 这是 平摊分析 的一个例子。

表达式 \(\log^* n\) 与阿克曼函数的反函数密切相关。