问AVL树的最小节点数？

EN

在S(h) = S(h-1) + S(h-2) + 1中，

S(h)是函数/公式。递归函数(以更小或更简单的方式)在其体内调用自己。

请注意，递归函数必须有一些基本情况，在本例中：

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

因此，假设是h = 6，那么S(h = 6)将是(只是替换)：

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

对于高度为6的树，AVL树中的最小节点数不是20个，应该是33个。

下面的方程应该演示N(h)函数的递归调用。

由于我们知道N(0)=1，N(1) = 2，N(2) = 4，我们可以将下列方程简化为h= 6的这些已知数。

由于AVL树是平衡的BST树，对于每一个高度h，在向前移动之前，我们必须形成一个h-1和h-2树，通过添加另一个节点来构造一个each树。因此，公式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

我希望这能帮到你

对于函数N(h) =1+N(h-1)+N(h-2)

麻省理工学院朗诵04陈述这个递归函数的基本情况是: N(1) = 1；N(2) =2

因此

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

等等，只要把先前答案中的数字插进去.

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