Disjoint-Set Union (Union–Find)

Bernard A. Galler & Michael J. Fischer, 1964

Introduced alongside the first asymptotic analyses of set merging structures, disjoint-set forests pair union by rank with path compression so every find short-circuit future traversals while ranks bound tree height. This exhibit staggers merges on six labeled vertices, flashes competing roots during unions, sketches directed parent arcs, displays rank superscripts at roots, and finishes with path compression flattening deep finds—each beat rendered in subdued stone, pewter teal, gallery gold accents, and softened azure.