使用不带按秩合并的并查集森林数据结构的并查集/查找算法

Question

这是一个关于维基百科上不相交集合森林的并查集算法的分解：

• 裸奔的不相交集合森林...（O(n)）
  • ... 使用按秩合并...（现在改进到O(log(n))）
    • ...使用路径压缩（现在改进到O(a(n))，实际上是O(1)）

实现按秩合并需要每个节点保持一个rank字段进行比较。我的问题是，按秩合并是否值得这额外的空间？如果我跳过按秩合并，只做路径压缩，会发生什么？现在的平摊复杂度是多少？

---

一个评论认为，在没有路径压缩的情况下，使用按秩合并（平摊O(log(n)复杂度）对于大多数实际应用来说已经足够了。这是正确的。我要问的是反过来：如果您跳过按秩合并，只做路径压缩怎么样？

在某种程度上，路径压缩是改进按秩合并的额外步骤，这就是为什么可以省略该额外步骤而不会产生灾难性后果的原因。但是，按秩合并是否是路径压缩必要的中间步骤？我能跳过它直接进行路径压缩吗，或者那会是灾难性的？

---

还指出，如果没有按秩合并，重复的合并可能会创建类似于链接列表的结构。这意味着单个路径压缩操作在最坏情况下可能需要 O(n) 的时间。当摊销在许多操作中时，这将影响未来的操作，因此我更感兴趣的是它如何发挥作用。

- polygenelubricants

---

我最喜欢的论文是：Yossi Shiloach，Uzi Vishkin：一种O(log n)并行连通性算法。J. Algorithms 3(1)：57-67（1982年）。 - Chad Brewbaker

另一方面，即使未来的单路径压缩操作可能需要最坏情况下的O(n)时间，由于该操作会压缩该路径，因此不会重复发生相同的最坏情况时间 - 至少不会在同一路径或其任何部分上。因此，最坏情况下重复操作的分析可能与最坏情况下单个操作不同，我猜？ - rwong

Answer 1

我在谷歌上搜索了“without union by rank”，第二个出现的链接是这个：

...我们用路径压缩来分析不使用按秩合并的并查集...

使用路径压缩但不使用按秩合并的并查集处理m个查找和n-1个链接操作的时间复杂度为O((m+n)logn)

- jkff

---

这真是个很好的发现！我承认我一开始没有先去谷歌，因为我没想到会有人考虑到这个问题。这意味着每次操作的摊销成本确实是O(log n)，而且不需要额外的空间来跟踪排名！ - polygenelubricants

@polygenelubricants：甚至更酷的技巧是，如果你随机分配父节点而不是按秩合并来源，你仍然可以在不跟踪秩的情况下获得O(an)而不是O(log n)。这只需要额外的1行代码 :) - pathikrit

请问n和m分别是什么？ - Henry

"m 次查找和 n-1 次链接操作" - jkff

Answer 2

路径压缩可以使树结构扁平化。按秩合并有助于合并。假设您跳过了后者。现在，您有一个没有排名信息选择如何合并的森林。潜在地，您现在面临将具有较大深度的树合并到具有较小深度的树中的风险，从而导致不平衡的树结构。在最坏的情况下，您可能会得到一个链表。即使查找的时间复杂度保持不变，您的联合的摊销时间复杂度也会增加。

在我看来，最好跳过路径压缩，但不要跳过秩。

- dirkgently

---

我同意你所说的，但如果有人能进行严格的分析来展示路径压缩在不使用按秩合并时的性能，那会很有帮助。不幸的是，我不熟悉这种分析所涉及的技术。例如，我不知道反阿克曼函数在完整实现中扮演什么角色。 - polygenelubricants