Union-find worst cases: the tallest trees, union by rank, path compression and a cost budget

A city's clubs keep merging, and anyone may ask whether two people are now in the same club. A union-find structure keeps each club as a tree of parent pointers: find(x) follows the pointers from $x$ up to the root, and union(a, b) links one root under the other. A find costs one step per pointer it follows, so tall trees are slow.

Three naive unions on 16 elements, and the pointers one find follows.

The two linking rules in parts A and B, for union(a, b) with roots $r_{a}$ of $a$ and $r_{b}$ of $b$ :

Naive: $r_{a}$ becomes a child of $r_{b}$ .
By size: the root of the smaller tree becomes a child of the other's root; on a tie, $r_{a}$ goes under $r_{b}$ .

A tree's height is the most parent steps from any element to its root. In parts A and B there are 16 elements, $0$ to $15$ , and each union is written as two numbers, a b, one per line.

Part C's cost

Your structure keeps everything in two lists the grader gives you, parent and rank, of $n$ cells each. Every read and every write of a cell costs 1. The grader runs four sequences of up to 24,096 operations on $n = 4096$ , built to hurt structures that skip one of the standard ideas. Each sequence's total must stay within $8 \times (operations + n)$ . Every find is checked: it must return an element of the right club, and the same one for the whole club until the next union. Every 97 operations the grader also compares two elements' clubs; those extra finds are not charged to you.

Background: Union-Find.

Part A: naive linking builds a chain

union(0, 1), union(1, 2), ..., union(14, 15): each union hangs the whole tree under one new element, so the tree is a path of height 15. A find on element 0 then follows every pointer. On $n$ elements the same pattern gives height $n - 1$ , and $m$ finds cost $Θ (m n)$ .

Part B: by size, a tree only grows a level by doubling

An element's depth grows only when its root is hung under another root, and by size that only happens when the other tree is at least as large. So each step down doubles the size of the element's tree: an element at depth $d$ is in a tree of at least $2^{d}$ elements, and the height is at most $\log_{2} n$ , which is 4 for 16 elements. To reach it, merge equal sizes: pairs, then pairs of pairs, then pairs of those, then the two halves. The result is a binomial tree.

Part C: union by rank or size, and path compression

Union by size alone keeps every find within $\log_{2} n$ steps, and repeated finds still pay that much every time. Compression alone flattens paths after they are walked, but a bad order of unions keeps building new long paths. With both, $m$ operations cost $O (m α (n))$ in total. On the grader's sequences that was:

structure	cell accesses per operation
union by rank + path compression	4.9 to 6.0
union by size + path halving	4.2 to 4.6
union by rank only	over 8 on "pairs, then pairs of pairs, then finds"
path compression only	over 8 on "random unions and finds"
naive	over 8 within the first sequence

Path halving, where each element skips to its grandparent on the way up, gives the same bound with one pass instead of two.

Going further

Is $α (n)$ real? Yes. Tarjan proved the $O (m α (n))$ bound and showed it is tight for this algorithm. Fredman and Saks proved that any structure for this problem needs $Ω (α (n))$ amortized time per operation in the cell-probe model. That covers every possible structure, not just this one.
Compression without rank costs $O (\log n)$ amortized per operation in the worst case. Tarjan and van Leeuwen analysed all the common variants.
Amortized Analysis has the potential arguments behind these bounds.

References

R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM 22(2), 1975.
R. E. Tarjan, J. van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM 31(2), 1984.
M. L. Fredman, M. E. Saks. The cell probe complexity of dynamic data structures. Proceedings of STOC, 1989.

The Merging Clubs