不相交集森林数据结构的不按等级并集的联合/查找算法

Question

以下是不相交集森林的并集/查找算法的细分 维基百科:

• 准系统不相交的森林...（O(n))
  • ...按等级联合...（现在改进为 O(log(n))
    • ...具有路径压缩（现在改进为 O(a(n)), ， 有效地 O(1))

按等级实现并集需要每个节点保留一个 rank 字段用于比较目的。我的问题是，按等级联合值得这个额外空间吗？如果我跳过按等级并集而只进行路径压缩，会发生什么情况？够好吗？现在的摊余复杂度是多少？

---

进行了评论，暗示按等级联合而不进行路径压缩（摊销 O(log(n) 复杂性）对于大多数实际应用来说已经足够了。这是对的。我要问的是相反的：如果您跳过按等级联合而只进行路径压缩会怎么样？

从某种意义上说，路径压缩是按等级改进联合的额外步骤，这就是为什么可以省略该额外步骤而不会造成灾难性后果。但是按等级并集是路径压缩的必要中间步骤吗？我可以跳过它并直接进行路径压缩吗？或者这会是灾难性的吗？

---

还有人指出，如果没有按等级并集，重复的并集可能会创建类似链表的结构。这意味着单个路径压缩操作可能需要 O(n) 在最坏的情况下。这当然会影响未来的运营，所以我更感兴趣的是在许多运营中摊销时如何发挥作用。

Answer 1

我用谷歌搜索“没有按等级联合”，出现的第二个链接是 这个:

...我们通过对路径压缩的联盟进行分析结束了本节，但没有等级。

具有路径压缩的Union-Find数据架构，但没有按等级过程的联合MIND和N-1链接操作在时间O（（M+n）log n）中

Answer 2

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

IMO，最好跳过路径压缩而不是排名。