Content deleted Content added
Line 88:
While the ideas used in disjoint-set forests have long been familiar, [[Robert Tarjan]] was the first to prove the upper bound (and a restricted version of the lower bound) in terms of the inverse Ackermann function. Until this time the best bound on the time per operation, proven by Hopcroft and Ullman, was O(log<sup>*</sup> n), the [[iterated logarithm]] of n, another slowly-growing function (but not quite as slow as the inverse Ackermann function). Tarjan and van Leeuwen also developed one-pass '''Find''' algorithms that are more efficient in practice. The algorithm was made well-known by the popular textbook ''Introduction to Algorithms'', listed in the references.
== External links ==
* [http://research.compaq.com/SRC/zeus/unionfind.html Compaq Research: Zeus: Animation of Union-Find Algorithms]
* [http://www.cs.unm.edu/~rlpm/499/uf.html Java applet: A Graphical Union-Find Implementation], by Rory L. P. McGuire
* [http://www.cs.rutgers.edu/~chvatal/notes/uf.html The abstract data type Union-Find ], a simple C implementation by Vašek Chvátal
* ''[http://citeseer.ist.psu.edu/anderson94waitfree.html Wait-free Parallel Algorithms for the Union-Find Problem]'', a [[1994]] paper by Richard J. Anderson and Heather Woll describing a parallelized version of Union-Find that never needs to block
* [http://gont.pld.org.pl/ Gont], a little-known programming language with Union-Find in its standard library
[[Category:Data structures]]
[[Category:Algorithms]]
== Notes ==
| |||