Consider the program:

Assume that the disjoint sets data structure is implemented as disjoint trees with union by rank heuristic.

Compute the product of the heights of the resulting trees after executing the code. For example, for a forest consisting of four trees of height 1, 2, 3, 1 the answer would be 6. (Recall that the height of a tree is the number of edges on a longest path from the root to a leaf. In particular, the height of a tree consisting of just one node is equal to 0.)

Transcribed Image Text:

1 2 3 4 5 6 7 8 9 10 11 for i from 1 to 12: MakeSet(i) Union (2, 10) Union (7,5) Union (6, 1) Union (3, 4) Union (5, 11) Union (7, 8) Union (7, 3) Union (12, 2) Union (9, 6) 1 2 3 4 5 6 7 8 9 10 11 for i from 1 to 12: MakeSet(i) Union (2, 10) Union (7,5) Union (6, 1) Union (3, 4) Union (5, 11) Union (7, 8) Union (7, 3) Union (12, 2) Union (9, 6)

Answer rating: 100% (QA)

Union by rank attaches the tree with low rank to the tree with larger rank If both the trees have sa... View the full answer