Coder Wiki | Algorithmen

Als Invariante beim AVL-Baum gilt, dass sich für jeden Knoten k die Höhen h1 und h2 der beiden Teilbäume um höchstens 1 unterscheiden. Dies nennt man auch das AVL-Kriterium ?.

Algorithmus

Jeder Knoten des Baums muss neben dem Schlüssel einen Balance-Wert speichern, der angibt ob der Baum links- oder rechtslastig ist. Der Balancegrad eines Knotens k berechnet sich aus („Höhe des rechten Teilbaums“) − („Höhe des linken Teilbaums“). Er beträgt 0, wenn der Knoten ausgeglichen ist (also linker und rechter Teilbaum gleich tief sind); er ist positiv, wenn der rechte Teilbaum tiefer als der Linke ist und negativ, wenn der Linke tiefer als der Rechte ist. Bei einem Balance-Wert größer 1 oder kleiner −1 ist eine Rotation erforderlich.

Nach jedem Einfügen oder Löschen eines Knotens wird in allen seinen Vorgängern bis zur Wurzel der Balance-Wert angepasst und die Balancierung überprüft. Dies geschieht auf dem „Rückweg“ der rekursiven Aufruffolge, was einen separaten Prüf- und Korrekturlauf überflüssig macht. Eine Rotation benötigt nur eine konstante Anzahl von Verknüpfungsänderungen am betreffenden Knoten, seinem Vorgänger und den beiden Nachfolgern.

Ausgleichen

Wurde durch eine Einfüge- bzw. Löschoperation die Balance zerstört, wird der AVL-Baum automatisch ausgeglichen. Dabei arbeitet er mit einfachen und doppelten Rotationen.

Eine einfache Rotation ist immer dann notwendig, wenn sich durch das Einfügen oder Löschen eines Elementes ein Höhenunterschied von mehr als 1 an einem der beiden äußersten Teilbäume eines Zweiges eines AVL-Baumes ergibt. Hingegen ist eine Doppelrotation notwendig, wenn der Höhenunterschied an inneren Teilbäumen auftritt.