使用 "Path Halving" 对不相交集进行 Find() 操作

Question

根据 Disjoint-set_data_structure，在 Union 部分，我在理解路径减半方法的实现时遇到了问题。

 function Find(x)
   while x.parent ≠ x
     x.parent := x.parent.parent
     x := x.parent
   return x

我的第一次迭代看起来像这样：

第一次迭代后，x.parent 和 x 指向同一个节点（这不应该发生）。我需要有关此函数正确流程和迭代的帮助

我对该函数的第 3 行和第 4 行以及“路径减半使路径上的每个其他节点都指向其祖父节点”感到困惑。

任何帮助将不胜感激，谢谢！

Answer 1

算法如下：从节点 x 开始，让 x 指向它的祖父节点，然后移动到祖父节点本身，继续直到找到根节点，因为根节点的父节点就是根节点本身.

看图片，你实际上是减半集合，将其转换为二叉树（这不是正确的二叉树，但它可以表示为二叉树）。

假设我们有这样一个集合：

8->7->6->5->4->3->2->1->0

其中箭头表示父级（例如 8->7 = 8 的父级是 7）

假设我们调用 Find(8)

第一次迭代：

x = 8
8.parent = 7

8.parent = 8.parent.parent = 7.parent = 6
x = 8.parent = 7.parent = 6

第二次迭代：

x = 6
6.parent = 5

6.parent = 6.parent.parent = 5.parent = 4
x = 6.parent = 5.parent = 4

等等...

Find() operation for disjoint sets using "Path Halving"