路径压缩对于不相交的森林就足够了，为什么我们需要按等级联合

Question

MAKE-SET(x?
    x.p = x
    x.rank = 0

UNION(x, y)
     LINK(FIND-SET(x),FIND-SET(y))

LINK(x, y)
    if x.rank > y.rank
        y.p = x
    else 
        x.p = y
        if x.rand == y.rank
            y.rank = y.rank +1

The FIND-SET procedure with path compression is quite simple:
FIND-SET(x)
    if x != x.p
        x.p = FIND-SET(x.p)
    return x.p

您可以在《算法导论》第 3章第 21 章中找到伪代码。

这是具有秩和路径压缩的不相交集森林的伪代码。从伪代码中我们可以看出，每次union操作之前，我们都会先找到每个节点的集合号。在路径压缩的 FIND-SET 操作中，x 和 y 的高度将始终只有 2。因为在 FIND-SET 之后 xp 和 yp 都将指向集合的根。为什么仍然需要按等级联合？

---

Shihab Shahriar 解决了我的问题，他的回答令人印象深刻！

Answer 1

x是的，和的深度y将为 2，但这并不意味着根的高度发生了变化。

请注意，我们实际上从未降低任何根的等级。假设等级 4 的根有 10 个叶子节点，即在该特定集合中 10 个节点相距 3 个边。现在，通过路径压缩，您可能已将这 10 个路径之一提升为深度 2，如x和y此处。但是还剩下 9 个，根的等级仍然是 4。现在，如果我们要将这个集合与另一个等级为 1 的集合链接起来，我们当然不希望当前的根成为该新集合的子集合，因为它会将其他 9 个节点的深度变为 5。这就是为什么除了路径压缩之外我们仍然需要排名。

现在，如果以某种方式将所有这 10 个叶节点提升到深度 2，我们应该减少根的等级以反映其适当的高度，但这样做所增加的复杂性似乎不值得这么麻烦。