Prouver qu'un arbre binaire a au plus

J'essaie de prouver qu'un arbre binaire avec $n$ nœuds a au plus $\left\lceil \frac{n}{2} \right\rceil$feuilles. Comment pourrais-je procéder avec l'induction?

Pour les personnes qui suivaient la question initiale sur les tas, elle a été déplacée ici .

Je suppose maintenant que la question est la suivante:

Etant donné un arbre binaire à nœuds, prouver qu'il contient au plus ⌈ $n$feuilles.$\left\lceil \frac{n}{2} \right\rceil$

Travaillons avec la définition d'arbre . Pour T un tel arbre, soit n T le nombre de nœuds dans T et l T le nombre de feuilles dans $\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$$T$$n_T$$T$$l_T$$T$ .

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

L'ancre à induction a deux parties. Premièrement, pour nous avons T = E m p t y avec l T = n T = 0 ; la revendication vaut clairement pour l'arbre vide. Pour h ( t ) = 1 , c'est-à-dire T = L e a f , nous avons de même l T = 1 = ⌈ n $h(t)=0$$T=\mathrm{Empty}$$l_T=n_T=0$$h(t)=1$$T = \mathrm{Leaf}$$l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$ , donc la demande est valable pour les feuilles.

L'hypothèse d'induction est: Supposons que la revendication s'applique à tous les arbres (binaires) avec h ( T ) ≤ k , k ≥ 1 arbitraire mais fixe.$T$$h(T)\leq k$$k\geq 1$

Pour l'étape inductive, considérons un arbre binaire arbitraire avec h ( T ) = k + 1 . Comme k ≥ 1 , T = N o d e ( L , R ) et n T = n L + n R + 1 . Comme L et R sont également des arbres binaires (sinon T ne le serait pas) et h ( L ) , h $T$$h(T)=k+1$$k\geq 1$$T=\mathrm{Node}(L,R)$$n_T = n_L+ n_R+1$$L$$R$$T$ , l'hypothèse d'induction s'applique et a$h(L),h(R)\leq k$

$\qquad \displaystyle l_L \leq \left\lceil \frac{n_L}{2} \right\rceil \text{ and } l_R \leq \left\lceil \frac{n_R}{2} \right\rceil.$

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

$\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ée par une distinction de casse (quadridirectionnelle) pour savoir si n L , n R ∈ 2 $(*)$$n_L,n_R\in 2\mathbb{N}$ . Par la puissance de l'induction, cela conclut la preuve.

Comme exercice, vous pouvez utiliser la même technique pour prouver les affirmations suivantes:

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

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

Soit un tel arbre à n nœuds et L feuilles. Puisque T est un arbre, il y a n - 1 arêtes, et en les comptant deux fois, nous voyons que 2 n - 2 ≤ L + 3 ( n - L ) qui dit que $T$$n$$L$$T$$n-1$