algorithm - 在线性时间内打印出不相交集数据结构中的节点

Question

我正在尝试在 Cormen 等人的算法简介中做这个与 Disjoin Set 数据结构有关的练习:

Suppose that we wish to add the operation PRINT-SET(x), which is given a node x and prints all the members of x's set, in any order. Show how we can add just a single attribute to each node in a disjoint-set forest so that PRINT-SET(x) takes time linear in the number of members of x's set, and the asymptotic running times of the other operations are unchanged. Assume that we can print each member of the set in O(1) time.

现在，我很确定所需的属性是一个尾指针，因此它可以跟踪子项。

由于不相交的集合结构已经有一个父属性，find-set(x) 可以很容易地打印出一个方向的节点。但是现在，有了尾指针，让我们也转向另一个方向。

但是，我不确定如何编写算法来执行此操作。如果有人可以用伪代码帮助我，我将不胜感激。

Answer 1

每个节点都应该有一个 next 指针，指向它所在集合中的下一个节点。集合中的节点应该形成一个循环链表。

当第一次创建单例集时，节点的 next 指针指向它自己。

当您将集合与节点 X 合并并与节点 Y 合并时(并且您已经通过标准化集合代表来检查这些集合是否不同)，您合并循环链表，你可以通过简单地交换 X.next 和 Y.next 来实现；所以这是一个O(1) 操作。

要列出包含节点X的集合中的所有元素，遍历从X开始的循环链表。