Disjointed-sets-forest Why is the heigth of a tree with n elements log n?

11 views Asked by At

I was implementing the disjoited-sets-forest structure using the cormens algorithms book. I found that after the implementation of Union-by-rank we make sure that the three heigth stays log n if we have n nodes.

But since if two trees have different rank they just get merged (with Union and all that comes with it), if I merge a tree, for example of 3/4 elements, with a single node n times, doesn't it stay of heigth 2?

For example

           3                     3 
          / \     Union 4 ->   / | \    and so on n times
         2   5                2  5  4 
0

There are 0 answers