union by rank
When a union-find structure merges two groups, it makes one group's root point to the other's root. The choice of which root becomes the new top matters enormously for the height of the trees. Union by rank is the rule: always attach the root of the shorter tree underneath the root of the taller one. Doing it the wrong way around can stack groups into a tall thin chain; doing it this way keeps the trees short and bushy.
Each root carries a number called its rank, a conservative estimate of the tree's height. To union two trees, compare ranks: the root with smaller rank becomes a child of the root with larger rank, leaving the height unchanged. Only when the two ranks are equal does the surviving root's rank increase by one. This single rule guarantees that a tree whose root has rank r contains at least 2^r nodes — proved by induction, since a rank-r root is formed only by joining two rank-(r-1) trees, each with at least 2^(r-1) nodes. Inverting that, a tree of n nodes has height at most log n, so every Find without any other trick already costs O(log n). 'Union by size,' which compares node counts instead of ranks, gives the same guarantee.
Union by rank is the other half of the fast union-find, complementing path compression. Used together, the two heuristics push the amortized cost per operation all the way down to O(alpha(n)), the inverse Ackermann bound — far better than either alone. The honest details: rank is an upper bound on height, not the exact height, and path compression can leave a node's rank larger than its true depth (ranks are never decreased), but this never breaks the bound because the analysis only uses rank as a ceiling. By itself, union by rank gives O(log n) per operation; the near-constant bound requires pairing it with path compression.
Union a rank-2 tree (>= 4 nodes) with a rank-1 tree (>= 2 nodes): the rank-1 root becomes a child of the rank-2 root, total height stays at the rank-2 tree's, and the merged root keeps rank 2. Had you instead hung the taller tree under the shorter root, the result would be one level deeper for no reason.
Hanging the shorter tree under the taller keeps height at most log n, so Find costs O(log n) even before path compression.
Rank is an upper bound on height, not the exact height; path compression flattens trees without lowering stored ranks, so a node's rank can exceed its real depth. The analysis only relies on rank as a ceiling, so this never invalidates the bound.