Union-Find for GATE: Union by Rank, Path Compression and the Near-Constant Bound

Union-find is a tiny data structure with an intimidating complexity bound. GATE uses that mismatch well: a short trace can test parent pointers, ranks, path compression and asymptotic cost together. An eight-element sequence makes the bound concrete.

The problem union-find solves

Union-find, also called the disjoint-set union structure, maintains a partition of elements. Every element belongs to exactly one set, and the sets do not overlap. It supports three operations:

• MakeSet(x) creates the singleton set {x}.

• Find(x) returns the representative of the set containing x.

• Union(x, y) merges the two sets containing x and y.

The usual representation is a forest. Each set is a rooted tree, every node stores a parent pointer, and a root points to itself. The root is the representative. Find follows parents to a root. Union first finds two roots and links one under the other.

Only tree shape makes these operations expensive. If the trees remain shallow, both finding and merging stay fast.

Why naive union is slow, and what rank fixes

A naive union may attach roots without considering tree shape. With an unfortunate order, it can build a chain containing n nodes. The deepest Find then walks n - 1 edges and costs O(n).

Union by rank uses a small estimate of tree height. After finding both roots:

1. Attach the lower-rank root below the higher-rank root.

2. If ranks are equal, choose one root to remain on top.

3. Increase that surviving root's rank by 1 only in the equal-rank case.

Attaching a short tree below a taller one does not increase the taller tree's height. Height increases only when two equally ranked trees merge. A tree of rank r must contain at least 2^r elements, so rank is at most log2(n). Union by rank alone therefore keeps worst-case tree height O(log n).

Rank is not recomputed downward after path compression. It remains a safe linking guide, not necessarily the current exact height.

Path compression during Find

Path compression works inside Find(x). First follow parent pointers until reaching the representative. While returning, change every node on that search path to point directly to the root.

The first search pays for the old path. Later searches from those nodes reach the representative in one hop. Compression also helps future searches starting below or through the changed nodes.

With union by rank and path compression together, a sequence of operations costs O(alpha(n)) amortised per operation, where alpha is the inverse Ackermann function. It grows so slowly that it is at most a tiny constant for any practical input. "Amortised" matters: one operation may still walk several edges, but the average over a long sequence is near constant.

Fully worked example: eight elements and seven unions

Create elements 1 through 8 with parent[x] = x and rank 0. The tie rule is: when ranks match, the first argument's root stays above the second root, and its rank increases.

1. Union(1,2): ranks tie at 0. Set 2 -> 1 and rank[1] = 1.

2. Union(3,4): set 4 -> 3 and rank[3] = 1.

3. Union(5,6): set 6 -> 5 and rank[5] = 1.

4. Union(7,8): set 8 -> 7 and rank[7] = 1.

5. Union(1,3): roots 1 and 3 both have rank 1. Set 3 -> 1 and rank[1] = 2. Node 4 remains below 3.

6. Union(5,7): roots 5 and 7 both have rank 1. Set 7 -> 5 and rank[5] = 2. Node 8 remains below 7.

7. Union(1,5): roots 1 and 5 both have rank 2. Set 5 -> 1 and rank[1] = 3.

The final parent array is:

Node 8 is deepest: 8 -> 7 -> 5 -> 1, which is three edges. The root rank is 3, consistent with a balanced construction from eight singleton elements. All eight nodes are in one set because every parent chain ends at 1.

The same example under path compression

Now call Find(8). The search visits four nodes in this order:

8 -> 7 -> 5 -> 1

It traverses three parent edges and returns representative 1. During the return, path compression assigns parent[8] = 1, parent[7] = 1 and parent[5] = 1. The last assignment does not change 5 because it already points to 1, but it is still on the visited path.

After compression, the parent row is:

[1, 1, 1, 3, 1, 5, 1, 1] for nodes 1 through 8.

Ranks remain [3, 0, 1, 0, 2, 0, 1, 0]. They are not reset. A later Find(8) or Find(7) takes one hop. Node 6 still points to 5, so Find(6) takes two hops, 6 -> 5 -> 1, and would then compress 6 as well.

Without rank, a poor linking order could make 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1. Find(8) would then visit all eight nodes and traverse seven edges before compression.

The complexity claim and how GATE states it

Keep the cases separate:

• naive linking can produce O(n) height

• union by rank alone gives O(log n) worst-case height and Find

• path compression alone gives logarithmic amortised performance under arbitrary linking

• both optimisations together give O(alpha(n)) amortised time per operation

Do not answer O(1) as a formal bound when the option O(alpha(n)) is available. "Effectively constant" explains its practical behaviour, while O(alpha(n)) is the expected theoretical answer.

Kruskal, cycle detection and the exam angle

Kruskal's minimum-spanning-tree algorithm processes edges in increasing weight. For an edge (u,v), compare Find(u) and Find(v). Equal representatives mean u and v are already connected, so adding the edge would form a cycle. Different representatives mean the edge can be accepted, followed by Union(u,v).

That application is worked directly in Minimum Spanning Tree for GATE: Kruskal and Prim Numericals with Unique-MST Questions. Graph Algorithms: BFS, DFS, and shortest paths worked out helps separate union-find's connectivity role from traversal and shortest-path methods.

GATE can ask for a forest after a union sequence, the hops taken by a Find, the effect of compression, or the amortised bound. Confirm current Algorithms syllabus and weightage details on the official GATE portal of the organising IIT.

The short version and your next step

Union by rank prevents tall trees from forming. Path compression flattens paths when they are searched. Together they give O(alpha(n)) amortised operations, and Kruskal uses them as a fast cycle test.

Build algorithm coverage through GATE Guidance by Sanchit Sir, test traces under time in the GATE Test Series, and use the GATE CS preparation catalogue to connect this structure with the rest of Algorithms.