Zunächst geht es in der Aufgabe um zwei Dinge: Blätter und Nicht-Blätter. Nicht-Blätter sind per definionem innere Knoten. Innere Knoten können nicht gleichzeitig Blätter sein. Umgekehrt können Blätter keine inneren Knoten sein. Wir haben es also mit zwei disjunkten Mengen zu tun.
(a) Sei \( i \in \mathbb{N}\) die Anzahl der inneren Knoten eines vollständigen binären Suchbaums. Wir zeigen mittels vollständiger Induktion über \(i - 1\), dass die Anzahl der Blätter \(i + 1\) beträgt.
Mit \(i_0 = 0\) erhalten wir einen vollständigen binären Suchbaum mit genau einem Knoten: der Wurzel, die gleichzeitig ein Blatt ist. Die Anzahl der Blätter ist also 1 und die Anzahl der inneren Knoten 0, da das Blatt keinen Vorgänger hat. Mit \(i_1 = 1\) erhalten wir einen vollständigen binären Suchbaum mit einer Wurzel und zwei Blättern. Damit gilt der Induktionsanfang.
Wir setzen für \(i > 1\) die Existenz eines vollständigen binären Suchbaums voraus, in dem \(i - 1\) die Anzahl der Blätter und \(i + 1 - 1 = i\) die Anzahl der Knoten ist.
Sei \(T\) ein vollständiger binärer Suchbaum mit \(i\) Knoten. Entfernen wir zwei Blätter, die zu einem gemeinsamen Elternknoten in \(T\) gehören, wird dieser Elternknoten zu einem Blatt in einem kleineren vollständigen binären Suchbaum. Nennen wir dieses Blatt \(v\) und den kleineren vollständigen Suchbaum \(T'\). \(T'\) hat \(i - 1\) innere Knoten, die nach Induktionsvoraussetzung \(i\) Blätter besitzen. Fügen wir diesem Blatt \(v\) in \(T'\) wieder zwei Blätter hinzu, erhalten wir \(T\), und \(v\) wird wieder zum inneren Knoten in \(T\). Somit gibt es \(i + (- 1 + 2) = i + 1\) Blätter in \(T\).
(b) Der vollständige binäre Suchbaum ist ein Spezialfall des allgemeinen binären Suchbaums. Überlege dir, welche Fälle es im Unterschied zum vollständigen binären Suchbaum gibt und führe den Beweis entsprechend durch.
