Rotationen links und rechts

Eine Rechtsrotation um Knoten y mit linkem Kind x macht x zur neuen Wurzel des Teilbaums und y zum rechten Kind von x. Linkssymmetrisch für die andere Seite.

Doppelrotationen (links-rechts, rechts-links) kombinieren zwei einfache Rotationen, wenn die Unbalance tiefer sitzt.

Rotationen erhalten die Suchbauminvariante und ändern die Höhe.

Lokale Zeigerupdates in AVL/Rot-Schwarz und verwandten Strukturen. Rotationen sind der Mechanismus, mit dem Indizes nach Insert/Delete wieder flach werden, ohne alles neu zu bauen.

Vertiefung

Eine Rotation verändert lokale Eltern-Kind-Beziehungen, ohne die aufsteigende Inorder-Folge der Schlüssel zu zerstören. Der mittlere Teilbaum wechselt dabei die Seite und bleibt zwischen denselben Grenzschlüsseln.

Neben Kindverweisen müssen gegebenenfalls Elternverweise, Wurzelreferenz und gespeicherte Höhen aktualisiert werden. Die Reihenfolge der Zuweisungen muss alle benötigten alten Referenzen erhalten.

Ein geradliniges Ungleichgewicht wird mit einer einzelnen Rotation repariert. Bei einem geknickten Pfad ist zuerst eine Rotation am Kind und danach am verletzten Knoten nötig.

Schwierigkeitsstufen

1. Schlüsselreihenfolge vor und nach einer Rotation prüfen.
2. Alle betroffenen Verweise und Metadaten aktualisieren.
3. Einfachen und doppelten Rotationsfall erkennen.

Fallstricke

Eine korrekte lokale Zeichnung reicht nicht, wenn der neue Teilbaumkopf nicht wieder mit seinem früheren Elternknoten verbunden wird. Höhen sollten erst nach den Verweisen neu berechnet werden.