ex 1.5.13 assign to the root of a heavier tree about algorithms-sedgewick-wayne HOT 2 CLOSED

Consider a union of trees A and B that form tree C. Also consider that tree A is smaller than B.
With your idea we would have a tree that is more compressed, with all nodes having C’s root as parent. In the original approach we would have all nodes from B pointing to C’s root and the nodes from A pointing to A’s original root, which now points to C’s root. So we have one less level for A’s nodes, which is good.
On the other hand, to do that, we have to first find both roots (to know their sizes), the same way as the original approach, and then go through all the nodes on tree A to update their pointers to B’s root (instead of just updating the parent of A’s root to B’s root).
So we end up with a more compressed tree but we also have to do extra operations (up to N / 2) to go over the smallest tree’s nodes and update their parents.
This makes the union() operation have linear runtime instead of logarithmic runtime, which would only be useful in an application where most of the operations are find() operations and union() is not frequently needed.

from algorithms-sedgewick-wayne.

Actually, since the exercise mentions that the combination of weighted quick-union with path compression results in operations with an amortized cost bounded by the inverse Ackermann function, the resulting tree heights would always be small. So the original approach still seems to be the best option in all cases.

from algorithms-sedgewick-wayne.