Disjoint Sets:
Set Representation:

 An array can be used to store parent of each element
 The ith element of this array represents the tree node that contains the element I and it gives the parent of that element
 Root node has a parent 1
 An array P[1:n] can be taken for all n elements in the forest
 Element at the root node is taken as the name of the set
Example: n=11, 4 sets S1 = {1, 7, 10, 11}, S2 = {2, 3, 5, 6}, S3 = {4, 8} and S4 = {9}
UNIONFIND Algorithms:
Union:
Find:
In a worstcase scenario SimpleUnion() and SimpleFind() perform badly. Suppose we start with the single element sets {1},{2},…,{n} , then, execute the following sequence of unions and finds UNION(1,2), UNION(2,3),…,UNION(n –1,n)
FIND(1),FIND(2),…,FIND(n).
This sequence results in a skewed tree
Time complexity for 1 union = 1
Time complexity for n1 union = n1
Therefore Tall unions = O(n)
Time complexity for 1 find = i
Time complexity for n find = 1+2+….+ n1 + n = n(n+1)/2
Therefore Tall finds = O(n^{2})
Weighted Union:


 Simple Union leads to high time complexity in some cases
 Weighted union is a modified union algorithm with weighting rule
 Widely used to analyze the time complexity of an algorithm in average case
 Weighted union deals with making the smaller tree a subtree of the larger
 If the no.of nodes in the tree with root i is less than the no.of nodes in the tree with root j, then make j the parent of I, otherwise make i the parent of j
 Count of nodes can be placed as a negative number in the P[i] value of the root i

Collapsing Find:
 SimpleFind() leads to high time complexity in some cases
 CollapsingFind() is a modified version of SimpleFind()
 If j is a node on the path from i to its parent and P[i]!= root, then set j to root