Disjoint-Set, Union By Rank & Path Compression
Disjoint-Set is a data structure that stores and maintains a collection of disjoint sets.
Note : Two sets are disjoint if their is no common element between the two; i.e their intersection is NULL.
Example : Set A { 1, 4, 6 } and Set B { 2, 5 } are disjoint.
Operations provided by disjoint sets
- Create-Set ( a ) : Create a set with one element { a }
- Find-Set ( a ) : Return a pointer that represents a set containing element { a }
- Merge-Set ( a, b ) : Merge a set containing element { a } and set containing element { b } into a single set. The original sets containing { a } and { b } are destroyed.
Implementation of disjoint sets
Root trees is one of the better ways of implementing disjoing sets as it is faster than other ways like linked list implementation. In rooted tree implemenation we have
- The sets are represented by rooted trees. Each node of the rooted tree contains one element and each tree represents a set.
- Each element of the set ( i.e the node of the tree ) points to its parent which represents that set.
- The root of the tree is its own parent.
Union-By-Rank and Path Compression are two heuristics that make the implementation of disjoint sets faster.
- Union-By-Rank
- In the Union-By-Rank approach, each node in the tree has a rank.
- Rank of a node is the number of nodes that point to it.
- For merging two disjoint subsets, the root of the tree with fewer nodes is made to point to the root of the tree with more nodes. i.e The root of a tree with smaller rank points to the root of a tree with bigger rank.
- The rank of a node is approximately the log 2 of the size of the sub-tree.
Algorithm : Merge ( a, b )
1. root_a = Find_Parent ( a )
root_b = Find_Parent ( b )
2. If root_a != root_b then
3. If Rank [ root_a ] < Rank [ root_b ] then
Parent [ root_a ] = root_b
Rank [ root_b ] += 1
4. Else
Parent [ root_b ] = root_a
Rank [ root_a ] += 1
Example Disjoint sets : Union-By-Rank
- Path Compression
- This heuristic is applied for making the rooted tree as flat as possible.
- Path compression gets applied during the find parent operation of a given node, thereby compressing the path from a node
to the root of the tree.
Algorithm : FindParent ( a )
1. If ( a != Parent [ a ] ) then
Parent [ a ] = Find_Parent ( Parent [ a ] )
2. return Parent [ a ]
Example :
FindParent ( 10 )
As 10 != Parent [ 10 ] as parent of 10 is 9.
Parent [ 10 ] = FindParent [ Parent [ 10 ] ]
i.e Parent [ 10 ] = FindParent [ 9 ]
FindParent ( 9 )
As 9 != Parent [ 9 ] as parent of 9 is 2.
Parent [ 9 ] = FindParent [ Parent [ 9 ] ]
i.e Parent [ 9 ] = FindParent [ 2 ]
FindParent ( 2 )
As 2 != Parent [ 2 ] as parent of 2 is 1
Parent [ 2 ] = FindParent [ Parent [ 2 ] ]
i.e Parent [ 2 ] = FindParent [ 1 ]
FindParent ( 1 )
As 1 == Parent [ 1 ] as parent of 1 is 1
Return 1
Thus we have updated the parent as Parent [ 10 ] = Parent [ 9 ] = Parent [ 2 ] = 1
Time complexity : The time complexity of finding the union of disjoint sets by applying union-by-rank is O ( log n ). Where n is the number of sets. After applying path compression the time complexity is further reduced to O( α ( n ) ). α ( n ) is the inverse Ackermann function which tend to grow extremely slowly.
Implementation of Disjoint Set Union-By-Rank and Path Compression.
class Set :
def __init__( self, arg_data, arg_rank) :
self.rank = arg_rank
self.data = arg_data
self.parent = self
print("Created set : " + str(arg_data) + " Rank : " + str(arg_rank))
# FindParent applies path compression to all the nodes in the search path of the parent
# without changing their ranks.
def FindParent ( s ) :
if ( s.data != s.parent.data ) :
s.parent = FindParent ((s.parent))
return s.parent
# Merge operation makes use of heuristic union-by-rank.
def Merge ( a, b ) :
parent_of_a = FindParent(a)
parent_of_b = FindParent(b)
if ( parent_of_a.data != parent_of_b.data ) :
if ( a.rank < b.rank ) :
a.parent = parent_of_b
b.rank += 1
else :
b.parent = parent_of_a
a.rank += 1
print("\nMerging " + str(a.data) + " & " + str(b.data))
print("Rank of : " + str(a.data) + " = " + str(a.rank))
print("Parent of : " + str(a.data) + " = " + str(a.parent.data))
print("Rank of : " + str(b.data) + " = " + str(b.rank))
print("Parent of : " + str(b.data) + " = " + str(b.parent.data))
def main() :
# Initially every node in a set has a rank 0 and is a parent of itself
s1 = Set(1, 0) # Data : 1, Rank : 0, Parent : 1
s2 = Set(2, 0)
s3 = Set(3, 0)
s4 = Set(4, 0)
s5 = Set(5, 0)
s6 = Set(6, 0)
s7 = Set(7, 0)
s8 = Set(8, 0)
s9 = Set(9, 0)
s10 = Set(10, 0)
Merge (s1, s3)
Merge (s2, s4)
#
# 1 2
# ^ ^
# | |
# 3 4
#
Merge (s3, s5)
Merge (s4, s6)
#
# 1 2
# ^ ^
# | \ | \
# 3 5 4 6
#
Merge (s1, s6)
if __name__ == "__main__" :
main()
Output
Created set : 1 Rank : 0
Created set : 2 Rank : 0
Created set : 3 Rank : 0
Created set : 4 Rank : 0
Created set : 5 Rank : 0
Created set : 6 Rank : 0
Created set : 7 Rank : 0
Created set : 8 Rank : 0
Created set : 9 Rank : 0
Created set : 10 Rank : 0
Merging 1 & 3
Rank of : 1 = 1
Parent of : 1 = 1
Rank of : 3 = 0
Parent of : 3 = 1
Merging 2 & 4
Rank of : 2 = 1
Parent of : 2 = 2
Rank of : 4 = 0
Parent of : 4 = 2
Merging 3 & 5
Rank of : 3 = 1
Parent of : 3 = 1
Rank of : 5 = 0
Parent of : 5 = 1
Merging 4 & 6
Rank of : 4 = 1
Parent of : 4 = 2
Rank of : 6 = 0
Parent of : 6 = 2
Merging 1 & 6
Rank of : 1 = 2
Parent of : 1 = 1
Rank of : 6 = 0
Parent of : 6 = 1
#include<iostream>
using namespace std;
class Set {
public:
int data;
int rank;
Set * parent;
Set (int arg_data, int arg_rank) : data(arg_data), rank(arg_rank), parent(this) {
cout << "Created set : " << arg_data << " Parent : " << parent->data << " Rank : " << arg_rank << endl;
}
Set* FindParent (Set& );
void Merge (Set&, Set&);
};
// FindParent applies path compression to all the nodes in the search path of the parent
// without changing their ranks.
Set* FindParent (Set& s) {
if ( s.data != s.parent->data ) {
s.parent = FindParent (*(s.parent));
}
return s.parent;
}
// Merge operation makes use of heuristic union-by-rank.
void Merge (Set& a, Set& b) {
Set* parent_of_a = FindParent(a);
Set* parent_of_b = FindParent(b);
if ( parent_of_a->data != parent_of_b->data ) {
if ( a.rank < b.rank ) {
a.parent = parent_of_b;
b.rank += 1;
} else {
b.parent = parent_of_a;
a.rank += 1;
}
}
cout << "\nMerging " << a.data << " & " << b.data << endl;
cout << "Rank of : " << a.data << " = " << a.rank << endl;
cout << "Parent of : " << a.data << " = " << a.parent->data << endl;
cout << "Rank of : " << b.data << " = " << b.rank << endl;
cout << "Parent of : " << b.data << " = " << b.parent->data << endl;
}
int main() {
// Initially every node in a set has a rank 0 and is a parent of itself
Set s1(1, 0); // Data : 1, Rank : 0, Parent : 1
Set s2(2, 0);
Set s3(3, 0);
Set s4(4, 0);
Set s5(5, 0);
Set s6(6, 0);
Set s7(7, 0);
Set s8(8, 0);
Set s9(9, 0);
Set s10(10, 0);
Merge (s1, s3);
Merge (s2, s4);
/*
1 2
^ ^
| |
3 4
*/
Merge (s3, s5);
Merge (s4, s6);
/*
1 2
^ ^
| \ | \
3 5 4 6
*/
Merge (s1, s6);
return 0;
}
Output
Created set : 1 Parent : 1 Rank : 0
Created set : 2 Parent : 2 Rank : 0
Created set : 3 Parent : 3 Rank : 0
Created set : 4 Parent : 4 Rank : 0
Created set : 5 Parent : 5 Rank : 0
Created set : 6 Parent : 6 Rank : 0
Created set : 7 Parent : 7 Rank : 0
Created set : 8 Parent : 8 Rank : 0
Created set : 9 Parent : 9 Rank : 0
Created set : 10 Parent : 10 Rank : 0
Merging 1 & 3
Rank of : 1 = 1
Parent of : 1 = 1
Rank of : 3 = 0
Parent of : 3 = 1
Merging 2 & 4
Rank of : 2 = 1
Parent of : 2 = 2
Rank of : 4 = 0
Parent of : 4 = 2
Merging 3 & 5
Rank of : 3 = 1
Parent of : 3 = 1
Rank of : 5 = 0
Parent of : 5 = 1
Merging 4 & 6
Rank of : 4 = 1
Parent of : 4 = 2
Rank of : 6 = 0
Parent of : 6 = 2
Merging 1 & 6
Rank of : 1 = 2
Parent of : 1 = 1
Rank of : 6 = 0
Parent of : 6 = 1
class Set {
private int data;
private int rank;
Set parent;
Set (int arg_data, int arg_rank) {
data = arg_data;
rank = arg_rank;
parent = this;
System.out.println("Created set : " + arg_data + " Parent : " + parent.data + " Rank : " + arg_rank);
}
// FindParent applies path compression to all the nodes in the search path of the parent
// without changing their ranks.
static Set FindParent (Set s) {
if ( s.data != s.parent.data ) {
s.parent = FindParent (s.parent);
}
return s.parent;
}
// Merge operation makes use of heuristic union-by-rank.
static void Merge (Set a, Set b) {
Set parent_of_a = FindParent(a);
Set parent_of_b = FindParent(b);
if ( parent_of_a.data != parent_of_b.data ) {
if ( a.rank < b.rank ) {
a.parent = parent_of_b;
b.rank += 1;
} else {
b.parent = parent_of_a;
a.rank += 1;
}
}
System.out.println("\nMerging " + a.data + " & " + b.data);
System.out.println("Rank of : " + a.data + " = " + a.rank);
System.out.println("Parent of : " + a.data + " = " + a.parent.data);
System.out.println("Rank of : " + b.data + " = " + b.rank);
System.out.println("Parent of : " + b.data + " = " + b.parent.data);
}
public static void main (String[] args) {
// Initially every node in a set has a rank 0 and is a parent of itself
Set s1 = new Set(1, 0); // Data : 1, Rank : 0, Parent : 1
Set s2 = new Set(2, 0);
Set s3 = new Set(3, 0);
Set s4 = new Set(4, 0);
Set s5 = new Set(5, 0);
Set s6 = new Set(6, 0);
Set s7 = new Set(7, 0);
Set s8 = new Set(8, 0);
Set s9 = new Set(9, 0);
Set s10 = new Set(10, 0);
Merge (s1, s3);
Merge (s2, s4);
/*
1 2
^ ^
| |
3 4
*/
Merge (s3, s5);
Merge (s4, s6);
/*
1 2
^ ^
| \ | \
3 5 4 6
*/
Merge (s1, s6);
}
}
Output
Created set : 1 Parent : 1 Rank : 0
Created set : 2 Parent : 2 Rank : 0
Created set : 3 Parent : 3 Rank : 0
Created set : 4 Parent : 4 Rank : 0
Created set : 5 Parent : 5 Rank : 0
Created set : 6 Parent : 6 Rank : 0
Created set : 7 Parent : 7 Rank : 0
Created set : 8 Parent : 8 Rank : 0
Created set : 9 Parent : 9 Rank : 0
Created set : 10 Parent : 10 Rank : 0
Merging 1 & 3
Rank of : 1 = 1
Parent of : 1 = 1
Rank of : 3 = 0
Parent of : 3 = 1
Merging 2 & 4
Rank of : 2 = 1
Parent of : 2 = 2
Rank of : 4 = 0
Parent of : 4 = 2
Merging 3 & 5
Rank of : 3 = 1
Parent of : 3 = 1
Rank of : 5 = 0
Parent of : 5 = 1
Merging 4 & 6
Rank of : 4 = 1
Parent of : 4 = 2
Rank of : 6 = 0
Parent of : 6 = 2
Merging 1 & 6
Rank of : 1 = 2
Parent of : 1 = 1
Rank of : 6 = 0
Parent of : 6 = 1