H 7.7 c)

[f_spitz]

Servus,

eine Frage zu folgender Frage :
"Gibt es einen AVL-Baum mit Höhe 10 und 120 Knoten" ?

Kann ich das über die finbonacci-bäume lösen?
Ich rechne mir also mit "min = Fib(höhe+2) - 1" die minimale Anzahl an Knoten aus. Die maximale Anzahl ist ja leicht zu bestimmen.
wenn 120 nun dazwischen liegt, dann kann ich die Frage mit ja beantworten?! In wie weit ist da ein Beweiß
gefordert?


Danke,

Gruß Flo

[bruse]

Du könntest einen solchen Baum ja zeichnen, wenn es ihn gibt. Das wäre Beweis genug. Alternativ zeigst du, dass es keinen geben kann, je nachdem, was richtig ist

Pass auf, dass Du die richtige Definition von Höhe nimmst. Sonst wirds garantiert falsch

[linn]

Pass auf, dass Du die richtige Definition von Höhe nimmst. Sonst wirds garantiert falsch

unsre definition von höhe ist ja anzahl knoten auf dem längsten Weg von Wurzel zu Blatt.
Die Formel im Skript zur Fibonacci-Höhe ist aber die gleiche wie bei Wikipedia, wo die höhe als anzahl der kanten auf dem längsten weg von wurzel zu blatt definiert ist.
Also wird bei der Formel im Skript ( 1,44*log2(n+1) ) wirklich die Höhe von Härder (anzahl kanten +1 ) benutzt?
Und auf dem Übungsblatt auch?

[bruse]

Zumindest auf dem Übungsblatt wird Härder (Anzahl der Knoten = Anzahl der Kanten+1) verwendet. Puuuh

[linn]

ok, also ich geh jetzt einfach mal davon aus das die Formel für die Def nach Härder gilt, also setze 10 und 120 ein.

[fetzer]

Da ein Fibonacci-Baum einen AVL-Baum mit minimaler Knotenanzahl darstellt ist das doch völlig korrekt. Wenn 120 nun kleiner deines Ergebnisses ist ist der Baum nicht möglich. Ist 120 größer musst du schauen, ob dadurch nicht die Anzahl auf Stufe 11 überschritten wird.
Das Einsetzen der 2 Zahlen in die bekannte Formel sollte meiner Meinung nach als Beweis eigentlich reichen.