Union-Find树上的操作？

Question

有人可以请用粗体解释答案吗？它是如何完成的？

下面是四个联合查找操作（带有加权联合和完整com- 按下）的序列，导致了以下up-tree。最后两个操作是什么？ （D，A），Union（B，C），Union（D/A，B/C），Find（B/C）。

答案：

Answer 1

记号被使用，因为套的。

让我们运用四个运算：

Union(D,A)导致以下三种：

D 
/
A 

Union(B,C)导致以下三种：

B 
/
C 

现在Union(D/A,B/C)意味着由于d和A属于同一套，无所谓冷杉t参数是，它可以是D或它可以是A。同样因为B和C属于同一组，所以第二个参数是什么也没关系，它可以是B或者它可以是C,结果将是相同的。

其结果将是第三次手术后：

D 
/\ 
A B 
     \ 
     C 

现在因为压缩也是允许的，在Find(C)操作会导致树：

D 
    /|\ 
A B C 

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

正确答案

四个运算的正确顺序是：

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