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?

  • $\begingroup$ I don't care if the constant overhead or the exponent on the log is so large that it's impractical $\endgroup$
    – dspyz
    Apr 1 '16 at 19:30
  • 1
    $\begingroup$ Doesn't using union by rank (without path compression) together with the fat node technique automatically give you this? $\endgroup$ Apr 2 '16 at 0:32
  • $\begingroup$ 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. $\endgroup$
    – dspyz
    Apr 2 '16 at 1:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.