Content deleted Content added
A reference and a note |
A bit more explanation and another link |
||
Line 22:
The first way, called ''union by rank'', is to always attach the smaller tree to the root of the larger tree, rather than vice versa. To evaluate which tree is larger, we use a simple heuristic called ''rank'': one-element trees have a rank of zero, and whenever two trees of the same rank are unioned together, the result has one greater rank. Just applying this technique alone yields an average running-time of O(log ''n'') per '''Make-Set''', '''Union''', or '''Find''' operation.
The second way, called ''path compression'', is a way of flattening the structure of the tree whenever we use '''Find''' on it. The idea is that each node we visit on our way to a root node may as well be attached directly to the root node; they all share the same representative. To effect this, we make one traversal up to the root node, to find out what it is, and then make another traversal, making this root node the immediate parent of all nodes along the path. The resulting tree is much flatter, speeding up future operations not only on these elements but on those referencing them, directly or indirectly.
These two techniques complement each other; applied together, the average time per operation is only O(α(n)), where α(n) is the inverse of the function ''f''(''n'') = ''A''(''n'',''n''), where ''A'' is the extremely quickly-growing [[Ackermann function]]. Since α(''n'') is its inverse, it's less than 5 for all remotely practical values of ''n''. Thus, the average running time per operation is effectively a small constant; we couldn't ask for much better than this.
Line 51:
* [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
| |||