Menu
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 of10items? 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-0Incorrect:
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-6Correct:
9 9 3 4 9 4 9 9 4 2
Explanation: Theid[]array contains a cycle:2->3->4->9->2Correct:
0 2 3 0 0 2 2 9 3 0
Explanation: Size of tree rooted at parent of2 <twice the size of tree rooted at2Correct:
0 4 6 7 4 1 5 1 7 3
Explanation: Height of forest =4 > lg N = lg(10)
415
Weighted quick-union by height. Solution. A union operation between elements in different trees either leaves the height unchanged (if the two tree have different heights) or increase the height by one (if the two tree are the same height). You can prove by induction that that the size of the tree is at least 2^height.
Weighted Union. A low-cost approach to reducing the height is to be smart about how two trees are joined together. One simple technique, called the weighted union rule, joins the tree with fewer nodes to the tree with more nodes by making the smaller tree's root point to the root of the bigger tree.
First improvement: weighted tree In the weighted quick-union, we examine the size of two trees and make sure that we only link the smaller tree under the larger tree. By applying this method, we can guarantee that the tree will not grow too tall. Keep tracking the size of the tree (numbers of objects).
Quick-union might slightly be faster in certain scenarios depending on the nature of the input. This is because with Quick-find, the union operation will always have a computational complexity greater than or equal to N. This is not the case for Quick-union, the find operation can perform computations less than N.
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).
111
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
