Disjoint-set data structure: Difference between revisions

Revision as of 13:15, 11 July 2023

Revision as of 10:20, 13 July 2023

Line 246:

===Better worst-case time per operation===

The worst-case time of the <code>Find</code> operation in trees with '''Union by rank''' or '''Union by weight''' is <math>\Theta(\log n)</math> (i.e., it is <math>O(\log n)</math> and this bound is tight).

In 1985, N. Blum gave an implementation of the operations that does not use path compression, but compresses trees during <math>union</math>. His implementation runruns in <math>O(\log n / \log\log n)</math> time per operation<ref>{{cite journal |last1=Blum |first1=Norbert |title=On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem |journal=2nd Symp. on Theoretical Aspects of Computer Science |date=1985 |pages=32-38}}</ref>, and thus in comparison with Galler and Fischer's structure it has a better worst-case time per operation, but inferior amortized time. In 1999, Alstrup et al. gave a structure that has optimal worst-case

time <math>O(\log n / \log\log n)</math> together with inverse-Ackermann amortized time.<ref>{{cite journal |last1=Alstrup |first1=Stephen |last2=Ben-Amram |first2=Amir M. |last3=Rauhe |first3=Theis |title=Worst-Case and Amortised Optimality in Union-Find |journal=31st Symp. on Theoretical Aspects of Computer Science |date=1999 |pages=499-506 |doi=10.1145/301250.301383}}</ref>