# Disjoint Set | Union-Find Algorithm – Union by rank and path compression

Earlier we have seen the complete implementation of Disjoint Set. We strongly recommend reading this before continue.

Disjoint Set operations –

• MakeSet(x)
• Find(x)
• Union(x,y)

How Disjoint Set is optimized:

• Union by rank.
• Path by compression.

Union by rank:

Uses Find to determine the roots of the trees x and y belong to. If the roots are distinct, the trees are combined by attaching the root of one to the root of the other. If this is done naively, such as by always making x a child of y, the height of the trees can grow as O(n). We can optimize it by using union by rank.

Union by rank always attaches the shorter tree to the root of the taller tree.

To implement union by rank, each element is associated with a rank. Initially a set has one element and a rank of zero.

If we union two sets and

• Both trees have the same rank – the resulting set’s rank is one larger
• Both trees have the different ranks – the resulting set’s rank is the larger of the two. Ranks are used instead of height or depth because path compression will change the trees’ heights over time.

Worst case complexity: O(LogN)

Explanation:

Pseudo Code:

```function Union(x, y)
xRoot := Find(x)
yRoot := Find(y)

// x and y are already in the same set
if xRoot == yRoot
return

// x and y are not in same set, so we merge them
if xRoot.rank < yRoot.rank
xRoot.parent := yRoot
else if xRoot.rank > yRoot.rank
yRoot.parent := xRoot
else
xRoot.parent := yRoot
yRoot.rank   := yRoot.rank + 1
```

Path compression:

Path compression` is a way of flattening the structure of the tree whenever Find is used on it. Since each element visited on the way to a root is part of the same set, all of these visited elements can be reattached directly to the root. The resulting tree is much flatter, speeding up future operations not only on these elements, but also on those referencing them.

Explanation:

Pseudo code:

```function Find(x)
if x.parent != x
x.parent := Find(x.parent)
return x.parent
```

MakeSet

The MakeSet operation makes a new set by creating a new element with a unique id, a rank of 0, and a parent pointer to itself. The parent pointer to itself indicates that the element is the representative member of its own set.

The MakeSet operation has O(1) time complexity.

Pseudo code:

``` function MakeSet(x)
if x is not already present:
add x to the disjoint-set tree
x.parent := x
x.rank   := 0
```

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

```Disjoint Sets: