Card 04/ 07
Union by Rank and Path Compression
Attach the shorter tree under the taller, and point every visited node at the root.
Union-find stays fast only while its trees stay flat, and two optimisations keep them flat: union by rank, which decides which root goes under which, and path compression, which flattens every path find walks. This card covers what each one does to the height of a tree, why the two together bring the cost per operation down to O(α(n)) amortised, and why either one alone is weaker.
In union-find each item stores a parent, and the item that is its own parent is the root of its group's tree. find(x) follows parents to the root, so its cost is the height of the tree, the number of parent steps from the deepest item to the root. Without help, a run of 1,024 unions, union(i, i + 1), built one chain of height 1,023.
Union by rank gives every root a rank, an upper bound on its tree's height that starts at 0. union links the root of lower rank under the root of higher rank, and only when the ranks are equal does the surviving root's rank grow by one. A tree can then grow taller only when two trees of equal rank meet, so a tree of height h holds at least 2^h items, and no tree is taller than log₂ n. With union by rank, the same unions gave height 1, and merging equal trees in pairs, the worst order for height, reached exactly 10, which is log₂ 1,024.
Path compression changes find: after reaching the root, it sets the parent of every item it passed through to the root itself, so the next find from any of them takes one step. The diagram shows a chain of five items before and after one find(0).
Before, the array read 1 2 3 4 4, height 4; after the one find it read 4 4 4 4 4, height 1, as the run printed.
The table sets the four combinations side by side for n items.
| Optimisation | Worst tree height | Cost per operation |
|---|---|---|
| None | n - 1 | O(n) |
| Union by rank only | log₂ n | O(log n) |
| Path compression only | n - 1, until a find flattens it | O(log n) amortised |
| Both | log₂ n, and flattened by every find | O(α(n)) amortised |
Amortised means averaged over a long sequence: one find may still be slow, but m operations together cost at most m times the bound. α(n) is the inverse Ackermann function, which grows so slowly that it is at most 4 for any n that fits in memory. Robert Tarjan proved the bound for the two optimisations together in 1975, and Tarjan and Jan van Leeuwen showed in 1984 that path compression alone gives O(log n) amortised, not O(α(n)).
Path compression alone does not earn this bound: without rank, a bad order of unions keeps building tall trees for later finds to flatten. Use both, at the price of one rank array.
← → move through sections and cards