Coder Wiki | Algorithmen | Rot-Schwarz-Baum

Ein Rot-Schwarz-Baum ist in der Informatik eine vom binären Suchbaum abgeleitete Datenstruktur, welche sehr schnellen Zugriff auf die in ihr gespeicherten Werte garantiert.

Die schnellen Zugriffzeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente werden durch fünf Eigenschaften erreicht, welche zusammen garantieren, dass ein Rot-Schwarz-Baum immer balanciert ist, wodurch die Höhe eines Rot-Schwarz-Baumes mit n Werten nie größer wird als O(log₂ n). Somit können die wichtigsten Operationen in Suchbäumen – suchen, einfügen und löschen – garantiert in O(log₂ n) ausgeführt werden.

Einfügen

Das Einfügen in den Rot-Schwarz-Baum funktioniert wie das Einfügen in einen binären Suchbaum, wobei der neue Knoten rot gefärbt wird, damit die Schwarztiefe des Baumes erhalten bleibt. Nach dem Einfügen können jedoch eventuell die zweite oder – was wahrscheinlicher ist – die vierte Eigenschaft des Rot-Schwarz-Baumes verletzt sein, weswegen es nötig werden kann, den Baum zu reparieren. Hierbei unterscheidet man insgesamt fünf Fälle, welche im folgenden genauer betrachtet werden.

Fall 1 Der neu eingefügte Knoten ist die Wurzel des Baumes. Da hierdurch die zweite Eigenschaft verletzt wird (Die Wurzel des Baums ist schwarz) färbt man die Wurzel einfach um. Da dieser Fall nur eintritt, falls man ein Element in den leeren Baum einfügt, braucht man sich nicht um weitere Reparaturen zu kümmern, da es im Baum nach dem Einfügen nur diesen einen Knoten gibt, weswegen keine der weiteren Eigenschaften verletzt werden kann.

Fall 2 Der Vater des neuen Knotens ist schwarz. Hierdurch wird die fünfte Eigenschaft gefährdet, da der neue Knoten selbst wieder zwei schwarze NIL-Knoten mitbringt und somit die Schwarztiefe auf einem der Pfade um eins erhöht wird. Da der eingefügte Knoten selbst aber rot ist, und beim Einfügen einen schwarzen NIL-Knoten verdrängt hat, bleibt die Schwarztiefe auf allen Pfaden erhalten.

Fall 3 Sowohl der Onkel als auch der Vater des neuen Knotens sind rot. In diesem Fall kann man beide Knoten einfach schwarz färben, und im Gegenzug den Großvater rot färben, wodurch die fünfte Eigenschaft wiederhergestellt wird. Durch diese Aktion wird das Problem um ein Level nach oben verschoben, da durch den nun rot gefärbten Großvater die zweite oder vierte Eigenschaft verletzten sein könnte, weswegen nun der Großvater betrachtet werden muss. Dieses Vorgehen wird solange rekursiv fortgesetzt, bis keine der Regeln mehr verletzt wird.

Fall 4 Der neue Knoten hat einen schwarzen Onkel und ist das rechte Kind seines roten Vaters. In diesem Fall kann man eine Linksrotation um den Vater ausführen, welche die Rolle des einzufügenden Knotens und seines Vaters vertauscht. Danach kann man den ehemaligen Vaterknoten mit Hilfe des fünften Falles bearbeiten. Durch die oben ausgeführte Rotation wurde ein Pfad (im Bild mit 1 markiert) so verändert, dass er nun durch einen zusätzlichen Knoten führt, während ein anderer Pfad (im Bild mit 3 markiert) so verändert wurde, dass er nun einen Knoten weniger hat. Da es sich jedoch in beiden Fällen um rote Knoten handelt, ändert sich hierdurch an der Schwarztiefe nichts, womit die fünfte Eigenschaft erhalten bleibt.

Fall 5 Der neue Knoten hat einen schwarzen Onkel und ist das linke Kind seines roten Vaters. In diesem Fall kann man eine Rechtsrotation um den Großvater ausführen, wodurch der ursprüngliche Vater nun der Vater von sowohl dem neu einzufügenden Knoten als auch dem ehemaligen Großvater ist. Da der Vater rot war, muss nach der vierten Eigenschaft (Kein roter Knoten hat ein rotes Kind) der Großvater schwarz sein. Vertauscht man nun die Farben des ehemaligen Großvaters bzw. Vaters, so ist in dem dadurch entstehenden Baum die vierte Eigenschaft wieder gewahrt. Die fünfte Eigenschaft bleibt ebenfalls gewahrt, da alle Pfade, welche durch einen dieser drei Knoten laufen, vorher durch den Großvater liefen, und nun alle durch den ehemaligen Vater laufen, welcher inzwischen – wie der Großvater vor der Transformation – der einzige schwarze der drei Knoten ist.

Algorithmen

Rot-Schwarz-Baum

Einfügen

Weblinks