The Parent Pointer Learns a Shortcut

A union-find structure keeps track of a partition:

which items are known to belong together?

It supports two ordinary questions:

find(x)       -> which representative names x's set?
union(x, y)   -> merge the two sets

That sounds too small to deserve a famous data structure. But the operation shows up wherever equality, connectivity, or “these two things now belong to the same component” arrives incrementally: Kruskal’s minimum spanning tree, type unification, connected-component labeling, offline graph algorithms, percolation simulations, image segmentation, and compiler bookkeeping.

The trick is not that the forest is always tidy.

The trick is that every lookup is allowed to tidy it.

Representatives Are Just Roots

The forest representation is almost embarrassingly plain. Every item stores one parent pointer. A root points to itself. The representative of x is the root reached by following parents:

find(x):
  while parent[x] != x:
    x = parent[x]
  return x

To merge two sets, find both roots and attach one root under the other:

union(x, y):
  rx = find(x)
  ry = find(y)
  if rx != ry:
    parent[rx] = ry

This already maintains the partition invariant. It also admits a terrible shape. If unions keep attaching the older root under the newer root, the forest can become a chain:

0 -> 1 -> 2 -> 3 -> ... -> n-1

Now find(0) costs \(n-1\) parent traversals.

Galler and Fischer’s 1964 paper introduced an improved tree-based equivalence algorithm for compiler storage assignment in Fortran-like EQUIVALENCE, DIMENSION, and COMMON settings.¹ The modern disjoint-set forest grew from exactly this kind of mundane pressure: many equivalence claims, many representative queries, and no appetite for rewriting whole sets on every merge.

Rank Prevents Ambition

The first repair is to stop attaching large trees under small ones. A common rule is union by rank:

if rank[rx] < rank[ry]: parent[rx] = ry
if rank[rx] > rank[ry]: parent[ry] = rx
if ranks tie:
  parent[ry] = rx
  rank[rx] += 1

Rank is not necessarily the current height after path compression begins. It is a certificate left behind by earlier balanced merges.

The useful invariant is:

if a root has rank r, its component contains at least 2^r items

That is an induction. Rank starts at zero with one item. A rank only increases when two roots of equal rank merge. If both roots of rank r have at least 2^r items, the new root of rank r+1 has at least 2^(r+1) items.

So rank cannot grow past \(\lfloor \log_2 n \rfloor\). This alone prevents the obvious chain disaster.

Compression Repairs the Road

Path compression changes find. After walking from x to the root, it points the nodes on that path directly to the root:

find(x):
  walk x -> ... -> root
  for every node on the path:
    parent[node] = root
  return root

This does not change the partition. It only changes the route by which future queries discover the representative.

That distinction is the whole data structure:

membership is invariant
parent pointers are negotiable

Hopcroft and Ullman studied set-merging algorithms before the final modern bound was understood.² Tarjan’s 1975 paper gave the classic analysis for the good forest algorithm, showing that the combined heuristics run in amortized time governed by an inverse-Ackermann function.³ Galil and Italiano’s survey is a useful map of the broader family of disjoint-set union results and variants.⁴

I am not going to rederive Tarjan’s proof here. The useful engineering reading is narrower and safer:

rank stops trees from becoming tall quickly
compression spends each find to make later finds cheaper
the amortized cost is effectively constant for ordinary input sizes

“Effectively constant” is interpretation, not the theorem. The theorem has an inverse-Ackermann term. The reason programmers treat it as constant is that the function grows so slowly on any input size they will see.

Lab: Let the Forest Rewrite Itself

The lab below runs the same deterministic workload through four policies:

plain linking;
path compression only;
union by rank only;
union by rank plus path compression.

The workload intentionally mixes a chain-shaped prefix with random unions and repeated finds. Plain linking uses the bad rule parent[rootA] = rootB, so it is allowed to demonstrate the failure mode.

With the default settings:

items:          48
chain unions:   20
random unions:  90
repeated finds: 120
seed:           111

the measured results are:

Policy	Parent traversals	Parent writes	Max depth	Avg depth
plain linking	4451	46	31	12.250
compression only	411	191	2	1.000
rank only	442	46	2	1.604
rank + compression	318	76	2	0.979

Do not read those as universal benchmarks. They are this workload. The point is that the same final partition can be represented by very different parent forests.

Items 48 Chain unions 20 Random unions 90 Repeated finds 120 Random seed 111 Focus view

What the Audit Checks

The lab does not trust the forest to validate itself. It runs a naive partition oracle beside every variant. The oracle stores one label per item and rewrites all labels on every union. That is slow, but easy to inspect.

The audit checks:

every variant agrees with the oracle partition;
rank variants satisfy the rank-size invariant;
the fast variant is no deeper than plain linking on the tested workloads;
the fast variant uses no more parent traversals than plain linking;
path compression shortens a deliberately constructed chain;
all variants execute the same operation counts;
all variants end with the same component count.

The exported audit reports 35 named checks: seven invariants across each of the five deterministic workloads below.

The current deterministic audit grid is:

Items	Chain unions	Random unions	Finds	Plain traversals	Fast traversals	Plain depth	Fast depth
48	20	90	120	4451	318	31	2
16	15	0	64	657	59	15	1
48	8	70	120	1323	247	13	1
72	0	150	120	2468	374	19	1
96	95	60	200	19123	356	95	1

You can reproduce that table from the repository root:

node - <<'NODE'
const lab = require("./assets/js/union-find-lab.js");
const EXPECTED_CASE_SHAPE = [
  "1:items=48:chain=20:random=90:finds=120:seed=111:4451/318:31/2:components=2:7/7",
  "2:items=16:chain=15:random=0:finds=64:seed=3:657/59:15/1:components=1:7/7",
  "3:items=48:chain=8:random=70:finds=120:seed=203:1323/247:13/1:components=3:7/7",
  "4:items=72:chain=0:random=150:finds=120:seed=42:2468/374:19/1:components=2:7/7",
  "5:items=96:chain=95:random=60:finds=200:seed=77:19123/356:95/1:components=1:7/7"
];
const EXPECTED_CHECK_NAMES = [
  "all variants match the oracle partition",
  "rank variants keep rank invariants",
  "fast variant is no deeper than plain",
  "fast variant uses no more parent traversals than plain",
  "path compression shortens the chain demo",
  "operation counts are preserved",
  "component counts agree"
];
const EXPECTED_CASES = EXPECTED_CASE_SHAPE.length;
const EXPECTED_CHECKS = EXPECTED_CASES * EXPECTED_CHECK_NAMES.length;
const EXPECTED_CHECK_ROWS = Array.from({ length: EXPECTED_CASES }, (_, index) =>
  `${index + 1}:` + EXPECTED_CHECK_NAMES.map((name) => `${name}=true`).join("|")
);

function sameList(actual, expected) {
  return actual.length === expected.length &&
    actual.every((value, index) => value === expected[index]);
}

function caseShape(row) {
  return `${row.caseId}:items=${row.items}:chain=${row.chainUnions}:` +
    `random=${row.randomUnions}:finds=${row.repeatedFinds}:seed=${row.seed}:` +
    `${row.plainTraversals}/${row.fastTraversals}:` +
    `${row.plainMaxDepth}/${row.fastMaxDepth}:components=${row.components}:` +
    `${row.passedChecks}/${row.totalChecks}`;
}

function checkRow(row) {
  return `${row.caseId}:` +
    row.checks.map((check) => `${check.name}=${check.ok}`).join("|");
}

function rowDrifts(actual, expected) {
  return {
    missing: expected.filter((row) => !actual.includes(row)),
    extra: actual.filter((row) => !expected.includes(row))
  };
}

function hasRowDrift(drift) {
  return drift.missing.length > 0 || drift.extra.length > 0;
}

const audit = lab.auditGrid();
const failed = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const shape = {
  cases: audit.cases.map(caseShape),
  checkRows: audit.cases.map(checkRow)
};
const checkRowDrifts = rowDrifts(shape.checkRows, EXPECTED_CHECK_ROWS);
const shapeErrors = [];
if (!sameList(shape.cases, EXPECTED_CASE_SHAPE)) {
  shapeErrors.push({ name: "cases", actual: shape.cases, expected: EXPECTED_CASE_SHAPE });
}
audit.cases.forEach((row) => {
  const names = row.checks.map((check) => check.name);
  if (!sameList(names, EXPECTED_CHECK_NAMES)) {
    shapeErrors.push({
      name: `case ${row.caseId} check names`,
      actual: names,
      expected: EXPECTED_CHECK_NAMES
    });
  }
});
if (hasRowDrift(checkRowDrifts)) {
  shapeErrors.push({ name: "checkRows", drift: checkRowDrifts });
}
const summary =
  `${audit.passed}/${audit.total} cases and ${audit.passedChecks}/${audit.totalChecks} checks passed`;
if (
  shapeErrors.length ||
  failed.length ||
  !audit.ok ||
  audit.total !== EXPECTED_CASES ||
  audit.totalChecks !== EXPECTED_CHECKS ||
  audit.passed !== audit.total ||
  audit.passedChecks !== audit.totalChecks
) {
  throw new Error(JSON.stringify({
    summary,
    shapeErrors,
    shape,
    checkRowDrifts,
    failed,
    errors: audit.errors,
    totals: {
      total: audit.total,
      passed: audit.passed,
      passedChecks: audit.passedChecks,
      totalChecks: audit.totalChecks
    }
  }, null, 2));
}
console.table(audit.cases.map((row) => ({
  items: row.items,
  chain: row.chainUnions,
  random: row.randomUnions,
  finds: row.repeatedFinds,
  plainTraversals: row.plainTraversals,
  fastTraversals: row.fastTraversals,
  plainDepth: row.plainMaxDepth,
  fastDepth: row.fastMaxDepth,
  checks: `${row.passedChecks}/${row.totalChecks}`,
  passed: row.passed
})));
console.log(summary);
NODE

Why the Shortcut Is Safe

Path compression can feel suspicious because it rewrites many parent pointers during a query. The reason it is safe is that those pointers are not the data. The data is the partition.

If every node on a path already reaches root r, then replacing its parent with r preserves the representative:

before: x -> ... -> r
after:  x -> r

The route changes. The set membership does not.

That is also why union-find is a nice example of amortized thinking. A find operation is allowed to pay a little extra bookkeeping because that bookkeeping changes the cost of future operations. Looking at one call in isolation misses the contract. The structure is not promising:

every operation has the same worst-case pointer count

It is promising something closer to:

over a sequence of operations,
the expensive walks flatten the forest that caused them

That is the mood of the Tarjan result. The forest learns from being traversed.

Bernard A. Galler and Michael J. Fischer, “An Improved Equivalence Algorithm”, Communications of the ACM 7(5), 1964. ACM record: https://dl.acm.org/doi/10.1145/364099.364331. ↩
John E. Hopcroft and Jeffrey D. Ullman, “Set Merging Algorithms”, SIAM Journal on Computing 2(4), 1973. ↩
Robert Endre Tarjan, “Efficiency of a Good But Not Linear Set Union Algorithm”, Journal of the ACM 22(2), 1975. The paper gives the classic inverse-Ackermann amortized analysis for the combined forest heuristics. ↩
Zvi Galil and Giuseppe F. Italiano, “Data Structures and Algorithms for Disjoint Set Union Problems”, ACM Computing Surveys 23(3), 1991. The survey organizes the union-find family and its historical analyses. ↩