Selbstbalancierende Bäume: AVL- und Rot-Schwarz-Baum

Kurz: Suchbäume, die sich nach dem Einfügen und Löschen selbst umbauen, damit sie nicht zu einer langen Kette entarten und Operationen schnell bleiben.

Genauer: Ein binärer Suchbaum findet Werte in O(log n), wenn er ausgewogen ist. Fügt man aber sortierte Daten ein (1, 2, 3, 4, …), entsteht eine lange „Kette“ mit O(n) Aufwand. Selbstbalancierende Bäume erkennen solche Schieflagen und stellen das Gleichgewicht mit Rotationen wieder her.

Im Detail

Rotation

Eine Rotation ordnet einige Knoten um, ohne die Sortierung zu verletzen. Bei einer Rechtsrotation wird der linke Kindknoten zur neuen Wurzel dieses Teilbaums, der alte Knoten wird sein rechtes Kind. Sie dauert nur konstante Zeit, verkürzt aber die Höhe eines schiefen Teilbaums.

AVL-Baum

Benannt nach Adelson-Velsky und Landis (1962). Regel: Für jeden Knoten unterscheidet sich die Höhe von linkem und rechtem Teilbaum um höchstens 1 (Balancefaktor −1, 0 oder 1). Wird die Regel nach Einfügen oder Löschen verletzt, korrigieren einfache oder doppelte Rotationen den Baum. AVL-Bäume sind sehr streng ausbalanciert, die Suche ist besonders schnell, Einfügen und Löschen brauchen etwas mehr Umbau.

Rot-Schwarz-Baum

Jeder Knoten ist rot oder schwarz. Regeln: Die Wurzel ist schwarz; ein roter Knoten hat nur schwarze Kinder; jeder Pfad von einem Knoten zu den Blättern enthält gleich viele schwarze Knoten. Daraus folgt, dass der längste Pfad höchstens doppelt so lang ist wie der kürzeste. Er ist weniger streng als AVL, braucht aber im Mittel weniger Umbauten. Viele Standardbibliotheken nutzen ihn, zum Beispiel TreeMap und TreeSet in Java und std::map in C++.

Wann verwendet man was

Beide garantieren O(log n) für Suchen, Einfügen und Löschen. AVL passt bei vielen Lesezugriffen, Rot-Schwarz bei vielen Änderungen. In Datenbanken und Dateisystemen, wo Daten auf Festplatten liegen, nutzt man stattdessen B-Bäume, die mehrere Schlüssel je Knoten speichern und weniger Zugriffe brauchen.

Siehe auch: Baum-Datenstruktur, B-Baum und B+-Baum, Big-O-Notation, Binäre Suche