Path Compression and Union by Rank: Optimizing Disjoint Sets

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 100int parent[N];int rank[N];voidmakeSet(int n){for(int i =0; i < n; i++){
      parent[i]= i;}}intfind(int x){if(parent[x]!= x){
      parent[x]=find(parent[x]);}return parent[x];}voidunionSet(int x,int y){int rootX =find(x);int rootY =find(y);if(rootX != rootY){if(rank[rootX]> rank[rootY]){
         parent[rootY]= rootX;}elseif(rank[rootX]< rank[rootY]){
         parent[rootX]= rootY;}else{
         parent[rootY]= rootX;
         rank[rootX]++;}}}intmain(){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));return0;}

Output

Following is the output of the above C 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 100int parent[N];int rank[N];voidmakeSet(int n){for(int i =0; i < n; i++){
      parent[i]= i;
      rank[i]=0;}}intfind(int x){if(parent[x]!= x){
      parent[x]=find(parent[x]);}return parent[x];}voidunionSet(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]++;}}}}intmain(){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));return0;}

Output

Following is the output of the above C 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

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.

Path Compression and Union by Rank: Optimizing Disjoint Sets