Prove que a árvore AVL tem esse tipo de propriedade com sequência de Fibonacci

Question

Q: provar que para qualquer árvore do AVL que tenha $ n $ nós ( $ n \ GEQ 1 $ )
e tem uma altura de $ H $ Esta propriedade é verdadeira:
$ n \ geq f (h) $ onde $ f (h) $ é a $ h $ -th elemento na sequência de Fibonacci:
$ f (0)= 0, f (1)= 1, f (n)= f (n-1) + f (n-2) ~~~~ \ forall n\ GEQ 2 $

Esta é minha go:

Sabemos que é uma árvore AVL, então $ h=log_2 {n} $
Assim, precisamos provar que $ n \ GEQ F (\ log_2 {n}) $

$ f (\ log_2 {n})= f (\ log_2 {n} -1) + f (\ log_2 {n} -2) $
No entanto, estou preso a partir daqui, não sei o que isso me ajuda e eu sou sem noção no que fazer o próximo ..
Eu apreciaria sua ajuda, obrigado!

Answer 1

Deixe $ t $ ser uma árvore do AVL de $ n> 0 $ nós com altura $ h \ GE 0 $ . Você pode provar que $ n> f (h) $ por indução na $ h $ .

para $ h= 0 $ A reivindicação é verdadeira desde a $ n= 1 $ e $ 1> 0= f (0)= f (h) $ . Para $ h= 1 $ A reivindicação é verdadeira, já que $ n \ GE 2 $ e $ 2> 1= f (1)= f (h) $ .

para $ h \ GE 2 $ , deixe $ R $ ser a raiz da árvore do AVL . A subárvore $ t_ \ ell $ enraizado na criança esquerda da $ R $ e a subtree $ t_r $ enraizado na criança certa da $ R $ existem são ambas as árvores AVL. Além disso, uma vez que $ T $ é balanceado, pelo menos uma árvore $ T '$ entre $ t_ \ ell $ e $ t_r $ deve ter altura $ h-1 $ , enquanto a outra árvore $ t '' $ deve ter altura pelo menos $ h-2 $ < / span>.

por hipótese indutiva o número $ n '$ de nós de $ t' $ é mais do que $ f (H-1) $ , enquanto o número de nós de $ t '' $ é mais do que $ f (H-2) $ . Portanto, o número de nós $ n $ é: $$ n= 1 + N '+ N' '\ GE 3 + F (H-1) + F (H-2)= 3 + F (h)> f (h). $$