Disjoint-set data structure: Difference between revisions

Revision as of 12:21, 11 July 2023

Revision as of 12:32, 11 July 2023

Line 241:

Therefore, <math>T = T_1 + T_2 + T_3 = O(m \log^*n).</math>

== Other structures ==

The worst-case time of the '''find'''

== Applications ==

Line 251 ⟶ 255:

Note that the regular implementation as disjoint-set forests does not allow the deletion of edges, even without path compression or the rank heuristic. However, there exist modern implementations that allow for constant-time deletion.<ref>{{Cite book |url=https://www.worldcat.org/oclc/262681795 |title=Automata, languages and programming : 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005 ; proceedings |date=2005 |publisher=Springer |others=Luís. Caires, European Association for Theoretical Computer Science |isbn=978-3-540-31691-6 |___location=Berlin |oclc=262681795}}</ref>{{vague citation|date=May 2023}}

Sharir and Agarwal report connections between the worst-case behavior of disjoint-sets and the length of [[Davenport–Schinzel sequence|Davenport–Schinzel sequences]], a combinatorial structure from computational geometry.<ref name="Sharir1995">{{cite book|first1=M.|last1=Sharir|first2=P.|last2=Agarwal|title=Davenport-Schinzel sequences and their geometric applications|title-link= Davenport–Schinzel Sequences and Their Geometric Applications|publisher=Cambridge University Press|year=1995}}</ref>

The [[Hoshen–Kopelman_algorithm| Hoshen-Kopelman algorithm]] uses a Union-Find in the algorithm.