Ein Rot-Schwarz-Baum (engl. Red-Black Tree) ist ein selbstbalancierender binärer Suchbaum: Er hält sich bei jedem Einfügen und Löschen automatisch im Gleichgewicht und garantiert damit für Suchen, Einfügen und Löschen eine Laufzeit von O(log n) im schlechtesten Fall. Die Idee: Jeder Knoten bekommt eine Farbe (rot oder schwarz), und ein paar einfache Färbungsregeln sorgen dafür, dass der Baum nie zu schief wird. Die Grundlagen des Suchbaums behandelt der Artikel Binärer Suchbaum.
Die fünf Rot-Schwarz-Regeln
- Jeder Knoten ist entweder rot oder schwarz.
- Die Wurzel ist schwarz.
- Alle Blätter (die NIL-Knoten) sind schwarz.
- Ein roter Knoten hat ausschließlich schwarze Kinder — es gibt also keine zwei roten Knoten direkt hintereinander.
- Jeder Pfad von einem Knoten zu einem Blatt enthält gleich viele schwarze Knoten (gleiche Schwarz-Höhe).
Wie die Balance gehalten wird
Beim Einfügen oder Löschen kann eine Regel verletzt werden. Dann greifen zwei Reparatur-Werkzeuge: Rotationen (Links- und Rechtsrotation) richten die Baumstruktur neu aus, und das Umfärben von Knoten stellt die Färbungsregeln wieder her. Jede dieser Reparaturen läuft in O(log n) ab. Aus den Regeln folgt, dass der längste Pfad höchstens doppelt so lang ist wie der kürzeste — die Höhe des Baums bleibt damit bei etwa 2 mal log2 von (n+1).
Rot-Schwarz-Baum vs. AVL-Baum
Der AVL-Baum hält die Höhe strikter im Gleichgewicht (maximal etwa 1,44 mal log n) und ist deshalb bei vielen Suchoperationen etwas schneller — zahlt dafür aber häufiger Rotationen. Der Rot-Schwarz-Baum erlaubt eine etwas größere Höhe, benötigt dafür aber weniger Rotationen beim Einfügen und Löschen. Beide sind Verfeinerungen des Binärbaums beziehungsweise der Baum-Datenstruktur.
Wofür Rot-Schwarz-Bäume verwendet werden
- Java: TreeMap und TreeSet
- C++: std::map und std::set
- Linux-Kernel: Completely Fair Scheduler (Prozess-Verwaltung) und epoll
- Nginx: Timer- und Event-Verwaltung
Die Garantie von O(log n) pro Operation macht den Rot-Schwarz-Baum zur ersten Wahl, wenn eine geordnete Datenstruktur mit vorhersagbarer Laufzeit gebraucht wird — siehe auch Big-O-Notation. Als ungeordnete Alternative mit O(1)-Zugriff dient die Hash-Tabelle.
Verwandte Grundlagen: Binärer Suchbaum, AVL-Baum, Binärbaum, Baum-Datenstruktur, Big-O-Notation, Hash-Tabelle.