Was ist ein AVL-Baum?

Jeder Knoten in einem AVL-Baum verfolgt seine eigene Höhe: die Anzahl der Kanten auf dem längsten Pfad hinunter zu einem Blatt. Ein Blatt hat die Höhe 1, und ein leerer Teilbaum zählt als Höhe 0. Aus der Höhe der beiden Kinder eines Knotens können Sie seinen Balance-Faktor berechnen: height(left) - height(right).

Ein Knoten ist ausbalanciert, wenn sein Balance-Faktor -1, 0 oder 1 ist. Die Regel des AVL-Baums ist einfach: Jeder einzelne Knoten muss jederzeit ausbalanciert bleiben. Wann immer ein Einfügen oder Löschen den Balance-Faktor eines Knotens auf 2 oder -2 verschiebt, führt der Baum eine Rotation durch: eine lokale Umordnung einiger Zeiger, die das Gleichgewicht in konstanter Zeit wiederherstellt, ohne die Suchbaum-Ordnung zu verletzen.

Es gibt vier Rotationsfälle (Links-Links, Rechts-Rechts, Links-Rechts, Rechts-Links), aber sie alle lassen sich auf zwei Bausteine reduzieren: eine einfache Linksrotation und eine einfache Rechtsrotation. Sie werden beide in den nächsten Lektionen von Grund auf neu erstellen.