19

以下是wikipedia上不相交集森林的联合/查找算法的细分：

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

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

做了一个评论，暗示没有路径压缩（摊销O(log(n)复杂性）的按等级联合对于大多数实际应用来说已经足够了。这是对的。我要问的是另一种方式：如果您按等级跳过联合并且只进行路径压缩怎么办？

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

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

4

2 回答 2

7

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

...我们以联合分析结束本节——使用路径压缩但没有按等级联合...

具有路径压缩但没有按等级联合的联合查找数据结构在时间 O((m+n) log n) 中处理 m 查找和 n-1 个链接操作

于 2010-02-24T14:29:30.810 回答
3

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

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

于 2010-02-24T03:12:05.837 回答