不相交集森林数据结构的不按等级并集的联合/查找算法
以下是 wikipedia 上不相交集合森林的并集/查找算法的详细信息：
- Barebone disjoint-设置森林... (
O(n))- ...按等级并集...（现在改进为
O(log(n)）- ...使用路径压缩（现已改进为
O(a(n))，实际上O(1)）
- ...使用路径压缩（现已改进为
- ...按等级并集...（现在改进为
按等级实现并集需要每个节点保留一个 rank 字段用于比较目的。我的问题是，按等级联合值得这个额外空间吗？如果我跳过按等级并集而只进行路径压缩，会发生什么情况？够好吗？现在的摊余复杂度是多少？
有评论表明，按等级联合而不进行路径压缩（摊销 O(log(n) 复杂度）对于大多数实际应用来说就足够了。这是正确的。我要问的是另一种方式周围：如果您跳过按等级并仅进行路径压缩，会怎样？
从某种意义上说，路径压缩是改进按等级并的额外步骤，这就是为什么可以省略该额外步骤而不会产生灾难性的后果。路径压缩的必要中间步骤？我可以跳过它并直接进行路径压缩吗？
还是有人指出，如果没有按等级并集，重复的并集可能会创建类似链表的结构。在最坏的情况下，单个路径压缩操作可能需要O(n)，这当然会影响未来的操作，所以我更感兴趣的是当分摊到许多操作时，它会如何发挥作用。
Here's a breakdown on the union/find algorithm for disjoint set forests on wikipedia:
- Barebone disjoint-set forests... (
O(n))- ... with union by rank ... (now improved to
O(log(n))- ... with path compression (now improved to
O(a(n)), effectivelyO(1))
- ... with path compression (now improved to
- ... with union by rank ... (now improved to
Implementing union by rank necessitates that each node keeps a rank field for comparison purposes. My question is, is union by rank worth this additional space? What happens if I skip union by rank and just do path compression instead? Is it good enough? What is the amortized complexity now?
A comment is made that implies that union by rank without path compression (amortized O(log(n) complexity) is sufficient for most practical application. This is correct. What I'm asking is the other way around: what if you skip union by rank and ONLY do path compression instead?
In a sense, path compression is an extra step to improve union by rank, and that's why that extra step can be omitted without disastrous consequence. But is union by rank a necessary intermediate step to path compression? Can I skip it and go straight to path compression, or will that be catastrophic?
It was also pointed out that without union by rank, repeated unions could create a linked-list like structure. This means that a single path compression operation could take O(n) in the worst case. This would of course affect future operations, so how this plays out when amortized over many operations is what I'm more interested in.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我用谷歌搜索“没有按等级联合”，出现的第二个链接是 这个：
I googled for "without union by rank" and the second link that came up was this one:
路径压缩使树结构扁平化。按等级联合有助于合并。假设您跳过后者。所以现在，你有一个没有排名信息的森林来选择如何合并。现在，您可能面临将深度较大的树合并为深度较小的树的风险，从而导致树结构不平衡。在最坏的情况下，您可能会得到一个链表。即使“查找”的摊余时间复杂度保持不变，您的 Union 的摊余时间复杂度也会增加。
IMO，最好跳过路径压缩而不是排名。
Path compression flattens the tree structure. Union by rank helps to merge. Assume that you skip the latter. So now, you have a forest with no rank information to choose how to merge. Potentially, you now run the risk of merging a tree with a larger depth to one with a smaller depth -- leading to an unbalanced tree structure. In the worst case, you may end up with a linked list. Your Union's amortized time complexity increases even if that for Find remains the same.
IMO, It'd be better to skip path compression but not rank.