联合查找树上的操作？

Question

有人可以用粗体解释一下答案吗？怎么做到的？

下面是四个联合查找操作的序列（带有加权联合和完全组合） pression) 导致了下面的向上树。最后两次手术是什么？

答案：并集(D,A)、并集(B,C)、并集(D/A、B/C)、查找(B/C)。

Answer 1

使用符号是因为设置 .

让我们应用四个操作：

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).

Union-Find operations on a tree?