Prouver qu'un arbre binaire a au plus

14

J'essaie de prouver qu'un arbre binaire avec n nœuds a au plus n2feuilles. 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 .

varatis
la source
3
Tout d'abord, notez que nous pouvons utiliser LaTeX ici. Cliquez sur "modifier" pour voir comment je l'ai fait. Deuxièmement, je ne vois pas d'induction. Vous jetez quelques chiffres là-bas, mais il n'y a aucune structure de preuve et aucune relation avec les tas. Pouvez-vous l'améliorer? Et enfin, l'affirmation est fausse: une liste triée remplit la propriété du tas et n'a qu'une seule feuille. Avez-vous omis certaines hypothèses?
Raphael
La modification de @ Kaveh est-elle ce que vous aviez en tête, c'est-à-dire "tout au plus"?
Raphael
@Raphael, en relisant la question, je pense qu'il pourrait s'agir de tas où chaque nœud interne a exactement deux enfants (auquel cas la question d'origine a du sens et la revendication est correcte, ou quelque chose de similaire).
Kaveh
1
@Kaveh Ah oui, je vois votre confusion. Les nœuds du tas ont au plus deux enfants (d'où la balise d'arbre binaire)
varatis
1
Je vois. La demande étant formulée avec précision, il n'est en effet pas nécessaire de formuler d'autres hypothèses. La propriété est valable pour tous les arbres binaires.
Raphael

Réponses:

7

Je suppose maintenant que la question est la suivante:

Etant donné un arbre binaire à nœuds, prouver qu'il contient au plus nnfeuilles.n2

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 TTree=EmptyLeafNode(Tree,Tree)TnTTlTT .

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 Th(t)=0T=EmptylT=nT=0h(t)=1T=LeaflT=1=nT2 , 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.Th(T)kk1

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 (Th(T)=k+1k1T=Node(L,R)nT=nL+nR+1LRT , l'hypothèse d'induction s'applique et ah(L),h(R)k

lLnL2 and lRnR2.

Comme toutes les feuilles de sont soit en L soit en R , nous avons celaTLR

lT=lL+lRnL2+nR2nL+nR+12()=nT2

L'inégalité marquée avec peut être vérifiée par une distinction de casse (quadridirectionnelle) pour savoir si n L , n R2 N()nL,nR2N . 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 - 1h2h1 nœuds.
  • Chaque arbre binaire complet a un nombre impair de nœuds.
Raphael
la source
2

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 = 23n=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=2n/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 TnLTn-1

2n-2L+3(n-L)
2Ln+2
n3
2Ln+1
Louis
la source
Je suppose que nous supposons silencieusement les arbres enracinés ici; Wikipédia le fait aussi.
Raphael
1
Wikipedia équivoque en quelque sorte: "En dehors de l'arbre, il y a souvent une référence au nœud" racine "(l'ancêtre de tous les nœuds), s'il existe." Quoi qu'il en soit, cet argument semble mériter d'être écrit, car il est différent et assez simple.
Louis
Si vous continuez à lire, tous les bords sont dirigés, ils parlent d '"enfants" et de "parents". Cela n'a pas de sens dans les arbres non racinés. En conséquence, une feuille serait un nœud avec un degré extérieur 0.
Raphael