Disjoint-set data structure: Difference between revisions

Revision as of 07:27, 19 July 2023

Revision as of 18:29, 3 August 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 runs 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. onOn Theoretical Aspects of Computer Science |date=1985 |pages=32-3832–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. onOn Theoretical Aspects of Computer Science |date=1999 |pages=499-506499–506 |doi=10.1145/301250.301383|s2cid=100111 }}</ref>

===Deletion===

The regular implementation as disjoint-set forests does not react favorably to the deletion of elements,

in the sense that the time for <code>Find</code> will not improve as a result of the decrease in the number of elements. However, there exist modern implementations that allow for constant-time deletion and where the time-bound for <code>Find</code> depends on the ''current'' number of elements<ref>{{cite journal |last1=Alstrup |first1=Stephen |last2=Thorup |first2=Mikkel |last3=Gørtz |first3=Inge Li |last4=Rauhe |first4=Theis |last5=Zwick |first5=Uri |title=Union-Find with Constant Time Deletions |journal=ACM Trans. Algorithms |date=2014 |volume=11 |issue=1 |pages=6:1-61–6:28|doi=10.1145/2636922 |s2cid=12767012 }}</ref><ref>{{cite journal |last1=Ben-Amram |first1=Amir M. |last2=Yoffe |first2=Simon |title=A simple and efficient Union-Find-Delete algorithm |journal=Theoretical Computer Science |date=2011 |volume=412 |issue=4-54–5 |pages=487-492487–492|doi=10.1016/j.tcs.2010.11.005 }}</ref>

== Applications ==