Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
AVL Bäume… Fehler im Skript?!
Hab mir grad AVL-Bäume angschaut…
Auf der Seite 8 zu AVL-Bäumen sind 2 Eigenschaften notiert, die für AVL-Bäume mit n Knoten und der Tiefe t gelten sollen.
die zweite Eigenschaft besagt, dass
Fib(t + 3) - 1 <= n <= 2^(t + 2) - 1
gilt. Wenn man das aber z.B. auf den AVL-Baum auf Seite 7 davor anwendet, läuft man da gehörig auf Widerspruch:
Tiefe t = 4, n = 7
Fib(4 + 3) - 1 = Fib(7) - 1 = 13 - 1 = 12
2^(4 + 1) - 1 = 2^5 - 1 = 31
demnach müsste gelten 12 <= 7 <= 31. 
Is das sonst auch noch jemandem aufgefallen oder hab ich was falsch gemacht?!
Wenn man die Tiefe des Baumes auf Seite 7 als 3 annimmt, ergibt die Formel Sinn:
Fib(3+3)-1 = 7 <= 7 <= 15 = 2^(3+1)-1
das ist aber leider falsch! 
Die Tiefe eines Baumes ist als die maximale der Längen der Pfade von der Wurzel zu den Blattknoten definiert,
und die Länge eines Pfades als die Anzahl der Knoten auf diesem Pfad (ist auch sonst überall im Skript so).
Ergo: Der Baum hat die Tiefe 4 und mit dieser Formel kann irgendwas nicht stimmen… :-/
Weiss sonst noch jemand Rat?
Das ist eine reine Definitionsfrage. Informatiker haben die unangenehme Angewohnheit, beim Zählen mal mit 0, mal mit 1 zu beginnen. Ich habe mir den Rest des „Skriptes“ nicht angeschaut, aber es würde mich nicht wundern, wenn es dabei nicht konsistent ist…
Mit deiner Definition der Baumtiefe müßte die Formel folglich lauten:
Fib(t+2)-1 <= n <= (2^t)-1
Der Zusammenhang zwischen Fibonacci-Zahlen und AVL-Bäumen ist hier recht gut erklärt:
http://www.inf.hs-zigr.de/~wagenkn/TI/Komplexitaet/ReferateWS9900/avl/node13.html
laenge des pfades
die tiefe eines leeren baumes ist 0
die tiefe eines baumes bestehend aus einer wurzel ist 1
die tiefe eines baumes ist das maximum der tiefen aller kinder der wurzel plus 1
also hat tsunami recht
das stehts nochmal:
http://wwwmayr.informatik.tu-muenchen.de/skripten/ead_ws9899_html/node21.html
mit der geilen formel von one (wo one wieder mal recht hatte!)
und ausserdem sind die avl baeume im skript absoluter schrott, weil es teilweise gar keine sind. aber egal. (seite 20 → das haette eine LL Rotation sein sollen und ausserdem ist dort 3 < 2 - is ja schliesslich logisch weil: 12 <= 7 im skript gilt - wie tsunami schon festgestellt hat - die semantik der zahlen wie wir sie kennen ist damit hinfaellig)
viel spass noch
linqs
stimmt - hab das auch als LL-Situation gesehen. aber könntes es nicht auch eine LR-Situation sein? Meiner Meinung nach ist die Balance-Situation nach dem Löschen eines Elements nicht eindeutug festzumachen wie beim Einfügen…
Also wenn ich das so gesehen hätte, hätte ich LR Rotation gemacht.
Dachte bisher, dass LL bzw. RR nur bei Bäumen zu machen ist, die 3 Elemente haben also
1 1
2 bzw 2
3 3
Kam jedenfalls bei dem Beispiel mit den Monaten nur so vor.
Hab eigentlich gedacht dass ich die AVL-Bäume kann aber dann bin ich auf ein Problem bei einer Prüfungsaufgabe gestoßen:(siehe Anhang, hab das mit dem Bild einfügen nicht hinbekommen)
Wie Rotier ich da dass es wieder dem Kriterium entspricht?Also die 23 nach oben und die 9 nach links …, aber dann?
Attachment:
AVL.bmp: https://fsi.cs.fau.de/unb-attachments/post_8202/AVL.bmp
ich hab dir jetzt mal genauso schoen paint-maessig reingekritzelt: ich wuerde da RL-rotieren. k. a. ob es andere moeglichkeiten gibt, SO geht es auf jeden fall.
Attachment:
AVL.GIF: https://fsi.cs.fau.de/unb-attachments/post_8206/AVL.GIF
Danke für die schnelle antwort!
Hast du dann 2 mal rotiert?Weil normalerweise steht ja die 23 oben!?
http://www.seanet.com/users/arsen/avltree.html
hat gestern oder so schon mal jemand gepostet, damit sollte zu avl-bäumen alles klar werden.
noe, hab nur einmal rotiert, aber eben eine double-rl-rotation. schau dir am besten nochmal den teil im skript an oder den link, der hier gepostet wurde…