Union–find

Union–find maintains an equivalence relation that only ever grows. Each element points to a parent, and following parents from any element reaches the root of its tree, which names the class. find x follows the pointers to the root; union x y finds both roots and makes one point to the other^[1]. It is used wherever equivalences are discovered one at a time: in Kruskal's minimum spanning tree algorithm^[7], in congruence closure, in the unification step of type inference, and in finding connected components.

Without care the trees degenerate into paths and find takes linear time. Two independent heuristics prevent this. Union by rank keeps for each root an upper bound on its tree's height, the rank, and makes the root of lower rank point to the other, so a tree of rank $r$ has at least $2^r$ nodes and every path is $O(\log n)$ long. Path compression makes every node visited by a find point directly at the root, so later finds from those nodes take one step^[3].

(* Disjoint sets over 0 .. n-1. Each element points to a parent; a root
   points to itself and names its set. *)
type t = { parent : int array; rank : int array; by_rank : bool; compress : bool }
 
let steps = ref 0
 
let create ?(by_rank = true) ?(compress = true) n =
  { parent = Array.init n Fun.id; rank = Array.make n 0; by_rank; compress }
 
let rec find u x =
  let p = u.parent.(x) in
  if p = x then x
  else begin
    incr steps;
    let r = find u p in
    if u.compress then u.parent.(x) <- r;  (* path compression *)
    r
  end
 
let union u x y =
  let rx = find u x and ry = find u y in
  if rx <> ry then
    if not u.by_rank then u.parent.(rx) <- ry
    else if u.rank.(rx) < u.rank.(ry) then u.parent.(rx) <- ry
    else if u.rank.(rx) > u.rank.(ry) then u.parent.(ry) <- rx
    else begin u.parent.(ry) <- rx; u.rank.(rx) <- u.rank.(rx) + 1 end
 
let same u x y = find u x = find u y

let n = 2_000
 
(* Union 0-1, 1-2, 2-3, ...: linking without ranks builds one long path.
   Then 100,000 finds of random elements. *)
let run name by_rank compress =
  let u = Uf.create ~by_rank ~compress n in
  Uf.steps := 0;
  for i = 1 to n - 1 do Uf.union u (i - 1) i done;
  Random.init 5;
  for _ = 1 to 100_000 do ignore (Uf.find u (Random.int n)) done;
  Printf.printf "%-22s %11d parent steps\n" name !Uf.steps

1~3 true, 1~7 false, 7~8 true
neither                   99799842 parent steps
path compression            101952 parent steps
union by rank               101950 parent steps
both                        101950 parent steps
random, rank only        2879492 parent steps, deepest node now 8
random, both             1936313 parent steps, deepest node now 4

On the path, either heuristic alone is enough: union by rank never builds it, and path compression flattens it in the first few finds. Together they bound every sequence of operations. On random unions compression halves the maximum depth and saves a third of the steps.

With both heuristics, a sequence of $m$ operations on $n$ elements takes $O(m\alpha (n))$ time, where $\alpha$ is a functional inverse of the Ackermann function^[3][4]. It grows so slowly that

Fredman and Saks proved that this is optimal: any data structure for the problem needs $\Omega (m\alpha (n))$ time in the cell-probe model^[5]. Simpler variants of compression, path halving and path splitting, which make each visited node point to its grandparent, achieve the same bound in a single pass^[4].

Union–find is inherently imperative, since find updates pointers. Conchon and Filliâtre gave a persistent version for OCaml that keeps the same practical efficiency when used linearly, built on persistent arrays that reroot themselves on access^[6].

Galler and Fischer introduced the tree representation in 1964 for handling equivalence declarations in Fortran compilers^[1]. Hopcroft and Ullman proved an $O(m{\log }^{\ast }n)$ bound for union by size with compression in 1973^[2], and Tarjan improved it to the inverse Ackermann bound in 1975^[3]. Tarjan and van Leeuwen analysed the variants of linking and compression in 1984^[4], and Fredman and Saks proved the matching lower bound in 1989^[5].

• Congruence closureCongruence closure is the algorithm that decides whether an equation between terms follows from a set of ground equations, using only the laws of equality and the congruence rule that equal arguments give equal function applications. It maintains equivalence classes of subterms in a union–find structure and, whenever two classes merge, merges any applications of the same function whose arguments have become equal. It runs in O(n log n) time and decides the quantifier-free theory of equality with uninterpreted functions (EUF), which makes it a core theory solver in SMT; the same data structure, the e-graph, underlies equality saturation in compilers.
• Red-black treeA red-black tree is a binary search tree whose nodes are coloured red or black so that no red node has a red child and every path from the root to a leaf passes through the same number of black nodes. The two rules keep the height at most 2 log2(n + 1), so search, insertion and deletion take O(log n) time. Red-black trees are an encoding of 2-3-4 trees as binary trees, and Okasaki's functional version reduces insertion to one rebalancing rule with four cases.

1. [1]B. A. Galler, M. J. Fischer, “An improved equivalence algorithm”, Communications of the ACM 7 (1964).
2. [2]J. E. Hopcroft, J. D. Ullman, “Set merging algorithms”, SIAM Journal on Computing 2 (1973).
3. [3]R. E. Tarjan, “Efficiency of a good but not linear set union algorithm”, Journal of the ACM 22 (1975).
4. [4]R. E. Tarjan, J. van Leeuwen, “Worst-case analysis of set union algorithms”, Journal of the ACM 31 (1984).
5. [5]M. L. Fredman, M. E. Saks, “The cell probe complexity of dynamic data structures”, STOC (1989).
6. [6]S. Conchon, J.-C. Filliâtre, “A persistent union-find data structure”, ML Workshop (2007).
7. [7]J. B. Kruskal, “On the shortest spanning subtree of a graph and the traveling salesman problem”, Proceedings of the AMS 7 (1956).

last updated 1 October 2026