AVL树中的最小节点数？

Question

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

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

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

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

原文由 user2913922 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在 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

原文由 Christian Tapia 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

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

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

由于我们知道 N(0)=1 ,N(1) = 2, N(2) = 4，我们可以将以下等式简化为 h = 6 的已知数。

因为AVL树是平衡BST，对于每一个高度h，我们必须先形成一个h-1和h-2树，然后再通过添加另一个节点来构建一个高度h的AVL树。于是，公式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

我希望这可以帮助你

原文由 Rana Priyanka 发布，翻译遵循 CC BY-SA 4.0 许可协议