证明AVL树具有斐波纳契序列的这种财产

Question

span>）
并且具有 $ h $ 这个属性是真的：
$ n \ geq f（h）$ 其中 $ f（h）$ 是 $ h $ -th元素在fibonacci序列中：
$ f（0）= 0，f（1）= 1，f（n）= f（n-1）+ f（n-2）~~~~~ \ forall n\ geq 2 $

这是我的GO：

我们知道它是一个avl树，所以 $ h=log_2 {n} $
因此，我们需要证明 $ n \ geq f（\ log_2 {n}）$

$ f（\ log_2 {n}）= f（\ log_2 {n} -1）+ f（\ log_2 {n} -2）$
然而，我被困在这里，我不知道这对我有什么帮助，我是无能为力的下一步。
我很感激你的帮助，谢谢！

Answer 1

让 $ t $ 是 $ n> 0 $ 节点具有高度 $ h \ ge 0 $ 。您可以证明 $ n> f（h）$ 通过归纳 $ h $ 。

对于 $ h= 0 $ 由于 $ n= 1 $ 和 $ 1> 0= f（0）= f（h）$ 。 对于 $ h= 1 $ 由于 $ n \ ge 2 $ 和 $ 2> 1= f（1）= f（h）$ 。

对于 $ h \ ge 2 $ ，让 $ r $ 是avl树的根。子树 $ t_ \ ell $ roved $ r $ 和子树 $ t_r $ rooted在 $ r $ 中存在均为AVL树。此外，由于 $ T $ 是平衡的，至少一个树 $ t'$ $ t_ \ ell $ 和 $ t_r $ 必须具有高度 $ h-1 $ ，而另一个树 $ t'' $ 必须具有高度 $ h-2 $ < / span>。

通过归纳假设 $ n'$ $ t'$ 的节点超过 $ f（h-1）$ ，而 $ t''$ 的节点数量更多比 $ f（h-2）$ 。 因此，节点 $ n $ 是： $$ n= 1 + n'+ n''\ ge 3 + f（h-1）+ f（h-2）= 3 + f（h）> f（h）。 $$