Union by Rank or Size

Union by rank or size is a Union-Find optimization that keeps parent trees shallow when merging groups.

It chooses which root should become the parent during union.

Core Idea

Without a rule, repeated unions can create long chains. Union by size attaches the smaller tree under the larger tree. Union by rank attaches the shallower tree under the deeper estimated tree.

Both approaches try to prevent tall structures.

Class Contract

UnionFind(size) starts with one group per element.

union(a, b) finds both roots, attaches the smaller group under the larger group, and returns False if both elements were already in the same group.

Python Example

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.size = [1] * size
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a == root_b:
            return False
 
        if self.size[root_a] < self.size[root_b]:
            root_a, root_b = root_b, root_a
 
        self.parent[root_b] = root_a
        self.size[root_a] += self.size[root_b]
        return True

The smaller group is attached under the larger group.

Size vs Rank

Union by size stores how many elements are in each root’s group. Union by rank stores an estimate of tree height. Both are used to choose which root becomes the parent.

For beginners, size is often easier to understand because it has a direct meaning: attach the smaller group under the larger group.

Why It Works

Long chains make find slow. If a large tree is repeatedly attached under a small tree, the structure can become unnecessarily tall. Union by size or rank keeps the tree shallow by making the larger or deeper structure remain the root.

Combined with path compression, this prevents repeated operations from degrading into long walks.

Complexity Effect

By itself, union by size or rank improves balance. With path compression, it gives the near-constant amortized behavior expected from practical Union-Find.

Common Confusions

Rank is not always the exact height after path compression. It is a guide for merging.

Union by size and union by rank are alternatives. Most implementations need one of them, not both.

Another common mistake is updating the size or rank for a node that is no longer a root. Size and rank values matter only for representatives.

When To Use It

Use union by rank or size with path compression for efficient Union-Find operations in connectivity-heavy algorithms.

Do not let the root choice depend on element value unless the problem has a special reason. Efficiency needs shallow trees, not meaningful root labels.

The Main Point

Union by size or rank keeps Union-Find trees shallow by choosing the root during merges deliberately.