證明節點的AVL樹的最小數目的

Question

我如何證明節點中的高度ħ 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樹的結構迫使另一個子樹具有（0）= 1，n（1）= 1，因此一個子樹的節點數量最少，另一個節點的節點數量最多，因此我們得到下面的遞歸規則： 2，n（h）= n（h-1）+ n（h-2）+1其中n（h）是最小值um高度= h處的節點數。

這種復發非常接近斐波那契序列。計算Fibonacci序列的精確公式可得F（n）=（φ^ n-hat（φ）^ n）/ sqrt（5）其中φ=（1 + sqrt（5））/ 2和hat （1-SQRT（5））/ 2。

這應該給一些想法如何繼續。 我認爲在這裏做一些數學會讓你找到答案。