Im vorigen Beitrag haben wir die Einführung in Red-Black Trees besprochen. In diesem Beitrag geht es um die Einfügung. Bei der Einfügung von AVL-Bäumen haben wir die Rotation als Werkzeug verwendet, um nach der Einfügung einen Ausgleich zu schaffen. Im Red-Black-Baum verwenden wir zwei Werkzeuge, um den Ausgleich zu schaffen.
- Umfärben
- Rotation
Umfärben ist die Änderung der Farbe des Knotens, d.h. wenn er rot ist, wird er schwarz und umgekehrt. Es ist zu beachten, dass die Farbe des NULL-Knotens immer schwarz ist. Außerdem versuchen wir immer zuerst die Umfärbung, und wenn diese nicht funktioniert, versuchen wir es mit einer Rotation. Im Folgenden finden Sie einen detaillierten Algorithmus. Die Algorithmen haben hauptsächlich zwei Fälle, die von der Farbe des Onkels abhängen. Wenn der Onkel rot ist, färben wir ihn um. Wenn der Onkel schwarz ist, führen wir Rotationen und/oder Umfärbungen durch.
Die Darstellung, mit der wir arbeiten werden, ist:
Diese Darstellung basiert auf X
Logik:
Zunächst muss man den Knoten ähnlich wie in einem Binärbaum einfügen und ihm eine rote Farbe zuweisen. Wenn der Knoten ein Wurzelknoten ist, ändern Sie seine Farbe in schwarz, wenn nicht, prüfen Sie die Farbe des übergeordneten Knotens. Wenn seine Farbe schwarz ist, dann ändern Sie die Farbe nicht, aber wenn nicht, d.h. wenn sie rot ist, dann prüfen Sie die Farbe des Onkels des Knotens. Wenn der Onkel des Knotens eine rote Farbe hat, dann ändere die Farbe des Elternteils und des Onkels des Knotens in schwarz und die des Großvaters in rot und wiederhole den gleichen Vorgang für ihn (d.h. den Großvater).
Wenn aber der Onkel des Knotens eine schwarze Farbe hat, dann gibt es 4 mögliche Fälle:
- Linker Fall (LL-Rotation):
- Linker Fall (LR-Rotation):
- Right Right Case (RR Rotation):
- Right Left Case (RL Rotation):
Nun, nach diesen Rotationen, wenn die Farben der Knoten nicht übereinstimmen, dann färbe sie neu.
Algorithmus:
Lassen Sie x den neu eingefügten Knoten sein.
- Standard BST-Einfügung durchführen und die Farbe der neu eingefügten Knoten auf ROT setzen.
- Wenn x die Wurzel ist, ändern Sie die Farbe von x auf SCHWARZ (Schwarze Höhe des gesamten Baums erhöht sich um 1).
- Verfahren Sie wie folgt, wenn die Farbe des Elternteils von x nicht SCHWARZ ist und x nicht die Wurzel ist.
a) Wenn der Onkel von x ROT ist (Großeltern müssen ab Eigenschaft 4 schwarz gewesen sein)
(i) Ändere die Farbe der Eltern und des Onkels in SCHWARZ.
(ii) Farbe eines Großelternteils als ROT.
(iii) Ändere x = x’s Großelternteil, wiederhole die Schritte 2 und 3 für das neue x.b) Wenn der Onkel von x SCHWARZ ist, dann kann es vier Konfigurationen für x geben, x’s Elternteil (p) und x’s Großelternteil (g) (Dies ist ähnlich wie AVL Tree)
(i) Left Left Case (p ist linkes Kind von g und x ist linkes Kind von p)
(ii) Left Right Case (p ist linkes Kind von g und x ist das rechte Kind von p)
(iii) Right Right Case (Spiegelung von Fall i)
(iv) Right Left Case (Spiegelung von Fall ii)
Beispiel: Erstellen eines rot-schwarzen Baumes mit den Elementen 3, 21, 32 und 17 in einem leeren Baum.
Lösung:
Wenn das erste Element eingefügt wird, wird es als Wurzelknoten eingefügt und da der Wurzelknoten schwarz ist, erhält er die Farbe schwarz.
Das neue Element wird immer mit roter Farbe eingefügt und als 21 > 3, so dass es Teil des rechten Teilbaums des Wurzelknotens wird.
Wenn wir nun 32 einfügen, sehen wir, dass es ein rotes Vater-Kind-Paar gibt, das gegen die Rot-Schwarz-Baumregel verstößt, so dass wir es umdrehen müssen. Außerdem sehen wir die Bedingungen der RR-Rotation (der Nullknoten des Wurzelknotens wird als schwarz betrachtet), so dass nach der Rotation der Wurzelknoten nicht rot sein kann, so dass wir den Baum neu färben müssen, was zu dem oben gezeigten Baum führt.
Wenn wir nun das neue Element einfügen, erscheinen der übergeordnete Knoten und der untergeordnete Knoten mit roter Farbe wieder, und hier müssen wir sie neu einfärben. Wir sehen, dass sowohl der Elternknoten als auch der Onkelknoten rot gefärbt sind, also ändern wir einfach ihre Farbe in Schwarz und die Farbe des Großvaters in Rot. Da der Großvater der Wurzelknoten ist, ändern wir seine Farbe wieder in Schwarz, was zu dem oben gezeigten Baum führt.
Endgültige Baumstruktur:
Der endgültige Baum sieht wie folgt aus
Für die vollständige Implementierung des obigen Algorithmus siehe C-Programm für Rot-Schwarz-Baum-Einfügung.
Rot-Schwarz-Baum | Satz 3 (Löschen)