+1 Daumen
3,2k Aufrufe

 

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(T1), h(T2 )) + 1, falls T durch die disjunkte Vereinigung  der Bäume T1 und T2 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.

Avatar von
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 Bh bezeichnet, genau
2h−1 Knoten,
2h−1−1 innere Knoten (nicht Blatt, aber eventuell Wurzel),
2t Knoten in Tiefe t (0 ≤ t ≤ h−1), insbesondere also
2h−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

1 Antwort

+2 Daumen

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

 

Avatar von 2,5 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community