avl树中最小节点数的证明

Question

如何证明高度为h的avl树中最小节点数为(5+2*5^(1/2))*((((1+5^(1/2))/2)^h) + (5-2*5^(1/2))*((((1-5^(1/2))/2)^h)-1

Answer 1

假设高度h处的根节点有两个子树。这两个子树中的一个高度必须是h-1。AVL树的结构迫使另一个子树的高度至少为h-2。因此，一个子树具有最小的可能节点数，另一个子树具有最大的可能节点数。得到如下递推规则: n(0) = 1，n(1) = 2，n( h ) = n(h-1)+n(h-2)+1，其中n(h)是高度为h的最小节点数。

这种重复非常接近Fibonacci序列。通过计算Fibonacci序列的精确公式，得到F(n) = (φ^n - hat(φ) ^n)/2(5)，其中φ= (1+sqrt(5))/2，hat(φ)= (1-sqrt(5))/2。

这应该会给出一些如何进行的想法。我认为在这里做一些数学运算会让你找到答案。