What is the order of this Union in the Rank chart?

I am having trouble understanding the following diagram:

alt text http://img251.imageshack.us/img251/9264/ranku.jpg

Why is A linked to D instead of B? Why is C linked to F instead of D?

+4
source share
1 answer

The rule of union by rank is to attach the smallest tree to the root of the largest tree.

At the first stage, A merges with D (this is just an example, I think you could do it any other way), so after union(A, D) you can have either A_0 -> D_1 , or D_O -> A_1 , since 2 singleton trees have the same rank, which you randomly select, in this case D , to be the root.

+5
source

All Articles