Das Beweisen eines binären Baums hat höchstens $ lceil n/2 rceil $ Blätter

Question

Ich versuche zu beweisen, dass a Binärbaum mit $ n $ nodes hat höchstens $ links lceil frac {n} {2} right rceil $ Leaves. Wie würde ich das mit Induktion machen?

Für Menschen, die in der ursprünglichen Frage zu Haufen folgten, wurde es bewegt hier.

Answer 1

Ich nehme jetzt an, dass die Frage die folgende ist:

Beweisen Sie bei einem binären Baum mit $ n $ Knoten, dass er höchstens $ links lceil frac {n} {2} rechts rceil $ Blätter enthält.

Arbeiten wir mit der Baumdefinition $ mathrm {baum} = mathrm {leer} mathrm {Leaf} Mid mathrm {node} ( mathrm {baum}, math mathrm {tree}) $ arbeiten. Für $ t $ einen solchen Baum, sei $ n_t $ die Anzahl der Knoten in $ t $ und $ l_t $ Die Anzahl der Blätter in $ t $.

Sie haben Recht, dies durch Induktion zu tun, aber Sie werden benötigen strukturell Induktion, die der Baumstruktur folgt. Für Bäume wird dies oft als vollständige Induktion über die durchgeführt Höhe $ h (t) $ der Bäume.

Der Induktionsanker hat zwei Teile. Erstens für $ h (t) = 0 $ haben wir $ t = mathhrm {leer} $ mit $ l_t = n_t = 0 $; Die Behauptung gilt eindeutig für den leeren Baum. Für $ h (t) = 1 $, dh $ t = mathhrm {Leaf} $ haben wir in ähnlicher Weise $ l_t = 1 = links lceil frac {n_t} {2} rechts rceil $, also die Behauptung hält für Blätter.

Die Induktionshypothese lautet: Angenommen, der Anspruch gilt für alle (binären) Bäume $ T $ mit $ H (t) Leq K $, $ K Geq 1 $ beliebig, aber behoben.

Betrachten Sie für den induktiven Schritt einen willkürlichen binären Baum $ t $ mit $ h (t) = k+1 $. As $ k Geq 1 $, $ t = mathhrm {node} (l, r) $ und $ n_t = n_l+ n_r+ 1 $. Da $ L $ und $ R $ auch binäre Bäume sind (ansonsten $ t $ nicht) und $ H (l), h (r) leq k $, gilt die Induktionshypothese und hat haben

$ qquad displaystyle l_l leq links lceil frac {n_l} {2} rechts rceil text {und} l_r leq links lceil frac {n_r {2} rechts rceil.

Da alle Blätter von $ t $ entweder in $ l $ oder $ R $ sind, haben wir das

$ qquad begin {align*} l_t & = l_l + l_r & leq links lceil frac {n_l} {2} rechts rceil + links lceil frac {n_r} {2}}}} rightrceil &leq leftlceil frac{n_L + n_R + 1}{2} rightrceil qquad (*) &= leftlceil frac{n_T}{2} Right rceil end {align*} $

Die mit $ (*) $ markierte Ungleichung kann mit (vier Way) -Schülle über die Unterscheidung über $ n_l, n_r in 2 mathbb {n} $ überprüft werden. Durch die Macht der Induktion schließt dies den Beweis.

---

Als Übung können Sie dieselbe Technik verwenden, um die folgenden Aussagen zu beweisen:

• Jeder perfekte Binärbaum der Höhe $ H $ hat 2 $^H-1 $ Knoten.
• Jeder volle binäre Baum hat eine ungerade Anzahl von Knoten.

Answer 2

Ich bin ein wenig verwirrt über die Frage. Wenn Sie an Bäumen mit dem Abschluss an höchstens $ 3 $ interessiert sind, was Wikipedia sagt, möchten wir das Problem, dass ein einzelner Rand $ n = 2 $ Knoten und $ n = 2 $ Blätter hat, aber $ n/ 2 = 1 $. Wie auch immer, hier ist etwas in der Nähe, das ein leichtes Argument hat.

Sei $ t $ so ein Baum mit $ n $ nodes und $ l $ blätter. Da $ t $ ein Baum ist, gibt es $ N -1 $ $ und doppelt sie doppelt zählen, sehen wir, dass $ 2n - 2 le l + 3 (n - l) $$, was besagt, dass $ 2L la n + 2 $$ und das ist in dem oben genannten Zwei-Geber-Beispiel eng. Ich denke, wenn Sie davon ausgehen möchten, dass es eine Wurzel von Grad zwei und $ n ge 3 $ gibt, können Sie dieses Argument verfeinern, um $ 2l le n + 1 $ zu geben, wonach Sie suchen und suchen und nach und Dies ist dicht, wenn der Baum voll ist.