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
您可以在第 21 章的算法导论 3rd 中找到伪代码。
这是具有等级和路径压缩的不相交集森林的伪代码。 从伪代码中我们可以看出，每次并集运算之前，我们都会先求出每个节点的集合数。在路径压缩的 FIND-SET 操作中，x 和 y 的高度将始终变为 2。因为 FIND-SET 之后 x.p 和 y.p 都将指向集合的根。为什么仍然需要按等级联合？
Shihab Shahriar 解决了我的问题，他的回答真是令人印象深刻!
最佳答案
请注意，我们应用 path compression只有当我们执行 find-set操作，当我们执行 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操作时间可能会减少，但关键是我们不想要 O(n)任何find-set的时间手术。因此，对于有多个联合操作并且最后有一个 find-set 的情况。然后操作O(n)如果不使用 union by rank 会浪费时间.
我们同时使用按等级合并和路径压缩，因为我们想降低树的高度并使其小于 log2(n)(n 是不相交集中的元素数)，最终目标就是让树的高度差不多是一棵。
关于algorithm - 路径压缩对于不相交集的森林来说已经足够了，为什么我们需要按等级合并，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49574421/