Union by Rank and Path Compression: Two Heuristics That Fix the Chain

The parent-pointer forest described in Parent-Pointer Forests as the Representation of Disjoint Sets is correct but can degenerate into a single path of length n. Two independent repairs exist, and they attack the problem from opposite ends: one constrains the shape at the moment of merging, the other rewrites the shape during queries. Either alone improves the worst case. Together they produce a bound so small that the structure is treated as constant-time in practice, though the analysis required to prove it is considerably more delicate than either heuristic looks.

Attaching the smaller tree under the larger

The arbitrary rule parent[rb] = ra ignores the sizes of the two trees it joins. The fix is to make the choice depend on the trees: attach the root of the smaller tree beneath the root of the larger one. The intuition is a doubling argument. An element’s depth increases by one only when its tree is merged into a tree at least as large, so its tree size at least doubles, and it can double at most log₂ n times before the tree contains everything. Depth is therefore bounded by ⌊log₂ n⌋, which for n = 10⁶ is 19 and for n = 2³² is 32.

The size must be stored somewhere, and the root is the only place with spare room. The negative-value encoding puts -size in the root’s parent slot, using the sign to distinguish roots from children and the magnitude to hold the count:

#include <stddef.h>

/* parent[i] < 0 means i is a root and the block has -parent[i] members. */
static size_t find(const long *parent, size_t x) {
    while (parent[x] >= 0)
        x = (size_t)parent[x];
    return x;
}

static void unite(long *parent, size_t a, size_t b) {
    size_t ra = find(parent, a), rb = find(parent, b);
    if (ra == rb)
        return;
    if (parent[ra] > parent[rb]) {   /* ra is the smaller: -size is greater */
        size_t t = ra; ra = rb; rb = t;
    }
    parent[ra] += parent[rb];        /* sizes add; both are negative */
    parent[rb] = (long)ra;
}

Two details make this work. The comparison parent[ra] > parent[rb] compares negative sizes, so the larger value is the smaller tree; writing it as a comparison on magnitudes inverts the branch and silently produces a structure that is still correct but has lost the guarantee. And the sum must be computed before the child’s slot is overwritten, because after parent[rb] = ra the size is gone.

Rank is the alternative to size. Storing exact sizes costs a slot per root anyway, so rank offers no space saving over size in this encoding; its advantage appears when sizes are not otherwise available. Rank is defined as an upper bound on height: a singleton has rank 0, and when two roots of equal rank are merged the survivor’s rank increases by one, while merging unequal ranks leaves the larger rank alone. Rank never decreases and never needs to be recomputed, which is why it survives path compression, where heights become unknown. The bound it guarantees is the same ⌊log₂ n⌋.

Union by rank without compression gives find a worst case of O(log n) and unite O(1) once the two finds are paid for, for O(m log n) over m operations. That is already good enough for most work, and it has one property the compressed version loses: the structure is a genuine forest whose shape is stable between operations, which makes it inspectable and, with care, persistable.

Flattening the path during a find

Compression attacks the cost from the query side. A find already walks from the element to its root, so it knows every node on that path; rewriting each node’s parent to point directly at the root makes the next traversal of the same path one step. The rewrite is pure gain for future queries and costs one store per node visited.

There are three placements of those stores, and they differ in constant factors and in how much they disturb concurrent readers.

Two-pass compression walks to the root, then walks the path again setting each node’s parent to the root. It does two traversals and d stores for a path of depth d, and it produces the flattest possible result.

Path halving rewires every other node: point the current node at its grandparent, then advance two levels. It does one traversal and about d/2 stores, and it leaves a path of roughly half the original depth. The halving variant is what Tarjan and van Leeuwen analysed as achieving the same asymptotic bound as full compression.

Path splitting performs the same rewire but advances one level at a time, so every node on the path except the root and its immediate child is rewired rather than every second one. The resulting depth is the same to within a factor, and the store count is about d instead of d/2. It is the formulation that falls out most naturally from the iterative loop, which is why it appears in code that was not written with the analysis in mind.

/* Halving: rewire every second node on the path to its grandparent.
   parent[i] < 0 marks a root and holds -size. */
static size_t find_halving(long *parent, size_t x) {
    while (parent[x] >= 0) {
        long p = parent[x];
        if (parent[p] < 0)               /* p is the root: nothing to rewire */
            return (size_t)p;
        parent[x] = parent[p];           /* skip one level permanently */
        x = (size_t)parent[p];           /* continue from the grandparent */
    }
    return x;                            /* x is a root */
}

The check parent[p] < 0 is what makes halving safe at the top of the tree: if the parent is a root, writing parent[x] = parent[p] would point the node at a negative size value, which is not an index. Omitting that check is the most common bug in hand-written halving code, and it corrupts the array rather than merely slowing it down. The uncompressed loop in Parent-Pointer Forests as the Representation of Disjoint Sets avoids the issue by testing the same condition as its loop predicate.

Why the heuristics cannot be analysed separately

Path compression makes heights unknowable. After a find flattens a subtree, a root’s rank no longer equals its height and may exceed it, so the rank is only an upper bound. The doubling argument for union by size still holds, because compression never changes the number of members in a block, but the argument for union by rank needs the bound rather than the exact height, and the bound survives.

The interesting part is the interaction in the other direction. Compression alone, with arbitrary attachment, is not O(log n) per operation. Tarjan’s 1975 analysis gives O((m + n) log n) amortized for that combination, which is a genuine improvement over O(mn) but far from the combined bound. The adversary can keep building tall trees and force finds to walk them; compression shortens each path it touches, but new elements keep arriving at the bottom.

With both heuristics the amortized cost of a sequence of m operations on n elements is O(m · α(n)), where α is the inverse of a variant of the Ackermann function. That result, and the matching lower bound showing no algorithm in this family does better, is the subject of The Inverse Ackermann Bound and Why It Is Effectively Constant.

The practical reading of α(n) ≤ 4 for every n that fits in a machine word is that the amortized cost is at most four link traversals, plus the constant work of the union. It is not literally O(1), and the distinction matters in one place: the bound is amortized, so a single find on an uncompressed path can still cost O(log n), which is 30-odd iterations at worst. Code with a hard per-operation latency requirement, such as an interrupt handler or a real-time loop, cannot rely on the amortized figure.

What compression costs that rank does not

Compression writes to memory that a query only needed to read. In a read-only or copy-on-write setting that is fatal: a find on a shared structure dirties pages and invalidates snapshots. The rollback variant used for offline dynamic connectivity drops compression entirely for exactly this reason, keeping union by size and undoing merges by replaying a log — the technique described in Rollback Union-Find and Offline Dynamic Connectivity.

Compression also destroys the ability to answer “what was the parent before this query”, so any application that needs the union history, such as building a merge tree or computing a dendrogram, must record the merges separately rather than reading them back out of the array.

Both heuristics assume the array is mutable and exclusively owned. Under concurrency, a halving find performs a store to a slot another thread may be reading, and the interleaving can produce a parent chain that is temporarily cyclic if two threads rewrite each other’s links. The usual remedies are per-thread structures with a merge phase, or a lock around union, and neither is a small change.

Choosing among the four combinations

The four combinations have distinct profiles, and the choice is not always “both heuristics”.

Attachment	Compression	Amortized cost	Notes
arbitrary	none	O(n) per find worst case	only for tiny n or one-shot use
arbitrary	full	O((m+n) log n)	simple, no extra state
by size or rank	none	O(log n) worst case per find	stable shape, persistable, rollback-friendly
by size or rank	full or halving	O(m α(n))	the default choice

The third row is underrated. When the structure must be serialized, snapshotted, or walked, an uncompressed forest with a height bound of 32 is easier to reason about than a compressed one, and the difference between 32 steps and 4 steps is irrelevant next to the cost of the I/O that usually surrounds such a structure. The compressed variants win when the structure lives in cache and is queried millions of times, which is the case the analysis was built for.