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章。
这是具有等级和路径压缩的不相交森林的伪代码。从伪代码中，我们可以看到，在联合操作之前的每次，我们都会首先找到每个节点的设置编号。在带有路径压缩的发现集操作中，X和Y的高度将始终变为2。因为X.P和Y.P都会在Find-Set之后指向集合的根。为什么仍然需要按等级的联盟？
Shihab Shahriar解决了我的问题，他的答案确实令人印象深刻！
请注意，我们仅在执行find-set操作时才应用path compression，并且在执行两组的union时无法应用路径压缩。
在联合等级中，我们要照顾一个事实，即树的根部较小(或较少的深度/高度(被指向具有较高等级的树的根(或更深的深度/高度(。这确保代表集合的树永远不会偏斜。
执行等级联合的一个示例：
depth=1,n=2 depth=0,n=1 depth=1,n=3
O U O = O
/ /
O O O
如果我们没有按等级执行联合，那么这棵树可能会变成这样的东西：
depth=1,n=2 depth=0,n=1 depth=2,n=3
O U O = O
/ /
O O
/
O
即高度增加。
您可以进行摊销分析并计算find-set的时间复杂性，当应用级别时，您会发现时间永远不会超过O(log2(n))。
因此，如果您不按等级执行联合，则find-set操作将花费O(D(时间(d代表树的深度(，在最坏的情况下，d可以成为n(集合中的元素数(。因此，对于find-set操作，时间复杂性将首次成为O(n)。但是，对于下一步的find-set操作，时间可能会减少，但要点是我们不希望任何find-set操作的O(n)时间。因此，对于有多个工会操作的情况，到最后，有一个find-set操作，如果您不使用union by rank，则会消耗O(n)时间。
我们同时将联合按等级和路径压缩一起使用，因为我们想降低树的高度并使其少于log2(n((n是脱节集中的元素数(，这是最终目标是要使树的高度几乎为1。
是的， x和 y的深度将为2，但这并不意味着根的高度已经改变。
请注意，我们实际上永远不会降低任何根的等级。假设等级4的根有10个叶子节点，即10个节点在此特定集中有3个边缘。现在，通过路径压缩，您可能已经将这10至2的深度之一提升为x和y。但是仍然有9个剩下的根，root仍然是4。将其他9个节点的深度转到5。这就是为什么除了路径压缩之外我们仍然需要等级的原因。
现在，如果以某种方式以某种方式将所有这10个叶子节点提升到深度2，我们应该降低根级以反映其适当的高度，但是这样做的额外复杂性似乎并不值得。