Induktionsbeweis zur Höhe von binären Bäumen (gerichtete Graphen mit Wurzeln)

Question

 

Hier ist meine Aufgabe:

 

Für einen(vollen,gewurzelten,binären) Baum T = (V,E,r) sei die Höhe h(T) definiert als

• 0 ,falls T nur aus einem Knoten besteht, und

• max(h(T₁), h(T₂ )) + 1, falls T durch die disjunkte Vereinigung  der Bäume T₁ und T₂ und

Hinzufügung von r  als neuer Wurzel enstanden ist.

Zeigen Sie mittels Induktion, dass h(T) ≤ n für alle Bäume T mit n inneren Knoten gilt.

Comments

Muss ein 'voller' Baum Verzweigungen enthalten und wie viele genau?

'Innere Knoten' sind wohl weder 'Blätter noch Wurzeln'.

Ohne Verzweigungen käme da doch eine Höhe von n+1 oder gar n+2 raus.

---

Ich würde gerne deine Fragen beantworten aber das ist die komplette Aufgabe ;(

---

Meine Frage wird bei Wikipedia beantwortet, wenn voll und vollstndig dasselbe ist.

https://de.wikipedia.org/wiki/Binärbaum

Induktiv lässt sich zeigen, dass ein vollständiger Binärbaum der Höhe h (h ≥ 1), den man häufig auch als B_h bezeichnet, genau
2^h−1 Knoten,
2^h−1−1 innere Knoten (nicht Blatt, aber eventuell Wurzel),
2^t Knoten in Tiefe t (0 ≤ t ≤ h−1), insbesondere also
2^h−1 Blätter
besitzt. Eine Darstellung eines Binärbaumes, in dem die Knoten mit rechtwinkligen Dreiecken und die Bögen mit Rechtecken dargestellt werden, nennt man pythagoreischen Binärbaum.

Da die Wurzel auch als innerer Knoten gezählt wird, könnte n hinkommen, ist aber eine Überschätzung.

Nachtrag: voll heisst nur, dass keine Halbblätter vorkommen. Vgl. Illustration v. Hanswurst5000

Answer 1

Voll heißt, dass jeder Elternknoten zwei Kindknoten hat; völlständig heißt außerdem noch, dass alle Blätter die gleiche Tiefe haben (siehe meine Zeichnung).

Induktionsanfang: n=1: h(T)=0<=1 wahr.

InduktionsVoraussetzung: Sei bereits für ein n gezeigt, dass h(T)<=n gilt.

Induktionsschritt: n->n+1

h(T)=max{h(T1), h(T2)} +1

OBdA kann man annehmen, dass T1 maximal n innere Knoten hat und somit auch h(T1)>h(T2). Dann gilt nach InduktionsVoraussetzung:

h(T)=h(T1)+1<=n+1, also h(T)<=n+1