5

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)

  • How am I supposed to know the actual union operations as shown by the first two problems?
  • Do I have to look at every element to figure out if there is a cycle?
  • How do I know the size of a tree? (BTW The explanation given in the fourth problem makes no sense to me)
  • How do I know the height of a forest?
Vinayak Garg
  • 6,518
  • 10
  • 53
  • 80
template boy
  • 10,230
  • 8
  • 61
  • 97

2 Answers2

5

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).

Vinayak Garg
  • 6,518
  • 10
  • 53
  • 80
  • If the question just gives me the array (`2 4 5 2...`), don't I have to look at each element until I find cycle? Otherwise how do I find one? – template boy Sep 12 '14 at 18:40
  • @templateboy: Yes starting from each element you can check for any and all the cycles. But like I answered, while doing union one should check if 2 disjoint sets have different roots or not, before joining them. – Vinayak Garg Sep 12 '14 at 18:51
  • Let `A.height = x` and `B.height = 4`. Now if you join `B` as child of `A` then you need to compare 5 with x. That extra 1 is A's root. – Vinayak Garg Sep 12 '14 at 19:15
1

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

yaodong
  • 404
  • 4
  • 12