In the depth-determination problem, we maintain a forest F = (Ti) of rooted trees under three operations:
• MAKE-TREE (v) creates a tree whose only node is v.
• FIND-DEPTH (v) returns the depth of node v within its tree.
• GRAFT(r, v) makes node r, which is assumed to be the root of a tree, become the child of node v, which is assumed to be in a different tree than r but may or may not itself be a root.
The key idea is to maintain in each node v a "pseudo distance" d[v], which is defined so that the sum of the pseudo distances along the path from v to the root of its set Si equals the depth of v in Ti. That is, if the path from v to its root in Si is v0, v1, ..., vk, where v0 = v and vk is Si's root, then the depth of v in Ti is .
b. Give an implementation of MAKE-TREE.
c. Show how to modify FIND-SET to implement FIND-DEPTH. Your implementation should perform path compression, and its running time should be linear in the length of the find path. Make sure that your implementation updates pseudo distances correctly.
d. Show how to implement GRAFT(r, v), which combines the sets containing r and v, by modifying the UNION and LINK procedures. Make sure that your implementation updates pseudo distances correctly. Note that the root of a set Si is not necessarily the root of the corresponding tree Ti.
e. Give a tight bound on the worst-case running time of a sequence of m MAKE-TREE, FIND-DEPTH, and GRAFT operations, n of which are MAKE-TREE operations.
d. Show how to implement GRAFT(r, v), which combines the sets containing r and v, by modifying the UNION and LINK procedures. Make sure that your implementation updates pseudo distances correctly. Note that the root of a set Si is not necessarily the root of the corresponding tree Ti.
e. Give a tight bound on the worst-case running time of a sequence of m MAKE-TREE, FIND-DEPTH, and GRAFT operations, n of which are MAKE-TREE operations.