CODEWITHSUNDEEP
algorithmquick-union
template boy
template boy

Reputation: 10480

Weighted quick-union explanations

I need help understanding the explanations given by the questions about weighted quick union:

Which of the following id[] array(s) could be the result of running the weighted quick union algorithm on a set of 10 items? Check all that apply.

Recall that our weighted quick union algorithm uses union by size (number of nodes) (and not union by height).

Incorrect: 9 1 7 3 4 9 6 7 8 9
Explanation: 9-5 7-2 5-0

Incorrect: 2 2 2 2 5 1 2 3 1 2
Explanation: 2-9 3-7 9-3 5-4 0-2 1-8 8-4 4-9 8-6

Correct: 9 9 3 4 9 4 9 9 4 2
Explanation: The id[] array contains a cycle: 2->3->4->9->2

Correct: 0 2 3 0 0 2 2 9 3 0
Explanation: Size of tree rooted at parent of 2 < twice the size of tree rooted at 2

Correct: 0 4 6 7 4 1 5 1 7 3
Explanation: Height of forest = 4 > lg N = lg(10)

Upvotes: 5

Views: 7503

Answers (2)

yaodong
yaodong

Reputation: 404

BTW, The explanation given in the fourth problem makes no sense to me

Because the depth of nodes only in the smaller tree will now increase by one, and the depth of the deepest node in the combined tree can only be at most one deeper than the deepest node before the trees were combined. The total number of nodes in the combined tree is therefore at least twice the number in the smaller subtree. source

Upvotes: 1

Vinayak Garg
Vinayak Garg

Reputation: 6616

You haven't given full context, but I will try to answer from what I know about weighted union.

Do I have to look at every element to figure out if there is a cycle?

No. That would defeat the purpose of quick-union. A cycle indicates that the union operation has not been implemented properly. And there should be no cycle at any time.

How do I know the size of a tree?

Initially all the trees are of size 1. In the union operation we sum the size of the 2 trees who are being joined. And we track the size through an array (say SZ[]). The given tree's size is updated at the roots offset in the array (SZ[root(i)]).

How do I know the height of a forest?

That has to be tracked too. Initially all the trees are of height 1. When you join 2 trees - say A & B, and you make A's root as the new root. Then height of joined tree will be max(A.height, B.height+1).

Upvotes: 5

Related Questions