AVL-Baum: Balancebedingung und Höhe

An jedem Knoten eines AVL-Baums unterscheiden sich die Höhen des linken und rechten Teilbaums um höchstens eins. Beim Balancefaktor BF=hL−hR sind daher nur −1, 0 und +1 zulässig. Diese lokale Regel begrenzt die Gesamthöhe logarithmisch und verhindert, dass etwa sortiert eingefügte Schlüssel den Suchbaum zu einer langen Kette machen. Zusätzlich bleibt die binäre Suchbaumordnung erhalten: kleinere Schlüssel liegen links, größere rechts. Leere Teilbäume brauchen eine festgelegte Höhenkonvention, etwa minus eins oder null; der zulässige Höhenunterschied bleibt gleich. Die Schranke gilt auch nach jeder erfolgreich abgeschlossenen Einfügung oder Löschung.

Eine Rotation ändert Eltern-Kind-Verknüpfungen in einem kleinen Teilbaum, erhält aber dessen sortierte In-Order-Folge. Werden 30, 20 und 10 in dieser Reihenfolge eingefügt, macht eine Rechtsrotation 20 zur Wurzel; 10 liegt links und 30 rechts. Die Reihenfolge bleibt 10,20,30, während die Höhenabweichung verschwindet. Implementierungen müssen danach gespeicherte Teilbaumhöhen aktualisieren. Die Rotation repariert also die Form, nicht die Schlüsselordnung. Die Teilbäume zwischen den gedrehten Knoten müssen in der Schlüsselordnung an ihrer ursprünglichen Stelle bleiben. Die äußeren Teilbäume bleiben dabei an den Grenzen ihrer Schlüsselintervalle angeschlossen.

Bei einem Links-Rechts- oder Rechts-Links-Fall knickt der schwere Pfad zunächst zum inneren Kind ab. Eine Rotation am Kind wandelt die Situation in einen außen schweren Fall um; eine zweite Rotation am unausgeglichenen Knoten stellt die Balance wieder her. Entscheidend ist die Richtung der letzten Einfügung relativ zum schweren Kind. Eine einfache Links- oder Rechtsrotation würde den inneren Knick nicht beheben und könnte die Höhe weiter unausgewogen lassen. Die Doppelrotation folgt aus zwei entgegengesetzten Schritten und wird oft als Links-Rechts- beziehungsweise Rechts-Links-Fall benannt.

Die AVL-Höhe ist O(log n); deshalb benötigt eine Suche logarithmisch viele Knotenbesuche. Einfügen und Löschen folgen zunächst ebenfalls einem Pfad dieser Länge und aktualisieren Höhen beziehungsweise Balancefaktoren. Je betroffener Ebene genügt eine begrenzte Zahl lokaler Rotationen, sodass die gesamte Aktualisierung logarithmisch bleibt. Dafür speichert der Baum zusätzliche Balancemetadaten und führt bei Änderungen mehr Arbeit aus als ein unbalancierter Suchbaum. Bei sehr häufigen Änderungen kann ein weniger streng balancierter Baum trotz höherer Suchhöhe günstiger sein. Dadurch bleiben sowohl Suche als auch Aktualisierung im logarithmischen Worst Case.

Die Balance hängt von den Teilbaumhöhen ab, nicht vom numerischen Abstand zwischen Schlüsselwerten. 30, 20 und 10 machen die fallende Einfügereihenfolge anschaulich; dieselbe Links-Links-Situation entsteht für beliebige Werte x>y>z in dieser Reihenfolge. Die Rotation verändert nur die Baumstruktur. Suchvergleiche führen weiterhin kleinere Schlüssel nach links und größere nach rechts, sodass die Suchbaumordnung und damit die korrekte Suche erhalten bleiben. Die Schlüsselwerte dienen nur als anschauliche Suchreihenfolge; die Balance wird allein aus gespeicherten Teilbaumhöhen bestimmt. Die Wahl der konkreten Schlüssel ändert die Rotationsregel nicht.