java - 为什么在 Weighted QuickUnion 中联合和查找操作期间的数组访问次数据说是 lg(N) 的顺序？

Question

快速联合算法的通用代码。

public class QuickUnionUF
{
 private int[] id;
 public QuickUnionUF(int N)
 {
   id = new int[N];
   for (int i = 0; i < N; i++) id[i] = i;
 }
 private int root(int i)
 {
   while (i != id[i]) i = id[i];
   return i;
 }
 public boolean connected(int p, int q)
 {
   return root(p) == root(q);
 }
 public void union(int p, int q)
 {
   int i = root(p);
   int j = root(q);
   id[i] = j;
 }
}

这里很明显，对于像“初始化”、“联合”和“查找是否连接”这样的联合操作，数组访问的次数将是 N 的数量级(从代码中可以很清楚地看出)。

然而，我的书声称，如果我们将 QuickUnion 修改为 Weighted QuickUnion，那么数组访问的数量将变为 lg(N) 的数量级。但我无法从代码中看出如何。

Weighted QuickUnion 所做的唯一更改是 union() 函数中的部分，如下所示:

 int i = root(p);
 int j = root(q);
 if (i == j) return;
 if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
 else { id[j] = i; sz[i] += sz[j]; } 

这里我们维护额外的数组sz[i]计算以 i 为根的树中对象的数量。

但是在这里，我看不到 union 的数组访问次数是 lg(N) 阶的。数组访问必须是 N 阶，因为我们必须调用 root() 方法两次。另外 lg(N) 的顺序如何，即使对于“查找是否连接”操作也是如此？

我对他们如何获得 lg(N) 感到困惑。有人可以解释一下吗？

Answer 1

在未修改的版本中，您获得线性依赖性，因为到父级的链接可以是任意的。因此，在最坏的情况下，您最终可能会得到一个长列表(即，如果您位于列表的末尾，则必须遍历所有其他元素)。

修改(按等级合并)旨在通过使较小的子树成为较大子树的根的子树来生成较浅的树。这种启发式方法使树更加平衡，即从任何叶子到其根的路径长度变为 O(log n)。请记住，具有 k 个节点的完整二叉树的高度是 O(log k)。

更正式的证明，请引用现有文献。

附加说明:我提到过按等级联合只是一种启发式方法。理想情况下，您会希望根据两个子树的高度做出决定。但是，跟踪高度非常困难。这就是为什么您通常使用子树的大小，它与其高度相关。