Operationen auf AVL-Bäumen

Zunächst können Suchen, Löschen und Einfügen wie in gewöhnlichen Suchbäumen durchgeführt werden. Das Einfügen bzw. Löschen eines Elements in einen AVL-Baum kann dessen Struktur verändern, sodass die Balancierungskriterien nicht mehr stimmen. Deshalb ist zu prüfen, ob Rebalancierungsmassnahmen notwendig sind oder nicht. Zur Rebalancierung werden

• die einfache Rotation (kurz Rotation genannt)
• die Doppelrotation verwendet.

Abbildung 7: Rotationen

Abbildung 8: Doppelrotationen

Die Rotation und die Doppelrotation können nach links oder nach rechts ausgeführt werden. Die Rotation sowie die Doppelrotation an einem Knoten $v$ kann in konstanter Zeit ausgeführt werden. Wir erläutern hier nur den Fall einer Rotation bzw. Doppelrotation nach links, die nach dem Einfügen im rechten Teilbaum oder Löschen im linken Teilbaum erforderlich sein kann. Man beachte, dass eine Rotation oder Doppelrotation nur an solchen Knoten $v$ durchgeführt wird, für die die Teilbäume von v der AVL-Bedingungen genügen. Dies kann dadurch sichergestellt werden, in dem die AVL-Bedingungen in Bottom-Up-Manier wiederhergestellt wird. Das heisst, dass wir starten mit dem tiefsten Knoten $v$, an dem die AVL-Balance gestört ist.

• Ist $bal(v) = -2$ und $bal(right(v)) \in \{-1,0\}$, dann ist eine einfache Rotation nach links auszuführen.
• Ist $bal(v) = 2$ und $bal(left(v)) \in \{1,0\}$, dann ist eine einfache Rotation nach rechts auszuführen.
• Ist $bal(v) = -2$ und $bal(right(v)) = 1$, dann ist eine Doppelrotation nach links auszuführen.
• Ist $bal(v) = 2$ und $bal(left(v)) = -1$, dann ist eine Doppelrotation nach rechts auszuführen.

Nach dem eigentlichen Einfügen bzw. Löschen, wie in gewöhnlichen Suchbäumen, muss die Balanceinformation berichtigt werden und eventuelle rebalanciert werden. Eine Beispielimplementierung könnte wie folgt aussehen:

PROCEDURE BalanceNode(node: PAVLNode): PAVLNode;
BEGIN
  IF node^.balance < LESS THEN
    IF node^.left^.balance > EQUAL THEN
      node^.left := RotLeft(node^.left);
    END;
    node := RotRight(node);
  ELSIF node^.balance > MORE THEN
    IF node^.right^.balance < EQUAL THEN
      node^.right := RotRight(node^.right); (* siehe Beispiel *)
    END;
    node := RotLeft(node);
  END;
  RETURN node;
END BalanceNode;