Description
Consider the following restricted version of the DISJOINT SETS ADT on the universe of
elements {i | 1 ≤ i ≤ k2
k}. (In other words, suppose that MAKESET(i) has been performed for all
1 ≤ i ≤ k2
k and no other MAKESET operations are performed.) The supported operations are:
• FINDSET(x), which always returns the representative of the set that contains element x, and
• LINK(x, y), which combines the sets whose representatives are x and y and returns the
representative of the new set, but only when x 6= y and either x and y are representatives
of sets each with at most k elements (small sets) or x and y are representatives of sets each
with more than k elements (large sets). If x = y or one of x and y is the representative of a
small set and the other is a representative of a large set, then the operation has no effect and
it returns nil.
Assume the existence of a data structure S on this universe that represents a collection of disjoint
sets, each of size at most k, and supports the usual findset(x) and link(x, y) operations in worst
case constant time (independent of k).
Describe a data structure for this restricted version of the DISJOINT SETS ADT so that the
amortized cost of all FINDSET and LINK operations is constant. Use linked lists of nodes with
representative pointers, where each node represents a set containing between k+ 1 and 2k elements.
1. Describe the representation of your data structure and how it is initialized.
2. Draw a picture of your data structure when k = 2 and the sets are {1,7} and {2,3,4,5,6,8}.
In red, show the representative in S of each element of the universe.
3. Explain how to perform FINDSET(x) in your data structure.
4. Explain how to perform LINK(x, y) in your data structure, where x and y are the representatives of their respective sets.
5. Use the accounting method to prove that the amortized cost of all FINDSET and LINK
operations is constant.
1