The Disjoint Set ADT Notice that we do not perform any operations comparing the relative values of elements,but merely require knowledge of their location. For this reason,we can assume that all the elements have been numbered sequentially from 1 to M.Thus,initially we have s=for /1 through M
The Disjoint Set ADT ◼ Notice that we do not perform any operations comparing the relative values of elements, but merely require knowledge of their location. ◼ For this reason, we can assume that all the elements have been numbered sequentially from 1 to N. Thus, initially we have Si={i} for i=1 through N
The Disjoint Set ADT Our second observation is that the name of the set returned by Find is actually fairly arbitrary.All that really matters is that Find(a)=Find(b)if and only if a and b are in the same set. Thus,one idea might be to use a tree to represent each set,since each element in a tree has the same root.Therefore,the root can be used to name the set
The Disjoint Set ADT ◼ Our second observation is that the name of the set returned by Find is actually fairly arbitrary. All that really matters is that Find(a)=Find(b) if and only if a and b are in the same set. ◼ Thus, one idea might be to use a tree to represent each set, since each element in a tree has the same root. Therefore, the root can be used to name the set