algorithm - 联合查找树上的操作？

Question

有人可以用粗体解释答案吗？它是怎么做的？

下面是四个联合查找操作的序列（带有加权联合和完全压缩），它们导致了以下向上树。最后两次操作是什么？

答案：Union(D,A)，Union(B,C)，Union(D/A,B/C)，Find(B/C)。

Answer 1

使用该符号是因为sets。

让我们应用四个操作：

Union(D,A)导致以下树：

   D
  /
 A

Union(B,C)导致以下树：

   B
  /
 C

现在Union(D/A,B/C)意味着因为D 和 A 属于同一个集合，所以第一个参数是什么并不重要，它可以是D或它可以是A。同样因为B 和 C 属于同一个集合，所以无论第二个参数是什么，它可以是B或它可以是C，结果都是一样的。

结果将在第三次操作之后：

   D
  / \
 A   B
      \
       C

现在因为也允许压缩，所以该Find(C)操作将生成树：

   D
  /|\ 
 A B C

如果第四个操作是Find(B)，树将保持不变，因为当我们在查找操作之后应用压缩时，我们使路径中遇到的所有节点都成为根的直接子节点，但是由于我们不会遇到C，我们将不能直接成为C的子级D，因为它在最终树中。

正确答案

四个操作的正确顺序是：

Union(D,A), Union(B,C), Union(D/A,B/C),Find(C).