CODEWITHSUNDEEP
data-structures
Chin
Chin

Reputation: 20675

AVL tree minimum node

What is the minimum number of nodes in an AVL tree of height h? I did some reseach on the Internet but they are all so confusing.

Upvotes: 4

Views: 17650

Answers (3)

Rana Priyanka
Rana Priyanka

Reputation: 131

the minimum number of nodes in an AVL tree for a tree with a height h. The following equation should demonstrate the recursive call of the N(h) function.

formula N(h)=1+N(h-1)+N(h-2)

Since we know that N(0)=1 ,N(1) = 2, N(2) = 4, for example: we can reduce the following equation to these knowns for h = 6.

N(3)=1+N(3-1)+N(3-2)=1+N(2)+N(1)=7

N(4)=1+N(4-1)+N(4-2)=1+N(3)+N(2)=12

N(5)=1+N(5-1)+N(5-2)=1+N(4)+N(3)=20

N(6)=1+N(6-1)+N(6-2)=1+N(5)+N(4)=33

Upvotes: 4

beNick
beNick

Reputation: 91

n(h) be the minimum number of nodes of an AVL tree of height h, then:

n(0)=1, n(1)=2
n(h)= 1+n(h-1)+n(h-2)

Upvotes: 9

NullPoiиteя
NullPoiиteя

Reputation: 57322

An AVL tree of height h has at least 2(h/2)-1 internal nodes.

Proof: Let n(h) be the minimum number of internal nodes in an AVL tree of height h.

n(1)=1 and n(2)=2. So the lemma holds for h=1 and h=2.

Upvotes: 0

Related Questions