CHAPTER 8
The Disjoint Set Class
8.1 We assume that unions operated on the roots of the trees containing the arguments. Also, in case of ties, the
8.2 In both cases, have nodes 16 and 0 point directly to the root.
8.4 Claim: A tree of height h has at least 2h nodes. The proof is by induction. A tree of height 0 clearly has at
least 1 node, and a tree of height 1 clearly has at least 2. Let T be the tree of height h with fewest nodes. Thus
8.5 We are given T(n) = n/f(n) * T(f(n)) + n
and then substitute this expression for T(f(f(n))) into the most recent formula we have for T(n).
T(n) = n/f(f(n)) * [ f(f(n))/f(f(f(n))) * T(f(f(f(n)))) + n ] + n2/f(n) + n
= n/f(f(f(n))) * T(f(f(f(n))) + n2/f(f(n)) + n2/f(n) + n
And, next we expand T(f(f(f(n)))) using the definition of T.
T(f(f(f(n)))) = f(f(f(n)))/f(f(f(f(n)))) * T(f(f(f(f(n))))) + n
s*n2 + (c+1)n. In other words, T(n) is a polynomial of degree 2, or T(n) = O(n2).
8.6 All answers are O(M) because in all cases alpha(M N) = 1.
8.8 It is easy to see that this invariant is maintained in each disjoint set as the algorithm proceeds.
8.10 (a) When we perform a union we push onto a stack the two roots and the old values of their parents. To
implement a deunion, we only have to pop the stack and restore the values. This strategy works fine in the
8.11 We assume that the tree is implemented with links instead of a simple array. Thus find will return a reference
instead of an actual set name. We will keep an array to map set numbers to their tree nodes. union and find
are implemented in the standard manner. To perform remove(x), first perform a find(x) with path
compression. Then mark the node containing x as vacant. Create a new one-node tree with x and have it
8.12 Suppose there are u union and f find operations. Each union costs constant time, for a total of u. A find costs
one unit per vertex visited. We charge, as in the text, under the following slightly modified rules:
(A) the vertex is a root or child of the root
8.14 For each vertex v, let the pseudorank Rv be defined as
log v
S
, where Sv is the number of descendents
(including itself) of v in the final tree, after all union operations are performed, ignoring path compression.
8.16 This is most conveniently implemented without recursion and is faster because, even if full path compression
is implemented nonrecursively, it requires two passes up the tree. This requires only one. We leave the