Disjoint-set data structure: Difference between revisions

Revision as of 20:17, 4 October 2004

Revision as of 20:26, 4 October 2004

Line 35:

In this naive form, this approach is no better than the linked-list approach, because the tree it creates can be highly unbalanced, but it can be enhanced in two ways.

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[[amortized analysis|amortized]] running-time of O(log ''n'') per '''MakeSet''', '''Union''', or '''Find''' operation. Here are the improved <code>MakeSet</code> and <code>Union</code>:

'''function''' MakeSet(x)

Line 64:

'''return''' root

These two techniques complement each other; applied together, the average[[amortized analysis|amortized]] time per operation is only O(&alpha;(n)), where &alpha;(n) is the inverse of the function ''f''(''n'') = ''A''(''n'',''n''), where ''A'' is the extremely quickly-growing [[Ackermann function]]. Since &alpha;(''n'') is its inverse, it's less than 5 for all remotely practical values of ''n''. Thus, the averageamortized running time per operation is effectively a small constant; we couldn't ask for much better than this.

In fact, we can't get better than this: Fredman and Saks showed in [[1989]] that &Omega;(&alpha;(n)) words must be accessed by ''any'' disjoint-set data structure per operation on average.