21.3 Disjointset forests
21.31
Redo Exercise 21.22 using a disjointset forest with union by rank and path compression.
1
/ / \ \
2 3 5 9
 / \ / \ \
4 6 7 10 11 13
  / \
8 12 14 15

16
21.32
Write a nonrecursive version of $\text{FINDSET}$ with path compression.
To implement $\text{FINDSET}$ nonrecursively, let $x$ be the element we call the function on. Create a linked list $A$ which contains a pointer to $x$. Each time we most one element up the tree, insert a pointer to that element into $A$. Once the root $r$ has been found, use the linked list to find each node on the path from the root to $x$ and update its parent to $r$.
21.33
Give a sequence of $m$ $\text{MAKESET}$, $\text{UNION}$, and $\text{FINDSET}$ operations, $n$ of which are $\text{MAKESET}$ operations, that takes $\Omega(m\lg n)$ time when we use union by rank only.
Suppose that $n' = 2k$ is the smallest power of two less than $n$. To see that this sequences of operations does take the required amount of time, we'll first note that after each iteration of the for loop indexed by $j$, we have that the elements $x_1, \dots, x_{n'}$ are in trees of depth $i$. So, after we finish the outer for loop, we have that $x_1, \dots, x_{n'}$ all lie in the same set, but are represented by a tree of depth $k \in \Omega(\lg n)$. Then, since we repeatedly call $\text{FINDSET}$ on an item that is $\lg n$ away from its set representative, we have that each one takes time $\lg n$. So, the last for loop alltogther takes time $\Omega(m \lg n)$.
for i = 1 to n
MAKESET(x[i])
for i = 1 to k
for j = 1..n'  2^{i = 1} by 2^i
UNION(x[i], x[i + 2^{j  1}])
for i = 1 to m
FINDSET(x[1])
21.34
Suppose that we wish to add the operation $\text{PRINTSET}(x)$, which is given a node $x$ and prints all the members of $x$'s set, in any order. Show how we can add just a single attribute to each node in a disjointset forest so that $\text{PRINTSET}(x)$ takes time linear in the number of members of $x$'s set and the asymptotic running times of the other operations are unchanged. Assume that we can print each member of the set in $O(1)$ time.
In addition to each tree, we'll store a linked list (whose set object contains a single tail pointer) with which keeps track of all the names of elements in the tree. The only additional information we'll store in each node is a pointer $x.l$ to that element's position in the list.
 When we call $\text{MAKESET}(x)$, we'll also create a new linked list, insert the label of $x$ into the list, and set $x.l$ to a pointer to that label. This is all done in $O(1)$.
 $\text{FINDSET}$ will remain unchanged.
 $\text{UNION}(x, y)$ will work as usual, with the additional requirement that we union the linked lists of $x$ and $y$, since we don't need to update pointers to the head, we can link up the lists in constant time, thus preserving the runtime of $\text{UNION}$.
 Finally, $\text{PRINTSET}(x)$ works as follows: first, set $s = \text{FINDSET}(x)$. Then print the elements in the linked list, starting with the element pointed to by $x$. (This will be the first element in the list). Since the list contains the same number of elements as the set and printing takes $O(1)$, this operation takes linear time in the number of set members.
21.35 $\star$
Show that any sequence of $m$ $\text{MAKESET}$, $\text{FINDSET}$, and $\text{LINK}$ operations, where all the $\text{LINK}$ operations appear before any of the $\text{FINDSET}$ operations, takes only $O(m)$ time if we use both path compression and union by rank. What happens in the same situation if we use only the pathcompression heuristic?
Clearly each $\text{MAKESET}$ and $\text{LINK}$ operation only takes time $O(1)$, so, supposing that $n$ is the number of $\text{FINDSET}$ operations occuring after the making and linking, we need to show that all the $\text{FINDSET}$ operations only take time $O(n)$.
To do this, we will ammortize some of the cost of the $\text{FINDSET}$ operations into the cost of the $\text{MAKESET}$ operations. Imagine paying some constant amount extra for each $\text{MAKESET}$ operation. Then, when doing a $\text{FINDSET}(x)$ operation, we have three possibilities:
 First, we could have that $x$ is the representative of its own set. In this case, it clearly only takes constant time to run.
 Second, we could have that the path from $x$ to its set's representative is already compressed, so it only takes a single step to find the set representative. In this case also, the time required is constant.
 Third, we could have that $x$ is not the representative and it's path has not been compressed. Then, suppose that there are k nodes between $x$ and its representative. The time of this $\text{FINDSET}$ operation is $O(k)$, but it also ends up compressing the paths of $k$ nodes, so we use that extra amount that we paid during the $\text{MAKESET}$ operations for these $k$ nodes whose paths were compressed. Any subsequent call to find set for these nodes will take only a constant amount of time, so we would never try to use the work that amortization amount twice for a given node.