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.
komplexe avl-rotationen
z. b. bei aufgabe 8d, klausur 10/1998: da kommt nach einer weile so ein baum raus:
10
3 12
2 5
9
ich habe jetzt keine ahnung, welche der 4 bekannten rotationen man verwenden soll. ich haette als naechstes das ganze einfach so umgeformt:
9
3 10
2 5 12
6
wie wuerdet ihr das machen?Also das ist die Rotation der Form:
x
x
x
Also den unteren Knoten nach oben, den obern nach rechts, der linke bleibt. Nun muss man noch die 9 entsprechend dranhängen (als li sohn von 10)
5
3 10
2 9 12
Bin mir aber nicht sicher.
Zustimmung
ich denke du meintest LR-Rotation mit Wurzel als oberstem Element
Naja, ich würde die 9 an der Stelle lassen, wo sie vorher war, nur nach oben rutschen, d.h.
5
3 10
2 9 12
wobei die 9 echt rüber müsste, aber nach Skript muss sie glaub ich links stehen bleiben.
Da WELL '3
ich hab noch keine aufgabe gefunden, in der man einen java-algorithmus für sowas finden muss.
also nimmst du die fraglichen elemente, die bei solchen rotationen manchmal scheinbar ‘im weg’ sind einfach mal komplett raus und sortierst sie anschließend (für die aufgabe natürlich im selben schritt…) wieder da ein, wo sie sein müsste. die sortierung des baums kennst du ja. das ist im übrigen dann auch immer die stelle, an der es nach bestimmten, ganz komplizierten regeln sein muss.
und für die einfacheren rotationen: du betrachtest nur die ‘wurzeln der fraglichen teilbäume’, alles was da noch so dranhängt, bleibt auch da! außer es ist im weg, dann gilt obiges.
Das geht aba net, weil alles links der 5 kleiner sein muss.
Also ich hab mir das so gedacht:
das letzte wo ich mir sicher bin war ja:
9
6 10
3 12
2 5
aber da ist die Balance von der 6 ja 2, also muss da was geschehen.
Also (ich glaube das heisst Single LL Rotation) ziehen wir die 3 hoch und packen die 6 rechts unten dran. Weil da aber schon was steht erst eins weiter:
9
3 10
2 5 12
6
Dann stimmt die Balance wieder und alle sind happy 
Mein Vorschlag:
9
5 10
3 6 12
2
So hätte ich des gemacht.
Noch ein Vorschlag: (ausgehend von Steppenwolfs ersten Baum)
5
3 10
2 6 9 12
@thevoid: und was ist mit der 6???
Was sagt man denn dazu:
aus:
9
3 10
2 5 12
6
wird, kA ob ich hier einfach nochmal doppelrotieren darf, bzw muss, ich machs einfach:
6
3 9
2 5 10
12
und dann:
6
3 10
2 5 9 12
Ich glaub, das ist schon ok so. Alles ausbalanciert. Also feddich
Solange keine Verletzung der AVL Eigenschaft vorliegt, sollte man nicht rotieren dürfen. Die 6 hab ich vorhin wohl irgendwie übersehen.
Aber ich glaube, die 5 muss in die Wurzel, da ich doch eine LR-Rotation mit den Knoten 10-3-5 mache. Die 9 hat nach der LR-Rotation auf der linken Seite der 10 einen Platz gefunden. Die 6 wurschtel ich dann halt einfach als linken Nachfolger an die 9 dran.
Und dann sieht mein Vorschlag so aus:
5
3 10
2 9 12
6
Ich denke die 5 kann nicht die neue Wurzel werden, denn ich denke bei den Doppelrotationen, in diesem Fall eine LR, nimmst du das K1, was am weitesten rechts steht, somit gewährleistest du, dass beide Teilbäume in sich stimmen…also musst du die LR-Rotation bei 10-3-5-9 machen…dann muss man auch nix wurschteln 
@Augenmann: Naja, ich hab mich halt an dem Beispiel im Skript (das mit den Monatsnamen) orientiert und komm dann auf das Ergebnis, das 2 Posts weiter oben steht.
Also mal im ernst, das Beispiel mit den Monatsnamen find ich so ziemlich das schlechteste im ganzen Script. Ich habe ewig gebraucht um überhaupt zu verstehen, dass die Monatsnamen da einfach beliebig eingefügt werden, ich hab da immer nach einer Ordnung gesucht :vogel:
Ich weiss ned ob die Regel stimmt, aber sie würde halt Sinn machen, wenn man DoppelRotationen macht, dann immer mit grössten Element, da nur so noch einigermassen “rotiert” werden kann, ansonsten stöpselt man die freien Blätter einfach irgendwo an…das kann nicht Sinn der Übung sein.
hilfääääääääääääääääää !!! :#: :#: :#: :#: :#: ich dachte es sei nur sinn und zweck die baeumchen im gleichgewicht zu halten? blick nich ganz warum das etz noch so ausfuehrlich diskutiert wird :#: :#: :#: :#:
@fredator: genau darum geht es bei avl-bäumen, ja.
ich hab hier in dem thread auch schon den überblick verloren, aber ich hab mir die aufgabe auch noch gar net so genau angeschaut. im wesentlichen gilt mein rat an alle, die’s nicht kapieren, weiterhin: (siehe mein letzter beitrag in dem thread)
Sollte so stimmen. Wenn ihr auf nen (noch) 4 Semestler hören wollt.
Und die 6 kann dann logischerweiße einfach links an die 9 angehängt werden.
C.U.
P.S. http://www.seanet.com/users/arsen/avltree.html
kann zum üben sehr hilfreich sein