algorithm - 加权快速联合解释

Question

我需要帮助来理解有关加权快速联合的问题给出的解释:

Which of the following id[] array(s) could be the result of running the weighted quick union algorithm on a set of 10 items? Check all that apply.

Recall that our weighted quick union algorithm uses union by size (number of nodes) (and not union by height).

Incorrect: 9 1 7 3 4 9 6 7 8 9
Explanation: 9-5 7-2 5-0

Incorrect: 2 2 2 2 5 1 2 3 1 2
Explanation: 2-9 3-7 9-3 5-4 0-2 1-8 8-4 4-9 8-6

Correct: 9 9 3 4 9 4 9 9 4 2
Explanation: The id[] array contains a cycle: 2->3->4->9->2

Correct: 0 2 3 0 0 2 2 9 3 0
Explanation: Size of tree rooted at parent of 2 < twice the size of tree rooted at 2

Correct: 0 4 6 7 4 1 5 1 7 3
Explanation: Height of forest = 4 > lg N = lg(10)

• 我怎么知道前两个问题所示的实际联合操作？
• 我是否必须查看每个元素以确定是否存在循环？
• 我怎么知道一棵树的大小？ (BTW 第四题给出的解释对我来说毫无意义)
• 我怎么知道森林的高度？

Answer 1

你没有给出完整的上下文，但我会尝试根据我对加权联合的了解来回答。

Do I have to look at every element to figure out if there is a cycle?

没有。那会破坏快速联合的目的。一个循环表示并集操作没有正确执行。而且任何时候都不应该有循环。

How do I know the size of a tree?

最初所有树的大小都是 1。在 union 操作中，我们将被连接的 2 棵树的大小相加。我们通过数组跟踪大小(比如 SZ[])。给定树的大小在数组中的根偏移处更新 (SZ[root(i)])。

How do I know the height of a forest?

那也必须被追踪。最初所有树的高度都是 1。当您加入 2 棵树时 - 假设 A & B，您将 A 的根作为新根。然后连接树的高度将为 max(A.height, B.height+1)。