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.
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, 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.
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:
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.
Der Beweis erfolgt über die Induktion über die Höhe h. Ein RS-Baum hat dabei:
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.
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:
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:
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.
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.
Die Komplexität der Rot-Schwarz-Bäume stellt sich bei -Elementen wie folgt auf:
Average-Case | Worst-Case | |
Suchen | ![]() |
![]() |
Einfügen | ![]() |
![]() |
Löschen | ![]() |
![]() |
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:
Hallo, leider nutzt du einen AdBlocker.
Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.
Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.
Danke!
Dein Studyflix-Team
Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.