path compression

A union-find (disjoint-set) structure keeps a collection of items partitioned into groups, and answers 'which group is x in?' by walking up a tree of parent pointers to the group's root. If those trees get tall, each query is slow because the walk is long. Path compression is a tiny, almost free trick applied during a find: after you walk from x up to its root r, you go back and re-point every node on that path directly at r, so future finds on any of them take one hop.

Concretely, Find(x) follows parent pointers x -> p -> q -> ... -> r until it reaches the root r (the node that is its own parent), and then makes a second pass setting the parent of x and of every node along the way to r. The path the search just paid to traverse gets flattened, so the structure self-improves: work spent now is never wasted, because it permanently shortens future paths. This is a perfect setting for amortized analysis — a single Find can still be slow if it climbs a tall path, but it leaves the tree shorter for everyone after. Path compression alone (without union by rank) already brings the amortized cost of a Find down to about O(log n), and that improvement is precisely the future paths it has flattened paying back.

Path compression is half of the famous near-constant union-find. Combined with union by rank (always hang the shorter tree under the taller), the amortized cost per operation drops to O(alpha(n)), where alpha is the inverse Ackermann function — effectively a small constant for any conceivable input. Two honest points: first, the analysis is subtle precisely because the structure keeps changing itself, which is why it needs the potential method rather than a simple sum; second, path compression by itself, without rank, gives O(log n) amortized, not O(alpha(n)) — you need both heuristics together for the inverse-Ackermann bound.