なぜ高さhのAVLツリーが最小数のノード= F（h + 2） - 1を有するか

Question

質問：なぜ高さhのAVLツリーは、ノード= F ）-1ここで、F（h）はh thフィボナッチ数ですか？

Iが高さhのAVLツリー内のノードの最小数の再発のように書くことができることを知っている：N（H）= N（H-1）+ N（H-2）+ 1

私はなぜN（h）= F（h + 2） - 1であるのか知りたいのですが、明示的に両方の再発を解決して数字を差し込む必要がありますか？N（h）= N（h-1）+ N（h-2）+ 1はフィボナッチ系列と非常に似ているので、フィボナッチ系列から直接行う別の方法があると仮定します。

Answer 1

より広範な回答hereが提供されていますが、これは、フィボナッチツリーがAVLアルゴリズムが回転を呼び出してツリーの高さを下げる前に持つことができるスパツリーツリーだからです。