申論題

13. (15 points) A disjoint-set data structure supports two operations. One is UNION(z,y), which merges the two roots of the trees containing a and y. The other is FIND(z), which returns the root of the tree containing 2. Union-by-beight is a union heuristic, which keeps track of the heights of the trees to attach the shorter tree to the root of the taller tree.

(b) (6 points) The union-by-height heuristic preveuts the height of a tree froin growing linearly. Consider another heuristic, called union-by-descendant, which always attaches the tree with fewer descen- dants to the root of the tree with mnore descendants. Suppose that path compression is not applied. Which of the two heuristics is asymptotically better? Why?