The uptrees used to represent sets in the union-find algorithm can be stored in two n-element arrays. The up array stores the parent of each node (or -1 if it has no parent). The weight array stores the number of items in a set if the node is the representative node of a set (else the weight entry for the node does not matter and can be anything).

The following shows a collection of sets containing the numbers 1 through 12, without the weight array filled in:

up -1 10 -1 9 1 1 11 -1 7 11 -1 1

weight

1 2 3 4 5 6 7 8 9 10 11 12

a) Draw a picture of the uptrees represented by the data in the up array shown above.

d) Suppose we did not keep the weight array updated as operations are performed. As you did in part (a), the algorithm could compute weights as needed. Would this asymptotically slow down union operations that use union-by-weight?

e) Show the result of performing the operation find(4) with path compression by doing both of the following:

Redraw below any uptrees (from part (a)) that change as a result.

Update the array representation as appropriate by drawing a single slash (\/") through any numbers that change and writing the new number next to it.