Prouver un arbre binaire a au plus $ \ lceil n / 2 \ rceil feuilles de $

Question

Je suis en train de prouver qu'un arbre binaire avec $ n $ nœuds a au la plupart des $ \ left \ lceil \ frac {n} {2} \ right \ rceil feuilles $. Comment pourrais-je aller sur le faire avec l'induction?

Pour les personnes qui marchent dans la question initiale sur les tas, il a été déplacé ici .

Answer 1

Je suppose maintenant que la question est la suivante:

  

Étant donné un arbre binaire avec des noeuds $ n $, prouver qu'il contient au plus $ \ left \ lceil \ frac {n} {2} \ right \ rceil feuilles $.

Laissez-nous travailler avec la définition arbre $ \ mathrm {Arbre} = \ mathrm {vide} \ mid \ mathrm {Feuille} \ mid \ mathrm {Node} (\ mathrm {Arbre}, \ mathrm {Arbre}) $ . Pour $ T $ un tel arbre, soit $ n_T $ le nombre de nœuds de $ T $ et l_T $ $ le nombre de feuilles de $ T $.

Vous avez raison de le faire par induction, mais vous aurez besoin structure induction qui suit la structure de l'arbre. Pour les arbres, ce qui est souvent fait que l'induction complète sur la hauteur $ h (T) $ des arbres.

L'ancre d'induction comporte deux parties. Tout d'abord, pour $ h (t) = 0 $ on a $ T = \ mathrm {vide} $ avec $ l_T = n_T = 0 $; la demande contient clairement l'arbre vide. Pour $ h (t) = 1 $, soit $ T = \ mathrm {Feuille} $, nous avons de la même $ l_T = 1 = \ left \ lceil \ frac {n_T} {2} \ right \ rceil $, de sorte que la demande détient des feuilles.

L'hypothèse de récurrence est: On suppose que la demande contient

pour tous les arbres $ T $ (binaire) avec $ h (T) \ leq k $, $ k \ geq 1 $ arbitraire mais fixe.

Pour l'étape d'induction, considérons un arbre binaire arbitraire $ T $ à $ h (T) = k + 1 $. Comme $ k \ geq $ 1, $ T = \ mathrm {Node} (L, R) et $ n_T = n_L + N_R + 1 $. Comme $ L $ et $ R $ sont également des arbres binaires (autrement ne serait pas T $ $ soit) et $ h (L), h (R) \ leq k $, l'hypothèse d'induction applique et avez

$ \ qquad \ displaystyle l_l \ leq \ left \ lceil \ frac {n_L} {2} \ right \ rceil \ texte {et} L_R \ leq \ left \ lceil \ frac {N_R} {2} \ right \ rceil. $

Comme toutes les feuilles de $ T $ sont soit en $ L $ ou $ R $, nous avons que

$ \ qquad \ begin {align *}   l_T & = l_l + L_R \\       & \ Leq \ left \ lceil \ frac {n_L} {2} \ right \ rceil + \ left \ lceil \ frac {N_R} {2} \ right \ rceil \\       & \ Leq \ left \ lceil \ frac {n_L + N_R + 1} {2} \ right \ rceil \ qquad (*) \\       & = \ Left \ lceil \ frac {n_T} {2} \ right \ rceil \ End {align *} $

L'inégalité marquée avec $ (*) $ peut être vérifié par (quatre voies) distinction cas de savoir si $ n_L, N_R \ dans 2 \ mathbb {N} $. Par la puissance de l'induction, ce qui conclut la démonstration.

---

En guise d'exercice, vous pouvez utiliser la même technique pour prouver les affirmations suivantes:

• Chaque arbre binaire parfait de hauteur $ $ h a 2 $ ^ h-1 nœuds de $.
• Chaque arbre binaire complet a un nombre impair de nœuds.

Answer 2

Je suis un peu confus par la question. Si vous êtes intéressé par les arbres avec un degré au plus 3 $ $, ce qui est ce que Wikipedia dit que vous voulez, nous courons le problème qu'un seul bord a $ n = 2 nœuds $ et $ n = 2 feuilles de $, mais $ n / 2 = 1 $. Quoi qu'il en soit, voici quelque chose de proche qui a un argument facile.

Soit $ T $ un tel arbre avec $ n $ nœuds et feuilles $ L $. Depuis $ T $ est un arbre, il y a n-1 $ bords $, et les doubles comptages, nous voyons que $$ 2n - 2 \ le L + 3 (n - L) $$ qui dit que $$ 2L \ le n + 2 $$ et cela est serré dans l'exemple ci-dessus deux sommets. Je suppose que si vous voulez supposer qu'il ya une racine de degré deux et $ n \ ge 3 $, alors vous pouvez affiner cet argument pour donner $$ 2L \ le n + 1 $$ qui est ce que vous cherchez, et c'est serré lorsque l'arbre est plein.