加权快速联合查找

Question

我正在上一门算法课程，其中讨论了加权快速联合查找。我很困惑为什么我们关心树的大小而不是深度？

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

根据我的理解，当涉及到并集函数（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&nbsp;(h-1)个节点，这个不变量由并集和查找操作来维护。因此，如果一个节点的大小为n，那么它的高度最多为Floor(log&nbsp;2&nbsp;(n))+1所以任何一个都可以。但是，很快您就会了解路径压缩，这使得跟踪根的高度变得困难，但大小仍然可用。那时，您将能够使用“rank”（类似于“height”），或者继续使用“size”。同样，任何一个都可以，但我发现尺寸更容易推理，所以我总是使用它。