Saturday, June 21, 2014

Size of tree rooted at parent of

Have you attempted the exercise but didn't the maximum due a mistake "size of tree rooted at parent of " explanation does not convince you?

Well, look at this thread on coursera https://class.coursera.org/algs4partI-005/forum/thread?thread_id=123

Basically checking that the depth of the three is below log_2 (N) is not enough to be sure the tree comes from a weighted quick union algorithm!

The final tree must be consistent with the principle of weighted quick union, i.e. that you attach the bigger tree to the smaller one. 
In the final tree the biggest subtree you see is NOT a child of any other smaller subtree! Once again, check the thread, make a drawing and you'll understand what I mean.

Look at the thread. Draw a picture and convince yourself.

No comments:

Post a Comment