联合/查找算法，不依赖于不相交森林数据结构的联合 [英] Union/find algorithm without union by rank for disjoint-set forests data structure

问题描述

以下是维基百科上不相交的设置森林的联合/查找算法的细目：

• Barebone disjoint-set forest ...（ O（n））
  
  
  
  
  • ...按照排序...（现在改为 O（log（n） ）
    
    
    
    
    • ...使用路径压缩（现在改为 O（a（n））有效地 O（1））
    
    
  
  

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

---

发表评论意味着没有路径压缩的排序（摊销 O（log（n）复杂性）是s适用于大多数实际应用。这是对的。我所要求的是相反的方式：如果你按顺序跳过联合，只做路径压缩，而不是做路径压缩？

从某种意义上说，路径压缩是一个额外的步骤通过等级提高联盟，这就是为什么额外的步骤可以省略而没有灾难性的后果。但是通过排列的联合是路径压缩的必要中间步骤？我可以跳过它直接进行路径压缩，还是会是灾难性的？

---

还指出，重复工会可以创建一个类似链接的结构。这意味着在最坏的情况下，单路径压缩操作可能需要 O（n）。这当然会影响未来的运营，所以在多次运营中进行摊销时，如何发挥作用就是我更感兴趣的。

解决方案

p>我在谷歌搜索没有联盟排名，第二个链接是这一个：

< blockquote>

...我们用
分析关联本节，使用$ $ $ $ $ $ $ $ $ $ $ $ $ $ $％

工作查找数据结构，路径为
压缩，但没有按位排列
处理m find和n-1链接
操作在时间O （m + n）log 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)), effectively O(1))

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.

解决方案

I googled for "without union by rank" and the second link that came up was this one:

...We close this section with an analysis of union–find with path compression but without union by rank...

The union-find datastructure with path compression but without union by rank processes m find and n-1 link operations in time O((m+n) log n)

这篇关于联合/查找算法，不依赖于不相交森林数据结构的联合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！