java - AVL树中的最小节点数？

Question

我知道在 AVL 树中查找最小节点数的公式是

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

但是，如果我们的 AVL 高度为 6，我真的不知道如何使用这个函数。答案告诉我 Minimum = 7 + 4 + 1 =12。但是你如何得到这个数字呢？我的意思是，当您插入 6 时，不是 (6-1) + (6-2) + 1 吗？

谁能告诉我如何解决这个问题？我的老师还没有谈到这个，但我真的很想自己解决这个问题，以便为下周的考试做准备。

Answer 1

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

S(h) 是 recursive function/formula .递归函数在其主体内调用自身(以更小或更简单的方式)。

注意递归函数必须有一些基本情况，在这种情况下:

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