Disjoint-set data structure: Difference between revisions

Revision as of 10:20, 13 July 2023

Revision as of 07:27, 19 July 2023

Line 198:

The precise analysis of the performance of a disjoint-set forest is somewhat intricate. However, there is a much simpler analysis that proves that the amortized time for any {{mvar|m}} <code>Find</code> or <code>Union</code> operations on a disjoint-set forest containing {{mvar|n}} objects is {{math|''O''(mlog^* ''n'')}}, where {{math|log^*}} denotes the [[iterated logarithm]].<ref>[[Raimund Seidel]], Micha Sharir. "Top-down analysis of path compression", SIAM J. Comput. 34(3):515–525, 2005</ref><ref>{{cite journal|last1=Tarjan|first1=Robert Endre|year=1975|title=Efficiency of a Good But Not Linear Set Union Algorithm|url=http://portal.acm.org/citation.cfm?id=321884|journal=Journal of the ACM|volume=22| issue=2| pages=215–225 | doi=10.1145/321879.321884|hdl=1813/5942|s2cid=11105749|hdl-access=free}}</ref><ref>{{cite journal| last1=Hopcroft|first1=J. E.| last2=Ullman|first2=J. D.|year=1973|title=Set Merging Algorithms|journal=SIAM Journal on Computing|volume=2| issue=4| pages=294–303 | doi=10.1137/0202024}}</ref><ref>[[Robert E. Tarjan]] and [[Jan van Leeuwen]]. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.</ref>

{{anchor|increasing rank lemma}}Lemma 1: As the [[Disjoint-set data structure#Disjoint-set forests|find function]] follows the path along to the root, the rank of node it encounters is increasing.

{{math proof| claim that as Find and Union operations are applied to the data set, this fact remains true over time. Initially when each node is the root of its own tree, it's trivially true. The only case when the rank of a node might be changed is when the [[Disjoint-set data structure#Disjoint-set forests|Union by Rank]] operation is applied. In this case, a tree with smaller rank will be attached to a tree with greater rank, rather than vice versa. And during the find operation, all nodes visited along the path will be attached to the root, which has larger rank than its children, so this operation won't change this fact either.}}

{{anchor|min subtree size lemma}}Lemma 2: A node {{mvar|u}} which is root of a subtree with rank {{mvar|r}} has at least <math>2^r</math> nodes.

{{math proof| Initially when each node is the root of its own tree, it's trivially true. Assume that a node {{mvar|u}} with rank {{mvar|r}} has at least {{math|2^''r''}} nodes. Then when two trees with rank {{mvar|r}} are merged using the operation [[Disjoint-set data structure#Disjoint-set forests|Union by Rank]], a tree with rank {{math|''r'' + 1}} results, the root of which has at least <math>2^r + 2^r = 2^{r + 1}</math> nodes.}}

[[File:ProofOflogstarnRank.jpg|center]]

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. 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>