Minimum AVL node tree

Question

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

+2

Chin Oct 20 '12 at 4:21

3 answers

beNick · Answer 1 · 2013-07-15T15:29:48+0000

n(h) - the minimum number of nodes of the AVL tree with height h, then:

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

Rana priyanka · Answer 2 · 2016-01-13T15:55:09+0000

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

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 expression for these known 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

NullPoite · Answer 3 · 2012-10-20T04:25:12+0000

AVL h 2 (h/2) -1 .

.. n (h) - AVL h.

n (1) = 1 n (2) = 2. , h = 1 h = 2.