CODEWITHSUNDEEP
data-structuresdisjoint-sets
blockerinho
blockerinho

Reputation: 1

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

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

Upvotes: 0

Views: 17

Answers (0)

Related Questions