CODEWITHSUNDEEP
time-complexityavl-tree
AskMath
AskMath

Reputation: 425

What is the complexity time for calculating the height of avl tree?

given avl tree, what is the time-complexity of "best" algorithm for calculate the height of the tree?

I know that the height of the tree is log(n) given that exists n elements in the tree. But how can I calculate the height?

Upvotes: 1

Views: 1746

Answers (1)

Md Johirul Islam
Md Johirul Islam

Reputation: 5162

Let's say the number of nodes that make a tree of height h is N_h. So the height of the tree having left child as the root is h-1 having N_(h-1) nodes and the right subtree can have minimum height of h - 2 with N_(h-2) nodes as the AVL tree is balanced ( height difference of left and right subtree cannot be more than 1). We can write the formula as following

N_h = N_(h -1) + N_(h -2) + 1           (i)

The base cases are N_1 = 1 and N_2 = 2 And

N_(h−1) = N_(h−2) + N_(h−3) + 1           (ii)

Putting (ii) in equation (i) we get

N_h = N_(h−2) + N_(h−3) + 1  + N_(h -2) + 1 
=> N_h = 2*N_(h−2) + N_(h−3) + 2 
=> N_h > 2*N_(h-2)
=> N_h > 2^(h/2)
=> log(N_h) > log(2^(h/2))
=> 2log(N_h) > h
=> h = O(log(N_h)

Replacing N_h by n we can write

h = O(lgn)

Upvotes: 1

Related Questions