Rot-Schwarz-Baum
Der Rot-Schwarz-Baum einfach erklärt! In unserem Video findest du alle wichtigen Eigenschaften über diese besondere Variante der balancierten Binärbäume und erfährst dadurch, wann welchem Knoten entweder die Farbe rot oder schwarz zugeordnet werden muss. Zusätzlich zeigen wir dir anhand eines Beispiels das Rot-Schwarz-Baum Einfügen und das Rot-Schwarz-Baum Löschen.
Zusätzlich erfährst du in diesem Beitrag die Komplexität und potenzielle Datenstrukturen, die eine mögliche Alternative darstellen.
Inhaltsübersicht
Rot-Schwarz-Baum Definition
Der Rot-Schwarz-Baum (englisch red-black-tree) ist ein binärer Suchbaum der Informatik. Die Datenstruktur ist bekannt für seine Balance und die Rot-Schwarz-Eigenschaft all seiner Knoten, wodurch eine schnelle Zugriffszeit auf die gespeicherten Werte erreicht wird.
Rot-Schwarz-Bäume
Rot-Schwarz-Bäume, die auch als RS-Baum oder RB-Baum bekannt sind, wurden in ihrer ersten Form 1972 von Rudolf Bayer entwickelt und symmetric binary b-trees genannt. Auf dieser Variante Aufbauen kennt man die heutige Version der Rot-Schwarz-Bäume, die von Leonidas J. Guibas und Robert Sedgewick durch die rot-schwarz Farbkonvention 1978 weiterentwickelt wurden.
Rot-Schwarz-Eigenschaften
Ein Rot-Schwarz-Baum ist wie ein Binärer Suchbaum aufgebaut. Dabei hat der linke Teilbaum nur kleinere Elemente und der rechte Teilbaum nur größere Elemente als die Wurzel.
Damit ein Binärbaum effizient arbeiten kann, muss er möglichst ausgeglichen aufgebaut sein. Somit gilt dasselbe auch für Rot-Schwarz-Bäume!
Dafür sorgt die sogenannte Rot-Schwarz Eigenschaft. Was eigentlich nur bedeutet, dass jeder unserer Knoten dabei entweder rot oder schwarz ist. Dabei gelten die folgenden Regeln:
- Der Wurzelknoten immer schwarz ist.
- Sobald ein Knoten rot ist, müssen die beiden Kinder immer schwarz sein – heißt also, dass niemals zwei rote Knoten direkt hintereinander folgen können.
- Zusätzlich muss man noch darauf achten, dass alle Wurzel-Blatt-Pfade immer die gleiche Anzahl an schwarzen Knoten haben.
- Und zu guter Letzt sind alle Blätter mit dem Wert Null bzw. NIL schwarz.
Höhe
Durch diese Eigenschaften bleibt ein Rot-Schwarz-Baum stets balanciert. Deshalb gilt für die Höhe bzw. Tiefe, dass die Höhe von Rot-Schwarz-Bäumen mit 
– Werten nie größer als 
werden kann.
Die Schwarzhöhe eines Knotens – oft auch als Schwarztiefe betitelt – bezeichnet die Anzahl schwarzer Knoten auf direktem Pfad zu einem Blatt.
Die Schwarzhöhe von Rot-Schwarz-Bäumen bezeichnet die gesamte Schwarzhöhe der Wurzel.
Lemma
Der Beweis erfolgt über die Induktion über die Höhe h. Ein RS-Baum hat dabei:
- Minimum
- Maximum
Rot-Schwarz-Baum Suchen
Die Operation Suchen erfolgt innerhalb von Rot-Schwarz-Bäumen nach dem allgemeinen Prinzip binärer Suchbäume. Es unterscheidet sich somit durch die Suche mit oder ohne Duplikate. Sollten Duplikate vorhanden sein, ist es auch beim RS-Baum empfehlenswert die Suche nicht bei dem ersten richtigen Wert abzubrechen, sondern den Pfad weiter zu durchlaufen.
Rot-Schwarz-Baum Einfügen
Das Rot-Schwarz-Baum Einfügen erfolgt auf Basis des allgemeinen Binären Suchbaums. In diesem Fall wird zusätzlich der neu hinzugefügte Knoten rot gefärbt, um die Schwarzhöhe des Baums zu erhalten. Werden dabei die Bedingungen verletzt, müssen die Knoten des Baums entsprechend umgefärbt werden, um den Baum zu reparieren.
Dabei gibt es für die verschiedenen Fälle unterschiedliche Vorgehensweisen:
- Der neue Knoten ist die Wurzel.
- Ein neuer Knoten besitzt einen schwarzen Vater.
- Der Vater des neuen Knotens ist rot.
- Der hinzugefügte Knoten hat einen schwarzen Onkel und ist das rechte Kind eines roten Vaters.
- Ein hinzugefügter Knoten besitzt einen schwarzen Onkel und ist das linke Kind eines roten Vaters.
Beispiele
Beispiele für die Operation „Rot-Schwarz-Baum Einfügen“.
Für die Liste sind folgende Zahlen gegeben: 35, 9, 50, 57, 68, 43, 46.
Die neu hinzugefügten Zahlen sind dabei immer ein roter Knoten. Da die 35 aber auch gleichzeitig die Wurzel ist, muss sie zur Erfüllung der Bedingungen natürlich schwarz gefärbt werden.
Dann kann ganz normal die Zahl 9 und die Zahl 50 in den Baum einfügt werden. Nun zur 57. Die Bedingung lautet, dass niemals zwei rote Knoten hintereinander folgen dürfen. Da immer die letzte hinzugefügte Zahl der rote Knoten ist, muss die 50 entsprechend schwarz werden. Nun ist aber die Bedingung verletzt, dass die Anzahl der schwarzen Knoten aller Pfade gleich ist, entsprechend muss man die 9 ebenfalls schwärzen, damit wieder ein Gleichgewicht herrscht. Weiter geht es mit der 68. Hier muss zuerst eine Linksrotation ausgeführt werden. Da wiederum ein Verstoß gegen die Rot-Rot-Folge vorliegt, muss man die Zahlen wieder entsprechend anpassen, genau wie bei der 50 wegen der Pfade.
Nun zur 43. Um nicht gegen die Bedingungen zu verstoßen, muss die 50 zum schwarzen Knoten werden und um die Anzahl wieder auszugleichen, muss die 57 entsprechend rot werden, wodurch die 68 schwarz wird.
Als nächstes folgt die 46. Dabei muss man zuerst nach links rotieren, um danach eine Rechts-Rotation vorzunehmen. Entsprechend der Bedingungen müssen die Farben der Knoten 46 und 50 angepasst werden. Fertig!
Überprüfung der wichtigsten Bedingungen:
- Die Wurzel ist schwarz.
- Die roten Knoten haben immer schwarze Kinder.
- Und die Wurzel-Blatt-Pfade bestehen immer aus 3 schwarzen Knoten.
Rot-Schwarz-Baum Löschen
Wenn Werte aus einem Rot-Schwarz-Baum gelöscht werden soll, erfolgt dies analog zum Löschvorgang aus Binärbäumen. Wie auch beim Einfügen ist dabei wichtig, dass trotzdem weiterhin die Rot-Schwarz-Eigenschaft erhalten werden muss. Je nach Fall, müssen deshalb nach dem Entfernen die Farben entsprechend angepasst werden.
Beispiele
Nun Beispiele für die Operation „Rot-Schwarz-Baum Löschen“.
Möchte man beispielsweise den roten Knoten 50 löschen, funktioniert das ohne Probleme, da dadurch keine Bedingungen verletzt werden. Möchte man nun auch noch die 46 löschen, würde man in diesem Fall erstmals die Pfad-Bedingung missachten, da die Anzahl von schwarzen Knoten damit nicht ausgeglichen wäre. Entsprechend wird das Kind, also die 43 nun zu einem schwarzen Knoten. Dadurch sind die Bedingungen wieder entsprechend erfüllt.
Wie sieht das nun aber aus, wenn am Anfang direkt die 57 gelöscht worden wäre? Dabei handelt es sich zwar um einen roten Knoten, der sich aber in der Mitte des Baums befindet. Deshalb muss der gelöschte Knoten durch eins seiner Kinder ersetzt werden, in diesem Fall mit der 50. Der Vorgang erfolgt durch eine Links-Rotation. Dadurch, dass nun rot mit rot ersetzt wird, bleiben alle Bedingungen automatisch erhalten.
Im Fall, dass beispielsweise kein Kind als Ersatz hergenommen werden kann, muss mit weiteren Rotationen gearbeitet werden. Beispielsweise beim Löschen der 68, muss das Ungleichgewicht wieder ausgebessert werden. Wie gerade auch mit einer Linksrotation. Darauf folgt dann direkt eine Rechts-Rotation. Im Anschluss müssen die Farben wieder entsprechend angepasst werden.
Komplexität
Die Komplexität der Rot-Schwarz-Bäume stellt sich bei -Elementen wie folgt auf:
| Average-Case | Worst-Case | |
| Suchen |  |
|
| Einfügen |  |
|
| Löschen | |
|
Alternativen
Eine bekannte Alternative für den Rot-Schwarz-Baum ist der AVL Baum. Im direkten Vergleich stellt sich der AVL Baum als etwas schneller bei der Suche dar, zeigt jedoch vergleichsweise Schwächen bezüglich den Operationen Einfügen und Löschen.
Weitere Datenstrukturen die dem RS-Baum ähneln:
- (a,b)-Baum
- AA-Tree
- Splay Tree
- Skip Liste: Verkettete Liste mit zusätzlichen Abkürzungen