java - 加权快速联合查找

Question

我正在上一门算法类(class)，他们会学习加权快速并集查找。我很困惑为什么我们关心树的大小而不是深度？

当我尝试编写代码时，我的代码看起来与提供的解决方案不同。

据我了解，就联合函数 (lg n) 的运行时间而言，树的大小(树中节点的总数)不如树的深度重要，因为它是深度将决定需要多少次查找才能到达节点的根？

谢谢

My code:
public void union(int p, int q) {
    int root_p = root(p);
    int root_q = root(q);

    // If the two trees are not already connected, union them
    if(root_p != root_q) {

        // The two trees aren't connected, check which is deeper
        // Attach the one that is more shallow to the deeper one
        if (depth[root_p] > depth[root_q]) {
            // p is deeper, point q's root to p
            id[root_q] = root_p;
        } else if (depth[root_q] > depth[root_p]) {
            // q is deeper, point p's root to p
            id[root_p] = root_q;
        } else {
            // They are of equal depth, point q's root to p and increment p's depth by 1
            id[root_q] = root_p;
            depth[root_p] += 1;
        }
    }
}


Solution code provided:

public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ) return;

    // make smaller root point to larger one
    if (size[rootP] < size[rootQ]) {
        parent[rootP] = rootQ;
        size[rootQ] += size[rootP];
    }
    else {
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    }
    count--;
}

Answer 1

深度(实际上是高度)与运行时间更直接相关这一点是正确的，但使用其中任何一个都会导致合并和查找的O(log N) 运行时间。

证明很简单——假定当我们开始时(当所有集合不相交时)，每个高度为 h 的根至少有 2^(h-1) 节点，这个不变量由 union 和 find 操作维护。因此，如果一个节点的大小为 n，那么它的高度最多为 floor(log₂(n))+1

所以任何一个都可以。但是，很快你就会了解路径压缩，这使得跟踪根的高度变得困难，但大小仍然可用。届时，您将能够使用类似于高度的 rank，或者继续使用尺寸。同样，任何一个都可以，但我发现尺寸更容易推理，所以我总是使用它。