Disjoint Set / Union-Find
Track connected components, in a forest.
A breathtakingly simple structure: each element points to a "parent"; root elements represent their set. Galler and Fischer's 1964 paper introduced it. Tarjan's 1975 analysis with path compression and union-by-rank proved the amortised cost is O(α(n)) — the inverse Ackermann function, which is < 5 for any imaginable n.
Each element has a parent pointer; the root's parent is itself. Find: walk up to root, optionally compress path on the way down. Union: find both roots, link the smaller-rank tree under the larger.
Kruskal's minimum spanning tree. Equivalence-class problems. Dynamic graph connectivity. Image segmentation. Hadoop's job DAG planner.
Tarjan's analysis is mathematically beautiful — the amortised cost is bounded by α(n), which grows so slowly it never exceeds 4 for any practical input. It's O(1) for all practical purposes, with a proof.