<p>In this paper <a href="https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf" rel="nofollow">https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf</a>, they claim to have a practically fast persistent union-find data structure for most use-cases, but it's still not polylogarithmic in the worst case (the worst case being, I have two variants which I alternately update between); only in a backtracking search.</p>

<p>Are there any implementations of a persistent union find datastructure which guarantee amortized polylogarithmic time complexity per operation regardless of how it's used?</p>

CC BY-SA 3.0
2016-04-01T19:30:34.213Z
I don't care if the constant overhead or the exponent on the log is so large that it's impractical
dspyz
CC BY-SA 3.0
2016-04-02T00:32:57.963Z
Doesn't using union by rank (without path compression) together with the fat node technique automatically give you this?
David Eppstein
CC BY-SA 3.0
2016-04-02T01:20:56.953Z
Oh, yeah.  I guess you're right.  I always assumed path compression was necessary for an efficient union-find data structure.  It didn't even occur to me that union by rank might be sufficient.
dspyz
<ds.data-structures><time-complexity><functional-programming>
Best Asymptotic Complexity for Persistent Union Find
dspyz
# Best Asymptotic Complexity for Persistent Union Find

(Asked by: username_0 on 2016-04-01)

In this paper <https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf>, they claim to have a practically fast persistent union-find data structure for most use-cases, but it's still not polylogarithmic in the worst case (the worst case being, I have two variants which I alternately update between); only in a backtracking search.

Are there any implementations of a persistent union find datastructure which guarantee amortized polylogarithmic time complexity per operation regardless of how it's used?

**Tags:** ds.data-structures, time-complexity, functional-programming
> **Comments:**
> **username_0**: I don't care if the constant overhead or the exponent on the log is so large that it's impractical  
> **username_1**: Doesn't using union by rank (without path compression) together with the fat node technique automatically give you this?  
> **username_0**: Oh, yeah.  I guess you're right.  I always assumed path compression was necessary for an efficient union-find data structure.  It didn't even occur to me that union by rank might be sufficient.  

---

## 0 answers

