寻找AVL树的最小“内部”节点？

Question

我知道如何使用公式n( h ) = n(h-1) + n(h-2) +1找到高度为h的AVL树(包括外部节点)中的最小节点数，但我想知道是否有一个公式可以仅找到高度为h的AVL树的最小内部节点。

所以对于n(3) = 4，如果我们只计算内部节点。n(4) = 7，如果我们只计算内部节点。我可以画出它并计算内部节点，但当你得到更大的AVL树时，它会变得一团糟。

我似乎找不到任何关于这方面的东西，试图找到一个具有一致答案的模式只会导致数小时的沮丧。提前谢谢。

Answer 1

是的，有一个很好的方法来计算它。让我们从两个最简单的AVL树开始，它们的阶数分别为0和1：

*    *
     |
     *

第一个树没有内部节点，第二个树有一个内部节点。这为我们提供了递归关系的基本情况：

• I(0) = 0
• I(1) = 1

从这里，我们注意到，在n+2阶的AVL树中获得最少内部节点的方法是选择n阶和n+1阶的两棵树作为子树(最小化节点的数量)，它们具有尽可能少的内部节点。结果树的内部节点数量将等于两个子树中的内部节点数量，加上一个用于新根的节点。这意味着

• I(n+2) = I(n) + I(n+1) + 1.

应用这个递归给出我们的序列

0、1、2、4、7、12、20等。

嘿-我们以前在什么地方见过这个吗？我们有!每一项加一个就给了我们

1、2、3、5、8、13、21等

这是斐波那契数列，下移了两个位置！所以我们的假设是

I(n) = F(n+2) -1

你可以通过对n的归纳来证明这一点。

这里有一种不同的方法来得出这个结果。假设你取了一棵高度为n的AVL树，去掉了所有的叶子。现在剩下一个高度为n-1的AVL树(证明这一点！)，该树中的所有剩余节点都是原始树的内部节点。在高度为n的AVL树中，节点的最小可能数量是F(n+2)-1，与我们的结果相匹配。