AVL-Idee: Balancefaktor

Ein AVL-Baum ist ein binärer Suchbaum, in dem sich die Höhen der Kindteilbäume um höchstens 1 unterscheiden. Der Balancefaktor eines Knotens ist Höhe(links) - Höhe(rechts) (oder umgekehrt; wichtig ist Konsistenz).

Nach Einfügen oder Löschen kann die Invariante gebrochen sein. Rotationen stellen sie lokal wieder her.

Ziel: Höhe bleibt $\Theta(\log n)$.

$$|h_L - h_R| \le 1$$

Wo gebraucht

Lehrgerüst für selbstbalancierende Bäume. In der Praxis oft Rot-Schwarz (TreeMap) oder B-Bäume; die Balanceinvariante ist dieselbe Produktidee: Höhe in $O(\log n)$ halten.

Vertiefung

Ein AVL-Baum ergänzt die Suchordnung um eine lokale Höhenbedingung. Der Balancefaktor eines Knotens ist die Differenz der Höhen seiner beiden Teilbäume. Zulässig sind nur kleine Abweichungen.

Nach einer Änderung können sich Höhen entlang des Pfads zur Wurzel ändern. Andere Teilbäume bleiben unverändert. Deshalb genügt es, diesen Pfad rückwärts zu prüfen und den ersten beziehungsweise weitere verletzte Knoten zu reparieren.

Die lokale Bedingung begrenzt die globale Höhe. Der kleinste AVL-Baum einer gegebenen Höhe enthält rekursiv einen minimalen Baum der beiden vorherigen Höhen, wodurch eine Fibonacci-artige Grössenfolge entsteht.

Schwierigkeitsstufen

1. Balancefaktoren aus Teilbaumhöhen berechnen.
2. Betroffene Vorfahren nach einer Änderung bestimmen.
3. Aus der Minimalgrössenrekurrenz eine logarithmische Höhe begründen.

Fallstricke

Vorzeichenkonventionen für den Balancefaktor unterscheiden sich. Entscheidend ist konsistente Verwendung; aus einem Vorzeichen allein darf ohne Definition keine Rotationsrichtung gefolgert werden.