Disjoint-Set Forests

A disjoint-set forest is a representation of a collection of disjoint sets in which each set is represented by a rooted tree.

The important idea is:

One tree = one set, and the root of the tree = representative of that set.

Each node contains one element and has a pointer to its parent.

1. Why do we need another representation?

Recall the linked-list representation.

Suppose we have


Set = {b, c, e, h}

c
↓
b → e → h

The representative might be c.

In the linked-list representation, every element has a pointer to the representative:


b ──────┐
e ──────┤
h ──────┤
        ↓
        c

This makes FIND-SET very fast, but UNION can be expensive because many representative pointers may have to be changed.

Therefore another representation is introduced:

Instead of making every node point to the representative, let every node point only to its parent.

This gives us a tree.

2. Basic Structure of a Disjoint-Set Forest

Consider the set

{b,c,e,h}

It can be represented as:

Here:

c is the root.
c is the representative.
b points to c.
e points to c.
h points to e.

The parent relationships are:

Node	Parent
c	c
b	c
e	c
h	e

The important property is:


Parent(root) = root

So:


parent(c) = c

This tells us that c is the root.

3. Why is it called a "forest"?

Suppose we have two disjoint sets:

S_{1} = {b, c, e, h}

and

S_{2} = {d, f, g}

We can represent them as two trees:


          c                 f
        /   \              / \
       b     e            d   g
             |
             h

These two trees together form a forest.

Therefore:

Disjoint-set forest = collection of rooted trees

Each tree represents one disjoint set.

4. The Representative

The root of each tree is the representative of the set.

For example:

The representative is:

To determine whether h belongs to this set, we follow:


h → e → c

We eventually reach c, the root.

Therefore:


FIND-SET(h) = c

5. The Three Operations

The three basic operations remain:

MAKE-SET(x)
FIND-SET(x)
UNION(x,y)

But their implementation is now based on parent pointers.

6. MAKE-SET

CLRS gives:


MAKE-SET(x)

1  x.p = x
2  x.rank = 0

Let's understand this carefully.

When we create a new element x, it forms a tree containing only itself.

Since x is the root:


parent(x) = x

Therefore:


x.p = x

Initially its rank is:


x.rank = 0

because the tree has height 0.

Example

Perform:


MAKE-SET(a)
MAKE-SET(b)
MAKE-SET(c)

We get:


a       b       c
↑       ↑       ↑
|       |       |
a       b       c

Each vertex is its own representative.

7. What is Rank?

This is one of the most important concepts.

The rank of a node is an upper bound on the height of the node.

Initially:


rank(x) = 0

because a singleton tree has height 0.

For example:


       A
      / \
     B   C

The height of A is 1.

Therefore:


rank(A) = 1

At least initially, rank corresponds to the height.

However, after path compression, rank need not equal the actual height.

This distinction is very important.

8. FIND-SET

Without path compression, FIND-SET is conceptually very simple:

Follow parent pointers until you reach the root.

Consider:

Parent relationships:


parent(D) = C
parent(C) = B
parent(B) = A
parent(A) = A

Now execute:


FIND-SET(D)

We follow:


D
↓
C
↓
B
↓
A

Since


parent(A) = A

we have reached the root.

Therefore:


FIND-SET(D) = A

9. The Find Path

calls the nodes visited while moving toward the root the find path.

For:

the operation


FIND-SET(E)

has find path:


E → D → C → B → A

This becomes important when we introduce path compression.

10. UNION

Suppose we have two trees:


        A                  C
       / \                / \
      B   D              E   F

The representatives are:

and

Suppose we execute:


UNION(B,E)

First we find the representatives:


FIND-SET(B) = A
FIND-SET(E) = C

Then we connect the two roots.

For example:

Now there is only one tree, so there is only one set.

The representative is A.

11. The Problem with Simple UNION

There is a serious problem.

Suppose we repeatedly perform UNION operations in an unfortunate order.

Start:


A   B   C   D   E

Perform:


UNION(A,B)

Suppose B becomes the parent of A:


B
|
A

Then:


UNION(B,C)

could produce:


C
|
B
|
A

Then:


UNION(C,D)

produces:


D
|
C
|
B
|
A

Then:


UNION(D,E)

produces:


E
|
D
|
C
|
B
|
A

We have created a linear chain.

12. Why is the Chain Bad?

Suppose we perform:


FIND-SET(A)

We have to follow:


A → B → C → D → E

If there are n nodes, this can take:

O(n)

Therefore, the simple forest representation alone does not solve the problem.

This is exactly why:

The straightforward algorithms for disjoint-set forests are no faster than those for linked lists.

We need heuristics.

Two heuristic are introduced:

Union by Rank
Path Compression

13. Heuristic 1: Union by Rank

The first heuristic is union by rank.

The basic idea is:

When joining two trees, make the root with smaller rank point to the root with larger rank.

In other words:


larger rank
     ^
     |
smaller rank

The larger-rank tree becomes the parent.

14. Why Use Rank?

Suppose we have:


Tree A                  Tree B

    A                      B
   / \                    / \
  x   y                  p   q

Suppose:


rank(A) = 1
rank(B) = 1

They have equal rank.

We can choose either root.

Suppose A becomes the parent:

The rank of A increases:


rank(A) = 2

15. Unequal Ranks

Suppose:


rank(A) = 4

rank(B) = 2

Then we make:


A
|
B

That is:


       A
      / \
     ... B

More precisely:


B.parent = A

The ranks do not change.

So:


rank(A) = 4
rank(B) = 2

remain unchanged.

16. Equal Ranks

Suppose:


rank(A) = 3
rank(B) = 3

Choose one root, say A:


B.parent = A

Now the resulting tree can have height 4.

Therefore:


rank(A) = 4

So the rule is:

If ranks are unequal


larger-rank root becomes parent

and ranks don't change.

If ranks are equal


choose either root as parent

and increment the parent's rank.

17. Why Doesn't Rank Change When Ranks Are Unequal?

This is worth explaining to students.

Suppose:


rank(A) = 4
rank(B) = 2

The tree rooted at A has height at most 4.

The tree rooted at B has height at most 2.

Attach B below A:


A
|
B

The height of the resulting tree is still at most 4.

Therefore:


rank(A) remains 4

It does not become 5.

18. Why Does Rank Increase When Ranks Are Equal?

Suppose both trees have rank 3:


rank(A) = 3
rank(B) = 3

Attach B under A:


        A
        |
        B

The deepest nodes of B are now one level farther from A.

Therefore the maximum height can increase from 3 to 4.

Hence:


rank(A) = 4

19. A Very Important Property of Union by Rank

Union by rank ensures that the tree cannot become arbitrarily tall.

In fact, the rank of a tree is at most:

⌊log2n⌋

where n is the number of elements.

Why?

Whenever the rank increases, it is because two trees of equal rank were joined.

If a tree has rank r, it must contain at least:

2^r

nodes.

For example:

Rank	Minimum number of nodes
0	1
1	2
2	4
3	8
4	16
5	32

Therefore, if there are n nodes:

2^^{r} \leq n

Taking logarithms:

r \leq log_{2} n

Thus the tree height is bounded by O(logn).

This is why union by rank alone gives:

O(mlogn)

for a sequence of m operations.

20. Heuristic 2: Path Compression

Union by rank keeps trees relatively shallow, but we adds another extremely powerful heuristic:

Path compression.

Path compression is performed during FIND-SET.

Consider:

Suppose:


FIND-SET(E)

The find path is:


E → D → C → B → A

Path compression changes the parent pointers of the nodes on this path.

After the operation:


        A
      / | \ \
     B  C  D  E

Now:


parent(B) = A
parent(C) = A
parent(D) = A
parent(E) = A

The representative is still A, but the tree has become much flatter.

21. How Does the Recursive FIND-SET Do This?

CLRS gives:


FIND-SET(x)

1  if x ≠ x.p
2      x.p = FIND-SET(x.p)
3  return x.p

The crucial line is:


x.p = FIND-SET(x.p)

This is path compression.

Let's trace it.

Suppose:


A
|
B
|
C
|
D

Execute:


FIND-SET(D)

First call


FIND-SET(D)

D is not the root.

So:


FIND-SET(D.p)

which means:


FIND-SET(C)

C is not the root.

So:


FIND-SET(B)

B is not the root.

So:


FIND-SET(A)

At A

A is the root because:


A.p = A

So:


FIND-SET(A) returns A

22. The Second Pass

Now comes the clever part.

The recursion starts unwinding.

For B:


B.p = FIND-SET(A)

which gives:


B.p = A

For C:


C.p = FIND-SET(B)

which returns A.

Therefore:


C.p = A

For D:


D.p = FIND-SET(C)

which returns A.

Therefore:


D.p = A

Final tree:


        A
      / | \
     B  C  D

This is why we describes FIND-SET with path compression as a two-pass method:

First pass

Move upward:


D → C → B → A

to find the root.

Second pass

During recursion unwinding:


A → B → C → D

update the parent pointers.

23. Path Compression Does NOT Change Rank

This is an important point

Before compression:

Suppose:


rank(A) = 3

After:


      A
    / | \
   B  C  D

the actual height has decreased.

But:


rank(A)

is not decreased.

It remains 3.

Why?

Because rank is used as an upper bound and is maintained according to the union-by-rank rules. Path compression is allowed to reduce actual height, but it does not modify ranks.

Therefore:

Rank is not necessarily the actual height after path compression.

24. Combining the Two Heuristics

Now we have:

Union by Rank

Controls how trees are joined.


smaller rank
      ↓
larger rank

Path Compression

Controls what happens during FIND.


all nodes on find path
          ↓
      root

Together they are extraordinarily efficient.

25. Complete Pseudocode

MAKE-SET


MAKE-SET(x)

1  x.p = x
2  x.rank = 0

UNION


UNION(x,y)

1  LINK(FIND-SET(x), FIND-SET(y))

LINK


LINK(x,y)

1  if x.rank > y.rank
2      y.p = x
3  else
4      x.p = y
5      if x.rank == y.rank
6          y.rank = y.rank + 1

FIND-SET


FIND-SET(x)

1  if x ≠ x.p
2      x.p = FIND-SET(x.p)
3  return x.p

26. Complete Example

Let's start with:


MAKE-SET(A)
MAKE-SET(B)
MAKE-SET(C)
MAKE-SET(D)

Initially:


A     B     C     D

rank  rank  rank  rank
 0     0     0     0

UNION(A,B)

Ranks are equal.

Choose A as parent:


    A
    |
    B

Now:


rank(A) = 1
rank(B) = 0

UNION(C,D)

Again ranks are equal.

Choose C as parent:


    C
    |
    D

Now:


rank(C) = 1
rank(D) = 0

We now have:


    A             C
    |             |
    B             D

UNION(B,D)

First:


FIND-SET(B) = A
FIND-SET(D) = C

Ranks:


rank(A) = 1
rank(C) = 1

Equal ranks.

Choose A as parent:

Increment:


rank(A) = 2

27. Now Perform FIND-SET(D)

Before FIND:

Execute:


FIND-SET(D)

Path:


D → C → A

After path compression:


        A
      / | \
     B  C  D

Now:


D.parent = A

Future:


FIND-SET(D)

takes only one parent-pointer traversal.

28. Why the Combination Is So Powerful

Consider a sequence of operations that initially creates a somewhat deep tree.

Union by rank prevents UNION from creating extremely tall trees.

Then, whenever FIND-SET encounters a path, path compression flattens that path.

Therefore:


Union by Rank
      ↓
prevents bad trees

Path Compression
      ↓
flattens trees that are actually traversed

Together
      ↓
extremely efficient FIND and UNION

29. Running-Time Results

The important complexity results are:

Simple disjoint-set forest

Can create a chain:

O(n)

for a FIND-SET.

Union by Rank Alone

CLRS gives:

O(mlgn)

for a sequence of m operations, where n are MAKE-SET operations.

Thus the amortized cost per operation is:

O(lgn)

Path Compression Alone

Path compression by itself also gives a substantial improvement, although the analysis is more complicated.

A bound involving the number of MAKE-SET operations n and FIND-SET operations f.

For teaching purposes, the key point is:

Path compression alone is powerful, but its analysis is more complicated than union by rank.

Union by Rank + Path Compression

This is the important final result:

O(mα(n))

where:

m = total number of operations
n = number of MAKE-SET operations
α(n) = inverse Ackermann function

30. What Exactly Are m and n?

This is worth emphasizing because it is easy to confuse them.

Suppose we have:


MAKE-SET(A)
MAKE-SET(B)
MAKE-SET(C)
MAKE-SET(D)
MAKE-SET(E)

There are:

n = 5

elements.

Now suppose we perform:


UNION(A,B)
UNION(C,D)
FIND-SET(A)
FIND-SET(D)
UNION(B,C)
FIND-SET(E)

There are 7 additional operations.

Therefore total operations:

m = 5 + 7 = 12

So:

n = 5

and

m = 12

The complexity is:

O(mα(n))

or:

O(12α(5))

31. Why is α(n) Considered Almost Constant?

The inverse Ackermann function grows incredibly slowly.

For all practical input sizes:

α (n) \leq 4

So:

O(mα(n))

is practically:

O(m)

But theoretically, but it is not mathematically exactly linear.

It is more accurate to say:

almost linear

rather than simply O(m).

32. The Most Important Conceptual Picture

I would recommend presenting the progression to students as follows:


                 DISJOINT SET
                      |
          +-----------+-----------+
          |                       |
     Linked List              Forest
                                  |
                         +--------+--------+
                         |                 |
                    Basic Forest      Heuristics
                                           |
                              +------------+------------+
                              |                         |
                       Union by Rank             Path Compression
                              \                         /
                               \                       /
                                +---------------------+
                                          |
                                  Very efficient
                                          |
                                  O(m α(n))

33. Linked List vs Forest

Feature	Linked List	Disjoint-Set Forest
Representation	Linked list	Rooted tree
Representative	Head of list	Root of tree
Information stored	Next + representative	Parent + rank
FIND-SET	O(1) with node pointer	O(h) without compression
UNION	Can require many representative updates	Links two roots
Main heuristic	Weighted union	Union by rank
Additional heuristic	—	Path compression
Final performance	$O (m + n log n)$	O(mα(n))

Summary

There are really three stages in understanding disjoint-set forests:

Stage 1 — Basic Forest

Represent every set as a tree.

Problem:

Trees can become tall.

Stage 2 — Union by Rank

When joining two trees:


small rank
    ↓
large rank

This prevents trees from becoming unnecessarily tall.

Result:

O(mlogn)

Stage 3 — Path Compression

When executing FIND:


A
|
B
|
C
|
D

turn it into:


    A
  / | \
 B  C  D

This makes subsequent FIND operations extremely fast.

Combining both:

O(mα(n))

Disjoint-set forests represent each set as a rooted tree whose root is the representative; union by rank keeps the trees shallow when sets are merged, while path compression flattens the trees during FIND-SET operations, and together these heuristics give an asymptotically optimal running time of $O (m α (n))$ .