Sets as rooted trees, one root per set: find walks to the root and union links one root under another. Which way round it links is the whole difference between a depth of 1 and a depth of 11 on twelve elements. Union by rank keeps every height at most log₂ n, by an induction showing a tree of rank r has at least 2ʳ elements; path compression flattens as it searches.
Core ideas
A structure with two operations and two optional rules. The rules look like optimisations and one of them is the difference between a bound and no bound at all.
Each element points at a parent; a root points at itself. find(x) walks up and returns the root, which is the set’s identity, so find(x) = find(y) is the “same set” test. Nothing is stored about the elements and nothing can be enumerated: this structure answers connectivity and refuses every other question, including “what is in this set”.
Linking the taller tree under the shorter one adds a level to the whole thing; linking the shorter under the taller adds none. Do it wrong consistently and the trees become paths. The lab runs a sequence of eleven unions both ways on twelve elements: with the rule the tallest tree has depth 1, without it, depth 11.
Union by rank increases a root’s rank only when two equal-rank trees merge, and then the merged tree has at least twice as many elements. So a rank-r tree has at least 2ʳ elements, and with only n elements no rank exceeds log₂ n. Without the rule the claim is simply false, and the lab shows a depth-11 tree holding 12 elements where 2¹¹ is 2048.
The material
The structure, the rank–height proof, what path compression adds, and the one bound on this page that is stated rather than proved.
A partition of {1, …, n} represented as a forest: each element has a parent pointer, each set is a tree, and the root of a tree is its representative. find(x) follows parent pointers from x to the root. union(x, y) finds both roots and, if they differ, makes one the parent of the other.
The cost of find is the number of pointers walked, which is the depth of x. Everything about the performance of this structure is therefore a statement about how deep the trees get.
The naive version links the root of the first argument under the root of the second. Run union(0,1), union(1,2), …, union(10,11) that way and each union hangs the growing tree under a fresh singleton: the result is a path of twelve nodes. The twelve finds afterwards walk 11 + 10 + … + 0 = 66 pointers, and the deepest find walks 11.
Each root carries a rank, initially 0. On a union, the root of smaller rank is made a child of the root of larger rank. If the two ranks are equal, either becomes the child and the new root’s rank increases by 1.
Rank is an upper bound on height and equals it when path compression is not used. The rule is two comparisons and costs nothing, and the next theorem is what it buys.
Under union by rank, any root of rank r has at least 2ʳ elements in its tree. Consequently no rank exceeds log₂ n, and since rank bounds height, every find walks at most log₂ n pointers.
Induction on r. A rank-0 root is a singleton, and 2⁰ = 1. A root reaches rank r only by merging two roots of rank r − 1, each of which has at least 2ʳ⁻¹ elements by the inductive hypothesis; the merged tree has at least 2ʳ⁻¹ + 2ʳ⁻¹ = 2ʳ. Attaching a lower-rank tree does not change the root’s rank, so it cannot break the claim — it only adds elements. With n elements in total, 2ʳ ≤ n forces r ≤ log₂ n.
Every step of that induction is about the rule. It is the “only by merging two roots of equal rank” clause that supplies the doubling, and the naive union has no such clause. So the bound is not a fact about disjoint-set forests; it is a fact about disjoint-set forests built with union by rank, and the lab makes the difference concrete.
Read the first row as a refutation rather than a slow result. A depth of 11 on twelve elements is not a worse constant; it is the 2ʳ claim failing outright, because there is no rank rule in force to make it true. The lab prints the bound and the set size side by side with the verdict, and the verdict on that row is “no”.
During find(x), after the root is located, set the parent of every node on the path from x directly to the root.
The walk has already visited those nodes, so the rewriting is free up to a constant. Every subsequent find on any of them costs one hop. It changes no set and no root; it only shortens the paths it has just traversed.
On the chain sequence, compression alone brings the total from 66 hops to 21: the first find walks eleven pointers and flattens the entire path, so the remaining eleven finds cost one each. The worst single find is still 11, because the tall tree was built before any find happened — compression repairs, it does not prevent. And the 2ʳ bound still fails on that row, because it is a claim about union by rank and compression is not that.
Pair up, then pair the pairs: union(0,1), union(2,3), … then union(0,2), union(4,6), … and so on. On twelve elements the lab reports 39 hops with neither rule and a tallest tree of depth 4, whose 2ʳ bound of 16 exceeds the twelve elements present — failing again, on a pattern that was not even trying to be bad. With union by rank the tallest rank is 3, the bound is 8, the set holds 12, and it holds. Both rules together bring the hops to 30.
With both rules, a sequence of m operations on n elements costs O(m α(n)), where α is the inverse Ackermann function and is at most 4 for every n that will ever be written down. That bound is stated on this course and not proved: its proof needs machinery no Subject in this library teaches, and the course’s list of what it does not cover says so too.
What is proved here is the log n bound from union by rank alone, by the induction above, and it is the bound every later course quotes when it uses this structure — Kruskal’s algorithm sorts the edges and then does union and find, and the sort dominates a logarithmic union anyway. The near-constant bound is better and is not needed to make the structure worth using, which is the honest reason a course can state it without developing it.
Interactive
Four combinations of two rules, on one sequence
Method
Run it without the rules first. The structure is only interesting once you have seen what it does when the rules are left out.
One arrow per element, roots pointing at themselves. The set is the tree and the name of the set is the root, so “same set” is always two walks and a comparison.
Link the first root under the second every time. On the chain pattern this gives a path, and the depth is one less than the number of elements. This is the baseline the rules are measured against and it is not a straw man: it is what the obvious implementation does.
Link the smaller rank under the larger; on a tie, increase the new root’s rank. Then for the tallest root, compare 2ʳ with the number of elements in its set. The claim is that 2ʳ is at most the set size, and with the rule off it will not be.
Compression does not reduce the worst single find on a tree built before any find happened; it reduces the total over a sequence. Read the hop total for that, and read the worst-find column to see what it did not fix.
Small enough to draw both forests. The unions are (0,1), (1,2), (2,3), (3,4), (4,5) in that order, and then a find on every element.
The only difference between the two columns is which root became the child, and the depth went from 5 to 1. On twelve elements the lab reports the same contrast at scale: 66 hops against 20, and a depth of 11 against 1.
Look at what the failing row actually says. A tree of depth 5 would need 32 elements for the 2ʳ claim to hold and there are 6. That is not a large constant or a slow case — it is the claim being false, because the claim is about union by rank and no rank rule was in force. A bound is a consequence of a rule, and removing the rule removes the bound rather than weakening it.
For a faded rehearsal, run the pairing pattern on twelve elements with each of the four rule combinations. The supplied observation is that pairing is already fairly balanced, so the no-rules depth is 4 rather than 11. Predict whether the 2ʳ bound holds on that row before looking — the rank is 4, the bound is 16, and twelve elements are present — and then say which of the four rows is the one the theorem in this lesson is about.
You should be able to run a union/find sequence keeping the parent pointers explicit, state and apply union by rank, give the 2ʳ induction in full, say what path compression does to a total and what it does not do to a worst case, and separate the bound this course proves from the one it states.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.