Minimum number of node in AVL tree?
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
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