H 7.7 c)

f_spitz
Erstie
Erstie
Beiträge: 15
Registriert: 31. Mai 2009 19:13

H 7.7 c)

Beitrag von 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

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: H 7.7 c)

Beitrag von 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 :-)
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

Re: H 7.7 c)

Beitrag von linn »

bruse hat geschrieben: 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?

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: H 7.7 c)

Beitrag von bruse »

Zumindest auf dem Übungsblatt wird Härder (Anzahl der Knoten = Anzahl der Kanten+1) verwendet. Puuuh :-)
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

Re: H 7.7 c)

Beitrag von 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
Kernelcompilierer
Kernelcompilierer
Beiträge: 522
Registriert: 1. Okt 2008 17:18

Re: H 7.7 c)

Beitrag von 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.

Antworten

Zurück zu „Archiv“