[联合查找算法伪代码

Question

我对联合查找算法不了解。

从概念上讲，我知道它是如何工作的。我知道，如果两个项目属于不同的组，那么这两个组将合并为一个。但是，在下面的伪代码中，

if rank[xSet] < rank[ySet]

然后将项目xSet设置为ySet。即，该项目现在属于另一个组。但事实是，组xSet中的所有项目现在也应该属于ySet。这在伪代码中未实现。

我在做什么错？预先感谢。

function UNION(x, y)
    xSet ← FIND(x)
    ySet ← FIND(y)
    if xSet = ySet then
        return False       # Nothing to merge
    else if rank[xSet] < rank[ySet] then
        set[xSet] ← ySet
    else
        set[ySet] ← xSet
        if rank[xSet] = rank[ySet] then
            rank[xSet] ← rank[xSet] + 1
    return True

Answer 1

如果要主动修改集合中每个元素的集合所有权，则并集步骤将有效地花费O（max（#xset，#yset））时间。此外，您甚至可能不会查询刚刚修改了其集合所有权的元素，从而导致所有这些额外的时间都花在了水龙头上。

---

另一方面，如果只更新集合的父元素的所有权，那么此步骤就是O（1）！您不修改所有单个元素就节省了很多时间。接下来，当您必须查找任何项目的所有权时，请遍历父项，直到最终找到没有父项的元素，并且该项的所有者是您最初要查找的项的所有者。] >

这样，您就不会做任何不必要的工作。

---

Bonus：

在遍历父项的过程中，您可以返回并更正遇到的所有父项元素的所有权，并将它们的集合所有权更新为最终值，以便下次，不仅这一步是O（1），但是减少了很多其他查询的运行时间。