Disjoint Set Operations
Introduction
Forests are used to represent sets. Assume the elements of the sets are the numbers 1, 2, 3, …, n.
Sets are pairwise disjoint. That is, if Si and Sj (i ≠ j) are two sets, then there is no common element in both Si and Sj.
Example: When n = 10, the elements can be partitioned into 3 disjoint sets:
S1 = {1, 7, 8, 9}, S2 = {5, 2, 10}, S3 = {3, 4, 6}
Each set is represented by a tree.
Links go from children to parent.
Operations on sets
The operations we perform on sets are:
Disjoint set union: If Si and Sj are two disjoint sets, then Si ∪ Sj = all elements x such that x is in Si or Sj.
Example: S1 ∪ S2 = {1, 7, 8, 9, 2, 5, 10}
Find(i): Given the element
i, find the set containingi.Example: Find(4) = S3