Satz - Knotenzahl vollständiger balancierter Binärbäume

Sei $T=(V,E)$ ein vollständiger, balancierter Binärbaum der Höhe $h$.
Dann hat $T$ genau

Knoten.

Beweis

Beweis per Induktion über $h$.

Induktionsanfang

$h=0$.
Dann enthält $T$ nur einen Knoten und es gilt

Induktionsvoraussetzung

Wir nehmen an, die Behauptung sei für alle $j<h$ schon bewiesen.

Induktionsschritt

Angenommen, $T$ hat Höhe $h>0$.
Sei $v$ die Wurzel von $T$ und $s_1,s_2$ die beiden Nachfolger.
Seien $T_1,T_2$ die beiden Teilbäume von $T$ mit Wurzel $s_1,s_2$.
Dann haben $T_1,T_2$ die Höhe $h-1$ und nach Induktionsvoraussetzung jeweils

Knoten.

Also gilt:

Links

• Induktionsbeweis
• DS_vollständiger_foliensatz.pdf