Minimum number of node in AVL tree?

Question

I know the formula of finding minimum number of node in a AVL tree is

S(h) = S(h-1) + S(h-2) + 1

However, I don't really get how to use this function, say if we have a AVL height of 6. The answer tells me that Minimum = 7 + 4 + 1 =12. But how do you get this number? I mean when you plug in 6 isn't it (6-1) + (6-2) + 1?

Can anyone explain to me how to solve this? My teacher haven't talk about this yet but I really want to figure this out myself in order to be prepared for the test next week.

Answer 1

In S(h) = S(h-1) + S(h-2) + 1,

S(h) is a recursive function/formula. A recursive function calls itself (in a smaller or simpler way) inside its body.

Note that a recursive function must have some base cases, in this case:

S(1) = 0
S(2) = 1

So let's say h = 6, then S(h = 6) will be (just replacing):

S(6) = S(6-1) + S(6-2) + 1
S(6) = S(5) + S(4) + 1 
S(6) = 2*S(4) + S(3) + 1 + 1
S(6) = 2*(S(3) + S(2) + 1) + S(3) + 2
S(6) = 3*S(3) + 2*S(2) + 4
S(6) = 3*(S(2) + S(1) + 1) + 2*S(2) + 4
S(6) = 5*S(2) + 3*S(1) + 7
S(6) = 5*1 + 3*0 + 7
S(6) = 12

Answer 2

The minimum number of nodes in an AVL tree for a tree with a height of 6 is not 20, it should be 33.

The following equation should demonstrate the recursive call of the N(h) function.

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

Because AVL tree is balanced BST, for each height h, we must form a h-1 and h-2 tree before moving forward to construct a height h AVL tree by adding another node. Thus, formula N(h)=1+N(h-1)+N(h-2)

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

I hope this may help you

Answer 3

For the function N(h) = 1 + N(h - 1) + N(h - 2)

MIT Recitation 04 states the base cases for this recursive function are: N(1) = 1; N(2) = 2

therefore

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

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

N(5) = 1 + N(4) + N(3) = 1 + 7 + 4 = 12

N(6) = 1 + N(5) + N(4) = 1 + 12 + 7 = 20

N(7) = 1 + N(6) + N(5) = 1 + 20 + 12 = 33

N(8) = 1 + N(7) + N(6) = 1 + 33 + 20 = 54

and so on, just keep plugging the numbers in from previous answers...

https://courses.csail.mit.edu/6.006/spring11/rec/rec04.pdf