Path Compression and Union by Rank: Optimizing Disjoint Sets

Previous
Quiz
Next

Path Compression and Union by Rank are two optimization techniques used in Disjoint Set Data Structure. These techniques help to improve the efficiency of the Disjoint Set operations like Find, Union, and MakeSet.

Path Compression

As the name suggests, Path Compression is a technique that compresses the path from a node to the root of the tree. When we perform a Find operation on a node, we traverse the path from the node to the root of the tree. During this traversal, we update the parent of each node to the root of the tree.

It helps to reduce the height of the tree and improves the efficiency of the Find operation.

Algorithm for Path Compression

Here is the algorithm for Path Compression −

1. If the node is the root of the tree, return the node
2. Otherwise, recursively find the root of the tree
3. Update the parent of the node to the root of the tree
4. Return the root of the tree

Code for Path Compression

Let's see the code for Path Compression in C, C++, Java, and Python −

C C++ Java Python 
// C program to implement Path Compression in Disjoint Set

#include <stdio.h>

#define N 100

int parent[N];
int rank[N];

void makeSet(int n) {
   for (int i = 0; i < n; i++) {
      parent[i] = i;
   }
}

int find(int x) {
   if (parent[x] != x) {
      parent[x] = find(parent[x]);
   }
   return parent[x];
   
}

void unionSet(int x, int y) {
   int rootX = find(x);
   int rootY = find(y);
   if (rootX != rootY) {
      if (rank[rootX] > rank[rootY]) {
         parent[rootY] = rootX;
      } else if (rank[rootX] < rank[rootY]) {
         parent[rootX] = rootY;
      } else {
         parent[rootY] = rootX;
         rank[rootX]++;
      }
   }
}
int main() {
   int n = 5;
   makeSet(n);

   unionSet(0, 1);
   unionSet(1, 2);
   unionSet(3, 4);

   printf("Find(2): %d\n", find(2));
   printf("Find(3): %d\n", find(3));

   return 0;
}

Output

Following is the output of the above C code −

Find(2): 0
Find(3): 3

#include <iostream>
using namespace std;

#define N 100

int parent[N];

void makeSet(int n) {
   for (int i = 0; i < n; i++) {
      parent[i] = i;
   }
}

int find(int x) {
   if (parent[x] != x) {
      parent[x] = find(parent[x]);
   }
   return parent[x];
}

void unionSet(int x, int y) {
   int rootX = find(x);
   int rootY = find(y);
   if (rootX != rootY) {
      parent[rootY] = rootX;
   }
}

int main() {
   int n = 5;
   makeSet(n);

   unionSet(0, 1);
   unionSet(1, 2);
   unionSet(3, 4);

   cout << "Find(2): " << find(2) << endl;
   cout << "Find(3): " << find(3) << endl;

   return 0;
}

Output

Following is the output of the above C++ code −

Find(2): 0
Find(3): 3

// Java program to implement Path Compression in Disjoint Set

public class DisjointSet {
   int[] parent;

   public DisjointSet(int n) {
      parent = new int[n];
      makeSet(n);
   }

   public void makeSet(int n) {
      for (int i = 0; i < n; i++) {
         parent[i] = i;
      }
   }

   public int find(int x) {
      if (parent[x] != x) {
         parent[x] = find(parent[x]);
      }
      return parent[x];
   }

   public void unionSet(int x, int y) {
      int rootX = find(x);
      int rootY = find(y);
      if (rootX != rootY) {
         parent[rootY] = rootX;
      }
   }

   public static void main(String[] args) {
      int n = 5;
      DisjointSet ds = new DisjointSet(n);

      ds.unionSet(0, 1);
      ds.unionSet(1, 2);
      ds.unionSet(3, 4);

      System.out.println("Find(2): " + ds.find(2));
      System.out.println("Find(3): " + ds.find(3));
   }
}

Output

Following is the output of the above Java code −

Find(2): 0
Find(3): 3

# Python program to implement Path Compression in Disjoint Set

N = 100
parent = [0] * N

def makeSet(n):
   for i in range(n):
      parent[i] = i

def find(x):
   if parent[x] != x:
      parent[x] = find(parent[x])
   return parent[x]

def unionSet(x, y):
   rootX = find(x)
   rootY = find(y)
   if rootX != rootY:
      parent[rootY] = rootX

n = 5
makeSet(n)

unionSet(0, 1)
unionSet(1, 2)
unionSet(3, 4)

print("Find(2):", find(2))
print("Find(3):", find(3))

Output

Following is the output of the above Python code −

Find(2): 0
Find(3): 3

Union by Rank

Union by Rank is another optimization technique used in Disjoint Set Data Structure. In this technique, we maintain the rank of each node in the tree. The rank of a node is the height of the tree rooted at that node. When we perform a Union operation, we merge the tree with a smaller rank into the tree with a larger rank.

It helps to keep the height of the tree as small as possible and improves the efficiency of the Union operation.

Algorithm for Union by Rank

Here is the algorithm for Union by Rank −

1. Find the root of the tree for the given nodes.
2. If the rank of the root of the first tree is greater than the rank of the root of the second tree, make the root of the second tree as the child of the root of the first tree.
3. Otherwise, make the root of the first tree as the child of the root of the second tree.
4. If the rank of the root of the first tree is equal to the rank of the root of the second tree, increment the rank of the root of the second tree by 1.

Code for Union by Rank

Let's see the code for Union by Rank in C, C++, Java, and Python −

C C++ Java Python 
// C program to implement Union by Rank in Disjoint Set
#include <stdio.h>
#define N 100

int parent[N];
int rank[N];

void makeSet(int n) {
   for (int i = 0; i < n; i++) {
      parent[i] = i;
      rank[i] = 0;
   }
}
int find(int x) {
   if (parent[x] != x) {
      parent[x] = find(parent[x]);
   }
   return parent[x];
}
void unionSet(int x, int y) {
   int rootX = find(x);
   int rootY = find(y);
   if (rootX != rootY) {
      if (rank[rootX] > rank[rootY]) {
         parent[rootY] = rootX;
      } else {
         parent[rootX] = rootY;
         if (rank[rootX] == rank[rootY]) {
            rank[rootY]++;
         }
      }
   }
}
int main() {
   int n = 5;
   makeSet(n);

   unionSet(0, 1);
   unionSet(1, 2);
   unionSet(3, 4);

   printf("Find(2): %d\n", find(2));
   printf("Find(3): %d\n", find(3));

   return 0;
}

Output

Following is the output of the above C code −

Find(2): 0
Find(3): 3

#include <iostream>
using namespace std;

#define N 100
int parent[N];  
int rankArr[N];

void makeSet(int n) {
   for (int i = 0; i < n; i++) {
      parent[i] = i;
      rankArr[i] = 0;
   }
}

int find(int x) {
   if (parent[x] != x) {
      parent[x] = find(parent[x]);
   }
   return parent[x];
}

void unionSet(int x, int y) {
   int rootX = find(x);
   int rootY = find(y);

   if (rootX != rootY) {
      if (rankArr[rootX] > rankArr[rootY]) {
         parent[rootY] = rootX;
      } else {
         parent[rootX] = rootY;
         if (rankArr[rootX] == rankArr[rootY]) {
            rankArr[rootY]++;
         }
      }
   }
}

int main() {
   int n = 5;
   makeSet(n);

   unionSet(0, 1);
   unionSet(1, 2);
   unionSet(3, 4);

   cout << "Find(2): " << find(2) << endl;
   cout << "Find(3): " << find(3) << endl;

   return 0;
}

Output

Following is the output of the above C++ code −

Find(2): 0
Find(3): 3

// Java program to implement Union by Rank in Disjoint Set
public class DisjointSet {
   int[] parent;
   int[] rank;

   public DisjointSet(int n) {
      parent = new int[n];
      rank = new int[n];
      makeSet(n);
   }

   public void makeSet(int n) {
      for (int i = 0; i < n; i++) {
         parent[i] = i;
         rank[i] = 0;
      }
   }

   public int find(int x) {
      if (parent[x] != x) {
         parent[x] = find(parent[x]);
      }
      return parent[x];
   }

   public void unionSet(int x, int y) {
      int rootX = find(x);
      int rootY = find(y);
      if (rootX != rootY) {
         if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
         } else {
            parent[rootX] = rootY;
            if (rank[rootX] == rank[rootY]) {
               rank[rootY]++;
            }
         }
      }
   }

   public static void main(String[] args) {
      int n = 5;
      DisjointSet ds = new DisjointSet(n);

      ds.unionSet(0, 1);
      ds.unionSet(1, 2);
      ds.unionSet(3, 4);

      System.out.println("Find(2): " + ds.find(2));
      System.out.println("Find(3): " + ds.find(3));
   }
}

Output

Following is the output of the above Java code −

Find(2): 1
Find(3): 4

# Python program to implement Union by Rank in Disjoint Set

N = 100
parent = [0] * N
rank = [0] * N

def makeSet(n):
   for i in range(n):
      parent[i] = i
      rank[i] = 0

def find(x):
   if parent[x] != x:
      parent[x] = find(parent[x])
   return parent[x]

def unionSet(x, y):
   rootX = find(x)
   rootY = find(y)
   if rootX != rootY:
      if rank[rootX] > rank[rootY]:
         parent[rootY] = rootX
      else:
         parent[rootX] = rootY
         if rank[rootX] == rank[rootY]:
            rank[rootY] += 1

n = 5
makeSet(n)

unionSet(0, 1)
unionSet(1, 2)
unionSet(3, 4)

print("Find(2):", find(2))
print("Find(3):", find(3))

Output

Following is the output of the above Python code −

Find(2): 0
Find(3): 3

Comparison of Path Compression and Union by Rank

Let's compare the efficiency of the Disjoint Set operations with and without Path Compression and Union by Rank −

Operation Without Optimization With Path Compression With Union by Rank With Path Compression and Union by Rank
MakeSet O(1) O(1) O(1) O(1)
Find O(n) O(log n) O(log n)
Union O(n) O(log n) O(log n) O(log n)

Conclusion

Path Compression and Union by Rank are two optimization techniques used in Disjoint Set Data Structure. These techniques help to improve the efficiency of the Disjoint Set operations like Find, Union, and MakeSet.

Using both Path Compression and Union by Rank, we can keep the height of the tree as small as possible and improve the efficiency of the Disjoint Set operations.

Print Page
Previous
Next
Advertisements