Forest Representation: Union by Rank and Path Compression | Algorithms II

Deep Forest Representation

Union-find forest: before and after path compression flattens the tree structure

Each set is represented as a rooted tree where each node points to its parent. The root’s parent pointer is NIL (or points to itself). The root serves as the representative of the set.

MakeSet

MakeSet(x):
    x.parent = x    // or NIL, depending on convention
    x.rank = 0

Creates a singleton tree. $\Theta(1)$ .

Find (Chase)

Follow parent pointers from x up to the root:

Find(x):
    while x.parent != NIL:    // or != x
        x = x.parent
    return x

Without optimisations, worst-case $\Theta(n)$ if trees become long chains.

Union by Rank

When merging two trees, make the root with the smaller rank point to the root with the larger rank. If ranks are equal, choose one as the new root and increment its rank by 1.

Rank is an estimate (upper bound) on the height of the tree. It is NOT the same as height after path compression is applied; ranks never decrease.

Union(x, y):
    rx = Find(x)
    ry = Find(y)
    if rx == ry: return
    if rx.rank > ry.rank:
        ry.parent = rx
    else if rx.rank < ry.rank:
        rx.parent = ry
    else:                     // equal ranks
        ry.parent = rx
        rx.rank = rx.rank + 1

Union by rank guarantees that a tree of rank $r$ contains at least $2^r$ nodes (provable by induction: each rank increase to $r+1$ merges two trees of rank $r$ , each having $\ge 2^r$ nodes, yielding $\ge 2^{r+1}$ ). Therefore, rank is at most $\lfloor \log_2 n \rfloor$ , and tree height (without compression) is $O(\log n)$ .

Path Compression

During Find(x), after locating the root, revisit all nodes on the path and set their parent pointer directly to the root. This flattens the search path:

Find(x):
    if x.parent != x:
        x.parent = Find(x.parent)    // recursive compression
    return x.parent

// Iterative version:
Find(x):
    root = x
    while root.parent != root:
        root = root.parent
    // Second pass: compress
    while x != root:
        next = x.parent
        x.parent = root
        x = next
    return root

Path compression makes future Find operations on the same or descendant nodes much faster. The cost of the first traversal is amortised over future operations.

Worked Example

Start with 7 singletons, all rank 0:

MakeSet(1..7): each node parent = self, rank = 0

Operation	Action	Resulting Trees
Union(1,2)	ranks equal, 2→1, rank(1)=1	1(rank1)←2
Union(3,4)	ranks equal, 4→3, rank(3)=1	3(rank1)←4
Union(1,3)	rank(1)=1 > rank(3)=1? No, equal. 3→1, rank(1)=2	1(rank2)←2, 1←3(rank1)←4
Union(5,6)	equal, 6→5, rank(5)=1	5(rank1)←6
Union(5,7)	rank(5)=1 > rank(7)=0, 7→5	5(rank1)←6, 5←7
Union(1,5)	rank(1)=2 > rank(5)=1, 5→1	1(rank2)←2,1←3←4,1←5←6,1←5←7
Find(4)	path 4→3→1, compress: 4→1, 3→1	4 and 3 now point directly to 1

After Find(4) with compression:

Combined Complexity

Using both union by rank and path compression, the amortised time per operation is $O(\alpha(n))$ , where $\alpha$ is the inverse Ackermann function. For any practical $n$ (less than $2^{2^{2^{65536}}}$ ), $\alpha(n) \le 4$ . Effectively constant time.

The proof of this bound is complex and uses a potential function based on partitioning ranks into levels; the full proof is beyond the Tripos scope but the result and the two heuristics are examinable.

Kruskal Complexity with Forest DS

With forest + union by rank + path compression:

MakeSet: $V$ calls, $O(V)$
Find: $2E$ calls, $O(E \cdot \alpha(V))$
Union: $V-1$ calls, $O(V \cdot \alpha(V))$
Sorting: $O(E \log V)$

Total: $O(E \log V + E \cdot \alpha(V)) = O(E \log V)$ since sorting dominates.

Summary

Heuristic	Guarantee	Alone	Combined
None	—	$O(n)$ per Find worst	—
Union by rank	Tree height $\le \lfloor \log_2 n \rfloor$	$O(\log n)$ per Find	$O(\alpha(n))$
Path compression	Flattens search path	$O(\log n)$ amortised	$O(\alpha(n))$
Both	Inverse Ackermann	—	Essentially $O(1)$

Key exam technique: When tracing Union/Find with compression, show the tree before and after each operation, and update ranks only on equal-rank Unions.