加权快速联合查找

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 ^(h-1)个节点，这个不变量由并集和查找操作来维护。因此，如果一个节点的大小为n，那么它的高度最多为Floor(log ₂ (n))+1

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