Quelltext der Seite Rot-Schwarz-Baum

{| class="wikitable float-right" style="text-align:right;"
|-
! colspan="3" style="background:#C0C0FF"| Rot-Schwarz-Baum
|-
|
|colspan="2" style="text-align:center;"| [[Landau-Symbole|Komplexität]]<br/>bei <math>n</math> Elementen
|-
!style="text-align:left;"| Platz
|colspan="2"| <math>\mathcal{O}(n)</math>
|-
!style="text-align:left;vertical-align:top;"| Operation
| im Mittel,<br/>[[#Durchschnittliche und amortisierte Laufzeit|amortisiert]]
|style="vertical-align:top;"| [[Worst Case]]
|-
!style="text-align:left;"| [[#Suchen|Suchen]]
| <math>\mathcal{O}(\log n)</math>
| <math>\mathcal{O}(\log n)</math>
|-
!style="text-align:left;"| [[#Traversieren|Querschritt]]
| <math>\mathcal{O}(1)</math>
| <math>\mathcal{O}(\log n)</math>
|-
!style="text-align:left;"| [[#Aufsuchen erstes oder letztes Element|Min, Max]]
| <math>\mathcal{O}(\log n)</math>
| <math>\mathcal{O}(\log n)</math>
|-
!style="text-align:left;"| [[#Operation Einfügen|Einfügen]]
| <math>\mathcal{O}(1)</math>{{FN|†}}
| <math>\mathcal{O}(\log n)</math>
|-
!style="text-align:left;"| [[#Operation Löschen|Löschen]]
| <math>\mathcal{O}(1)</math>{{FN|†}}
| <math>\mathcal{O}(\log n)</math>
|-
|colspan="3" style="text-align:left;"| {{FNZ|†|ohne [[#Navigationsoperationen|Navigation]] (nur [[#Durchschnittliche und amortisierte Laufzeit|Rebalancierung]])}}
|-
|colspan="3" style="text-align:left;"| <small>Platz- und Zeit-Komplexitäten</small>
|}
Ein '''Rot-Schwarz-Baum''', auch '''RS-Baum''' oder '''RB-Baum''', ({{enS|'''red–black tree'''}} oder '''''RB tree''''') ist eine [[Datenstruktur]] vom Typ [[binärer Suchbaum]], die [[Binärer Suchbaum#Motivation|„sehr schnellen“ Zugriff]] auf die in ihr gespeicherten Schlüssel garantiert. Rot-Schwarz-Bäume wurden zuerst 1972 von [[Rudolf Bayer (Informatiker)|Rudolf Bayer]] beschrieben,<ref>{{cite journal
|author=[[Rudolf Bayer (Informatiker)|Rudolf Bayer]]
|title=Symmetric Binary B-Trees. Data Structure and Maintenance Algorithms
|language=en
|journal=Acta Informatica
|volume=1
|pages=290–306 |year=1972
|doi=10.1007/BF00289509}}</ref> welcher sie ''symmetric binary B-trees'' nannte. Der heutige Name geht auf [[Leonidas J. Guibas]] und [[Robert Sedgewick (Informatiker)|Robert Sedgewick]] zurück, die 1978 die rot-schwarze Farbkonvention einführten.<ref>{{cite journal
|first=Leo J.
|last=Guibas |coauthors=Robert Sedgewick
|title=A Dichromatic Framework for Balanced Trees
|language=en
|journal= Proceedings of the 19th Annual Symposium on Foundations of Computer Science |pages=8–21
|publisher=IEEE Computer Society |year=1978}}</ref> Die schnellen Zugriffszeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente (meist Paare vom Typ (Schlüssel,Wert)) werden durch zwei Forderungen erreicht, die die [[Balancierter Baum|Balance]] des Baums in einer Weise festlegen, dass die Höhe eines Baums mit <math>n</math> Elementen nie größer als <math>2 \log_2(n\!+\!2)\!-\!2</math> sein kann.<ref group="Anm.">Diese Abschätzung ist scharf (s.&nbsp;Abschnitt [[#Höhenbeweis|Höhenbeweis]])
und für <math>n > 0</math> wegen
:<math>2\log_2(n+2)-2 = 2\log_2(n/2+1) < 2\log_2(n+1)</math>
marginal genauer als das [[#Cormen2001|vielzitierte]]
:<math>2 \log_2(n+1)</math>.</ref> Somit können die wichtigsten Operationen in Suchbäumen – ''[[Binärer Suchbaum#Suchen|Suchen]]'', ''[[Binärer Suchbaum#Einfügen|Einfügen]]'' und ''[[Binärer Suchbaum#Löschen|Löschen]]'' – garantiert in <math>\mathcal O(\log n)</math> (s.&nbsp;[[Landau-Symbole]]) ausgeführt werden.

== Definition ==
Zusätzlich zu den Eigenschaften des [[Binärer Suchbaum|binären Suchbaums]] hat jeder [[Knoten (Graphentheorie)|Knoten]] des Rot-Schwarz-Baums ein weiteres Attribut, genannt »Farbe«, das zwei Werte annehmen kann, genannt »rot« (<code>RED</code>) und »schwarz« (<code>BLACK</code>). Diese Einfärbung hat die folgenden zwei Forderungen zu {{nowrap|erfüllen:<ref>Der Text folgt [[#Pfaff a|Ben Pfaff: ''An Introduction to Binary Search Trees and Balanced Trees'']]. Zu anderen Varianten der Forderungen s.&nbsp;die Anmerkung [[#NIL-Knoten|NIL-Knoten]].</ref>}}
{|
|-
|style="width:22em;"|
* Forderung '''!RR'''   (»Nicht Rot-Rot«):
*
| Ein [[Gewurzelter Baum#Weitere Begriffe|Kindknoten]] eines roten Knotens ist schwarz.
|-
|style="vertical-align:-9px;"|
* Forderung '''S#='''   (»Schwarz-Zahl Gleich«):
*
|style="vertical-align:9px;"| Jeder [[Weg (Graphentheorie)|Pfad]] von einem gegebenen Knoten zu einem seiner [[Gewurzelter Baum#Weitere Begriffe|Nachfahren]] mit [[Grad (Graphentheorie)#Gerichtete Graphen|Ausgangsgrad]] ≤1, d.&nbsp;h. zu Blättern oder [[Halbblatt|Halbblättern]], im Folgenden kurz ''Pfadenden'' {{nowrap|genannt,<ref>bei [[#Pfaff a|Ben Pfaff]] ''non-branching node''</ref>}} enthält die gleiche Anzahl schwarzer Knoten.
|}
[[Datei:Red-black tree example nN.svg|322px|mini|Rot-Schwarz-Baum<br/>der Baumhöhe 4 und der Schwarzhöhe 2]]
{{Anker|HalbblattBlatt}}Eine unmittelbare Folge aus den Forderungen ist, dass ein Halbblatt (bspw. der Knoten <math>\mathsf{1}</math> im Beispielbaum) schwarz und sein (einzelnes) Kind (der Knoten <math>\mathsf{6}</math>) rot sein muss, denn beide sind Pfadenden, und der Pfad zum Pfadende {{nowrap|<math>\mathsf{1}</math><sub>links</sub>}} ist um genau den Knoten <math>\mathsf{6}</math> kürzer.

Aus beiden Forderungen zusammen folgt ähnlich unmittelbar, dass ein schwarzer Knoten, der nicht die Wurzel ist, ein Geschwister hat.

=== Schwarzhöhe, Baumhöhe ===
{{Anker|Schwarzhöhe|Schwarztiefe}}Die auf allen Pfaden von Pfadende zu [[Wurzel (Graphentheorie)|Wurzel]] gleiche Anzahl <math>s</math> schwarzer Knoten wird die »Schwarzhöhe« ({{enS|black height}})<ref>Bei [[#Pfaff a|Ben Pfaff]] ist die Schwarzhöhe eines Knotens die einheitliche Anzahl schwarzer Knoten auf allen Pfaden zu den Pfadenden im von ihm gewurzelten Teilbaum.</ref><ref>[[#Mehlhorn2|Mehlhorn 2008 S. 155]] färbt die [[Kante (Graphentheorie)|''Kanten'']] rot/schwarz und zählt als Schwarztiefe ({{enS|black depth}}) eines Knotens die Zahl der schwarzen Kanten von ihm zur Wurzel.</ref> genannt: des ''Baums'', aber auch seiner ''Wurzel''. Nach dieser Definition ist ein Knoten der Schwarzhöhe 0 ein rotes Blatt (dann ist seine Baumhöhe 1) wie bspw. die Knoten <math>\mathsf{6, 22, 27}</math> im Beispielbaum – oder ein [[#Nullknoten|unechter (und leerer)]] Knoten mit der Baumhöhe 0. In diesem Artikel sind schwarze Knoten echt (und Schlüssel tragend) und haben sowohl Schwarzhöhe wie Baumhöhe {{nowrap|≥ 1.}}
Die roten Knoten <math>\mathsf{8, 17},</math> aber auch die schwarzen Knoten <math>\mathsf{1, 11, 15, 25},</math> haben Schwarzhöhe 1. Die schwarzen Knoten <math>\mathsf{1, 25}</math> haben Baumhöhe 2, die Knoten <math>\mathsf{11, 15}</math> Baumhöhe 1, und <math>\mathsf{1}</math> ist der einzige Knoten mit Ausgangsgrad 1, das einzige Halbblatt.

Durch die zwei Forderungen<ref name="Schwarzwurzel">Einige Autoren fordern noch, dass die Wurzel des Baums schwarz zu färben sei. Nicht jedoch z.&nbsp;B. [[#Mehlhorn2|Mehlhorn 2008]] und [[#Sedgewick|Sedgewick]]. Tatsächlich ist diese Forderung ohne merkliche Bedeutung für das Laufzeitverhalten und stört die [[Rekursivität]] der Algorithmen etwas. Nun verletzt die Umfärbung einer roten Wurzel in schwarz keine der anderen Forderungen. In den Algorithmen für Einfügung und Löschung kann man jedoch mit einer Fallunterscheidung weniger auskommen, wenn man bei einem roten Knoten immer einen [[Gewurzelter Baum#Weitere Begriffe|Elterknoten]] voraussetzen kann.</ref> wird die wichtigste Eigenschaft von Rot-Schwarz-Bäumen sichergestellt:

Ist <math>s</math> die Schwarzhöhe des Baums, dann gibt es wegen der {{nowrap|1=Forderung '''S#='''}} auf einem Pfad von der Wurzel zu einem Pfadende genau <math>s</math> schwarze Knoten, aber wegen der {{nowrap|Forderung '''!RR'''}} höchstens einen roten Knoten mehr als schwarze, also insgesamt maximal <math>2s\!+\!1</math> Knoten.
Damit gilt für die Zahl <math>n</math> aller Knoten im Baum {{nowrap|<math>2^s\!\!-\!\!1 \le n \le 2^{2s+1}\!\!-\!\!1</math>,}} so dass der Rot-Schwarz-Baum immer gut genug [[Balancierter Baum|balanciert]] ist – auf jeden Fall so gut, dass das Verhältnis zwischen der [[Höhe (Graphentheorie)|Baumhöhe]] <math>h ,</math> für die <math>s \le h \le 2s\!+\!1</math> gilt, und dem [[Logarithmus]] der Knotenzahl <math>n</math> beschränkt bleibt. Diese logarithmische Beschränkung, die im Abschnitt [[#Höhenbeweis|Höhenbeweis]] formal bewiesen wird, ist aber gleichzeitig das informationstheoretische Optimum, d.&nbsp;h. es gibt [[Binärbaum#Vollständiger Binärbaum und vollständig balancierter Binärbaum|keinen Binärbaum]] mit kleinerer maximaler Pfadlänge <math>h\!\!-\!\!1 \in \mathcal{O}(\log n).</math>

Bei den herausgehobenen Operationen ''Suchen'', ''Einfügen'' und ''Löschen'' ist der auf einer Ebene des Baums anfallende Aufwand konstant. Also ist die Laufzeit höchstens proportional zur Anzahl der Knoten in einem Pfad, die wieder durch die Höhe limitiert ist, welche ihrerseits durch den Logarithmus der Knotenzahl limitiert ist.

=== NIL-Knoten ===
Dieser Artikel nimmt die im Artikel ''[[Binärer Suchbaum#Unterschiedliche Sprechweisen|Binärer Suchbaum]]'' in dessen Abb. 1A aufgezeigte und bei vielen Baumstrukturen übliche Sichtweise ein, bei der die Knoten die Schlüssel tragen ([[Binärer Suchbaum#Knotenorientierte und blattorientierte Speicherung|knotenorientierte Speicherung]]), unabhängig davon, ob sie interne Knoten oder (interne) Blätter sind.

[[Datei:Red-black tree example with NIL.svg|322px|mini|Derselbe Rot-Schwarz-Baum mit NIL-Knoten<br/>(Baum- und Schwarzhöhe sind 4 und 2 – wie oben)]]
Sehr verbreitet in der Literatur über Rot-Schwarz-Bäume ist die nebenstehende und im Artikel ''Binärer Suchbaum'' in dessen Abb. 1B gezeigte Sichtweise, bei der – ebenfalls knotenorientiert – die die Schlüssel tragenden Knoten als ''intern'' angesehen werden, dem Baum aber zusätzliche Knoten, so genannte »NIL-Knoten«, als ''externe'' Blätter angeheftet sind, die an den Pfadenden für die (randlosen, „offenen“) Intervalle ({{enS}} auch ''missing nodes''<ref name="persistentRB">J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan: ''Making Data Structures Persistent.'' In: ''Journal of Computer and System Sciences.'' Band 38, No. 1, 1989 ([http://www.cs.cmu.edu/~sleator/papers/Persistence.htm cs.cmu.edu])</ref>) ''zwischen'' den Schlüsseln stehen. Die Darstellung mit {{nowrap|1=<span style="background:#000000"><span style="color:#FFFFFF">&nbsp;'''NIL'''&nbsp;</span></span>-Knoten}} bringt das einseitige Pfadende {{nowrap|<math>\mathsf{1}</math><sub>links</sub>}} (links am Knoten {{nowrap|<math>\mathsf{1}</math>)}} ähnlich deutlich heraus wie die paarigen Pfadenden an den Knoten <math>\mathsf{6,11,15,22,27}.</math> Völlig unabhängig von der grafischen Darstellung lassen sich die NIL-Knoten sowohl als unterschiedslose [[Nullzeiger]] wie als unterschiedslose Zeiger zu ein und demselben [[Sentinel (Programmierung)|Wächterknoten]] implementieren.
Diese Option beim Zeigerwert wird zur Unterscheidung vom Nullzeiger im Text als {{nowrap|NIL-Zeiger}} oder NIL und im Beispielcode als <code>NIL</code> kenntlich gemacht.

Werden die NIL-Knoten jedoch als individuelle Knoten aufgefasst, dann kommt für sie eine Forderung hinzu, so dass folgende drei Forderungen aufzustellen {{nowrap|sind:<ref name=Cormen2001>{{BibISBN|0262032937}}</ref>{{rp|273}}}}
* NIL-Knoten sind schwarz.
* Kinder eines roten Knotens sind schwarz.
* Die Anzahlen schwarzer Knoten in einem Pfad von einem gegebenen Knoten zu jedem seiner NIL-Knoten sind gleich.
Diese Auffassung hat für das Verständnis der Sachverhalte vernachlässigbaren Nutzen und hat bei „naiver“ Implementierung eher einen ungünstigen Einfluss.<ref group="Anm.">Werden nämlich die NIL-Knoten als minimale Rot-Schwarz-Knoten implementiert, so brauchen sie Speicher für zwei Kindzeiger, ggf. einen Elterzeiger, das Feld für die Farbe und ein Erkennungsfeld für die Eigenschaft »NIL-Knoten«. Bei <math>n</math> Schlüssel tragenden Knoten braucht man <math>n+1</math> NIL-Knoten, womit sich der Rot-Schwarz-[[Overhead (EDV)|Overhead]] mehr als verdoppelt. Die Verknüpfungen der NIL-Knoten mit den Schlüssel tragenden Knoten (bspw. bei den Rotationen) sind überdies zu pflegen, so dass sich auch die Laufzeit verlängert. Das bedeutet im Ergebnis einen erheblichen Aufwand für das Aufzeichnen und Pflegen von Informationen, die für die nachfolgenden Algorithmen nicht gebraucht werden oder sich unmittelbar aus den anderen Informationen herleiten lassen.</ref>

=== Datenstruktur ===
Der nachfolgende Beispielcode, der in der [[C (Programmiersprache)|Programmiersprache C]] formuliert ist, nimmt Bezug auf eine Deklaration des Baumknotens der folgenden Art:
{{Anker|logGleich}}
<syntaxhighlight lang="c" line start="10">
 struct RBnode  // Knotenfeld
 {
   struct RBnode* child[2]; // Zeiger zu ≤2 Kindknoten dieses Knotens
                // oder NIL: kein Kindknoten
   byte color;  // RED oder BLACK
   ...          // Benutzer-Daten (z. B. Schlüssel, Wert)
 } ;

 #define LEFT  0
 #define RIGHT 1
 #define left  child[LEFT]  // -> linker  Kindknoten
 #define right child[RIGHT] // -> rechter Kindknoten
 #define RED   0
 #define BLACK 1
</syntaxhighlight>
{{Anker|Nullknoten}}Befindet sich NIL an einer Stelle im Baum, an der syntaktisch ein Zeiger zu einem Knoten erwartet wird, so soll dies verabredungsgemäß das ''Fehlen'' eines Knotens (einen Null- oder auch Wächterknoten) an dieser Stelle des Baums bedeuten (der Knoten gilt als ''unecht''). M.&nbsp;a.&nbsp;W.: der von einem NIL-Knoten gewurzelte Teilbaum ist ''leer'' und hat Schwarz- und Baumhöhe 0.
Sein Zeigerwert {{nowrap|1=<code>X == NIL</code>}} ist weniger wichtig als der Ort, wo dieser Wert in der [[#Datenstruktur|Datenstruktur]] steht. Dieser Ort gibt die graphentheoretischen Beziehungen zu den anderen Elementen des Baums an:
: Ohne selbst einen Knoten zu repräsentieren, kann er in Kindesbeziehung, und damit auch in Geschwister- und Onkelbeziehung zu anderen Knoten stehen – niemals aber ein Elter sein.<br/>Seine Baumhöhe und Schwarzhöhe gelten beide als 0, und Farbe ist ihm auch nicht zugeordnet. Er hat einen Elter (wenn er die Wurzel ist, den Baum als logischen Elter), aber niemals einen Zeiger zum Elter.<br/>Funktionell entspricht er exakt dem [[#NIL-Knoten|NIL-Knoten]], ohne dass ihm allerdings irgendeine Individualität zukäme.

Werden der Datenstruktur Rot-Schwarz-Baum Operationen zum Zugriff und zur Verwaltung beigegeben, so werden diese nur dann als zugehörig angesehen, wenn sie die Rot-Schwarz-Forderungen aufrechterhalten, indem sie insbesondere den Baum nach einer modifizierenden Operation überprüfen und wenn nötig reparieren. So erweitert wird die Datenstruktur zu einem [[Abstrakter Datentyp|Abstrakten Datentyp (ADT)]]. Bei Suchbäumen gibt es im Englischen dafür auch die Charakterisierung als ''self-balancing tree''.

== {{Anker|Traversieren|Aufsuchen erstes oder letztes Element}} Navigationsoperationen ==
Die Navigationsoperationen, das sind die [[Binärer Suchbaum#Suchen|verschiedenen Suchoperationen]], das ''Traversieren'', ''Aufsuchen erstes oder letztes Element'' und ähnliche, lassen den Baum unverändert (nur lesender Zugriff) und funktionieren im Prinzip auf jedem [[Binärer Suchbaum|binären Suchbaum]]. Die dortigen Algorithmen und Angaben zur Komplexität gelten genauso für Rot-Schwarz-Bäume – mit der Präzisierung, dass die Höhe des Rot-Schwarz-Baums sich immer logarithmisch zur Anzahl der Knoten verhält.

{{Anker|Suchen}}Das ''Suchen'' eines Elements (oder einer Lücke) anhand seines Schlüssels ist die wichtigste unter den Navigationsoperationen. (Die {{nowrap|(Höhen-)Balancierung}} des Rot-Schwarz-Baums versucht, auf diese Operation hin zu optimieren.) Sie unterstützt eine Art [[Wahlfreier Zugriff|''direkten'' Zugriff]] (im Gegensatz zum [[Sequentieller Zugriff|''sequentiellen'' Zugriff]] der [[Binärbaum#Traversierung|Traversierung]]) und wird in der Regel als vorausgehende Operation bei den Modifikationsoperationen (Einfügen oder Löschen) zum Auffinden der betreffenden Stelle im Baum eingesetzt.

Das Suchen setzt eine [[Quasiordnung#Totale Quasiordnung|totale Quasiordnung]] auf der Menge der Schlüssel voraus, die am flexibelsten durch eine [[Binärer Suchbaum#Ordnungsrelation|Vergleichsfunktion]] realisiert wird. Wenn Duplikate im Baum erlaubt sein sollen, dann empfiehlt sich eine leicht [[Binärer Suchbaum#Suchen, wenn Duplikate zulässig|abgewandelte Suchfunktion]].

== {{Anker|ZE}}Zeichenerklärung zu den Diagrammen ==
Die komplizierteren Einzelfälle der Einfüge- und Löschoperation werden weiter unten in Diagrammen skizziert.
Diese Diagramme stellen die für die Rebalancierung relevanten Beziehungen und Farben von Knoten heraus.

Ein Diagramm hat drei Spalten, wobei die linke Spalte die Überprüfung auf der untersten Stufe (ersten Iteration) eines Falles und die rechte die auf einer höheren Ebene desselben Falles beschreibt.
Die mittlere Spalte unterteilt die Transformation in mindestens zwei Abschnitte:
# Der erste (und oberste, mit »Bedingung« beschriftete) Abschnitt zeigt die Ausgangskonstellation,
# eine eventuelle »Rotation« folgt im nächsten Schritt,
# danach eine »Umfärbung«, falls erforderlich.
# Wenn der Baum dann noch nicht rebalanciert ist, zeigt der letzte (mit »Neuzuweisung« beschriftete) Abschnitt die Konstellation nach der erneuten Zuweisung des Problemknotens <math>\mathsf{N}</math> und der durch ihn bestimmten anderen Knoten. Diese Konstellation wird zur Weiterbehandlung an den in der Spalte {{nowrap|→''Test''}} eingetragenen Fall übergeben.

Die erste ''Iterationsstufe'' spielt sich auf der tiefstmöglichen Ebene des Baums ab. Dies gilt für Einfügungen wie auch [[#Löschen0|erstaunlicherweise]] für Löschungen. Da Schwarzhöhen und Baumhöhen auf sie bezogen werden können, soll diese Iterationsstufe auch einen Namen als Variable haben, und zwar den Buchstaben <math>j</math> mit dem ersten Wert {{nowrap|<math>j\!=\!1</math>}} mit der Folge, dass in den komplizierteren Fällen der Problemknoten <math>\mathsf{N}</math> in der ersten Iterationsstufe die Schwarzhöhe <math>j-1\!=\!0</math> und in den höheren <math>j-1 \ge 1</math> hat.

Obwohl die Konstellation der untersten Stufe <math>j\!=\!1</math> in denen der höheren im Prinzip enthalten ist, werden die sie betreffenden Diagramme um der größeren Deutlichkeit willen gebracht, und zwar ohne leere Teilbäume.<br/>Beim Löschen wird in der untersten Stufe das Pfadende, das einen schwarzen Knoten verloren hat (und das dem Problemknoten <math>\mathsf{N}</math> entspricht, der hier leer ist), durch einen blauen Pfeil nach links [[Datei:nilBlue.svg|grundlinie]] markiert.

# Der alte Problemknoten (<math>\mathsf{N}</math> im Abschnitt »Bedingung« eines Diagramms) hat eine blaue Kontur; und wenn die Operation nicht beendet ist, dann auch der neue (im Abschnitt »Neuzuweisung«).
# Das Symbol [[Datei:BlackNode.svg|13px|grundlinie]] stellt einen (echten) schwarzen und [[Datei:RedNode.svg|grundlinie]] einen (echten) roten Knoten dar.
# Das Symbol [[Datei:TriangleTop.svg|grundlinie]] stellt einen {{nowrap|'''!RR'''-konform}} bei seinem Elter angebundenen Teilbaum dar. Er hat (außer in den Abschnitten »Neuzuweisung«) die Schwarzhöhe <math>j\!-\!\!1</math>. {{Anker|Schwarzhöhe0}} Die Schwarzhöhe ist in der ersten Iterationsstufe 0; dann besteht der Teilbaum entweder
#* aus einem roten Blatt oder
#* er ist leer, also ein NIL-Knoten, wann der „Knoten“ auch als ''unecht'' gilt.
# Das Dreieck [[Datei:TriangleSubtree.svg|grundlinie]] (ohne die kleine schwarze Kreisfläche an der Spitze) symbolisiert einen {{nowrap|'''!RR'''-konform}} bei seinem Elter angebundenen Teilbaum, dessen Schwarzhöhe <math>j\!-\!\!2</math> ist. Seine Schwarzhöhe ist also um 1 niedriger als die der {{nowrap|[[Datei:TriangleTop.svg|grundlinie]]-Teilbäume.}} In der ersten Iterationsstufe wäre die Schwarzhöhe negativ, was so zu interpretieren ist, dass schon sein Elter leer ist.
# Zweimal [[Datei:RedOrBlackNode.svg|grundlinie]] in einem Diagramm oder auf einer Zeile der Zusammenschau bedeutet zweimal dieselbe Knotenfarbe, schwarz oder rot.

== Operation Einfügen ==
Die ersten Aktionen beim Einfügen eines neuen Knotens <math>\mathsf{N}</math> in einen Rot-Schwarz-Baum unterscheiden sich nicht von denen eines allgemeinen [[Binärer Suchbaum#Einfügen|binären Suchbaums]]: Der [[Zeiger (C)|Zeiger]] zum neuen Knoten ersetzt einen {{nowrap|NIL-Zeiger,}} der an einem ''Pfadende'' steht und als Indikator für das Fehlen entweder der Wurzel, falls der Baum leer ist, oder – bei einem Schlüssel tragenden Knoten <math>\mathsf{P}</math> – für die Abwesenheit des linken oder des rechten Kindes steht.

Im unten stehenden Beispielcode wird angenommen, dass diese Richtung, die das letzte Ungleich-Ergebnis einer Suche nach dem Schlüssel von <math>\mathsf{N}</math> reflektiert, im [[Parameter (Informatik)|Funktionsparameter]] <code>dir</code> ∈ {<code>LEFT,RIGHT</code>} übergeben {{nowrap|wird.<ref group="Anm.">Dabei ist <code>dir == LEFT</code> &nbsp; &nbsp; &nbsp; <math>\Longleftrightarrow</math> &nbsp; &nbsp; &nbsp; Schlüssel von <math>\mathsf{N}</math> < Schlüssel von <math>\mathsf{P}</math>.<br/>S.&nbsp;a. [[Binärer Suchbaum#Suchen, wenn Duplikate zulässig]].</ref>}}
Ferner wird angenommen, dass diese Suchfunktion den [[Stapelspeicher|Stapel]] {{nowrap|<code>struct RBnode* Parents[]</code>}} der Vorfahren von <math>\mathsf{P}</math> gebildet {{nowrap|hat.<ref name="Stapel">Die Implementierung kommt auf diese Weise (wie auch [[#Pfaff a|Ben Pfaff]] – zumindest konzeptionell) ''ohne'' einen bei den Knoten gespeicherten Elterzeiger aus.<br/>Zur Größe eines solchen Stapels [[#Stapelgröße|s. Stapelgröße]].<br/>Werden allerdings [[Binärer Suchbaum#Mehrere Zugriffspfade|mehrere Zugriffspfade]] zum selben Suchbaum benötigt, dann kann die Implementierung mit Elterzeiger bessere Laufzeiten ergeben als die Wiederholung von Suchvorgängen.</ref>}} Der ebenfalls übergebene Zeiger <code>struct RBnode** pParent</code> zeigt in diesem Stapel auf den Zeiger des direkten Elters des einzufügenden Knotens. Wenn der Baum leer ist, ist <code>pParent</code> < <code>&Parents[0]</code> (und <code>dir</code> irrelevant).
Andernfalls ist <code>Parents[0]</code> gleich dem Zeiger auf den Wurzelknoten, <code>pParent</code> ≥ <code>&Parents[0]</code>, und <code>dir</code> die Kindesrichtung des neuen Knotens.

Der Knoten <math>\mathsf{N}</math> wird zunächst rot gefärbt, damit die Schwarzhöhe des Baumes erhalten bleibt.<ref>[[#Pfaff a|Ben Pfaff]] bringt außer der Variante des Textes auch eine Variante mit einem ersten eingefügten Knoten schwarzer Farbe.</ref>

{{Anker|Rebalancierung}}Die darauf folgenden Aktionen überprüfen, ob die Rot-Schwarz-Balance im Baum eingehalten ist und stellen sie wenn erforderlich wieder her.
Diese Reparatur wird als »Rebalancierung« ({{enS|rebalancing}}) bezeichnet.

Der neue Knoten <math>\mathsf{N}</math> (wie {{enS|node}}) ist der gerade betrachtete Problemknoten. Sein [[Elterknoten|Elter]] ist <math>\mathsf{P}</math> (wie {{enS|parent}}). Der Großelter sei <math>\mathsf{G}</math> (wie {{enS|grandparent}}) und der Onkel (das Geschwister des Elters) <math>\mathsf{U}</math> (wie {{enS|uncle}}) genannt.

Der Kopf der Funktion <code>RBinsert1</code> zum Einfügen eines Knotens nach einer vorher erfolgten und nicht erfolgreichen Suchoperation könnte wie folgt aussehen:<ref group="Anm.">Die Kurzschreibweise mit dem Pfeil <code>-></code> ist erklärt im Artikel [[Verbund (Datentyp)#Beispiel in C|Verbund (Datentyp)]].</ref>
<syntaxhighlight lang="c" line start="100">
 void RBinsert1(
 RBtree* T,          // -> Rot-Schwarz-Baum
 struct RBnode*   Parents[], // Liste der -> Vorfahren
 struct RBnode** pParent,    // ->-> Nachbarknoten (wird zum Elterknoten von N)
 struct RBnode*   N, // -> einzufügender Knoten
 byte dir)           // (Kindes-)Richtung der Einfügung ∈ {LEFT, RIGHT}
 {
   struct RBnode* P; // -> Elterknoten von N
   struct RBnode* G; // -> Elterknoten von P
   struct RBnode* U; // -> Onkel von N
 
   assert(N != NIL); // N muss Zeiger zu einem echten Knoten sein.
   N->left  = NIL;   // Dieses Programm ist hierfür zuständig.
   N->right = NIL;
   N->color = RED;
   if (pParent >= &Parents[0]) { // N ist nicht die neue Wurzel
     P = *pParent;   // -> Nachbarknoten (wird zum Elterknoten von N)
     assert(P->child[dir] == NIL); // darf kein echter Knoten sein
     P->child[dir] = N; // neuer Knoten als dir-Kind von P
     goto Start_E;   // Sprung in die Schleife
   } // end_if
   // pParent < &Parents[0]
   T->root = N; // N ist die neue Wurzel des Baums T.
   return; // Einfügung fertiggestellt
 
   do { // Beginn der (do while)-Schleife:
     // pParent >= &Parents[0]
     // ===> Es gibt den Elter P von N.
     // (<=> Bedingung_E1 trifft NICHT zu.)
     N = G; // neuer Problemknoten (kann die Wurzel sein)
     P = *pParent; // -> Elterknoten von N
 Start_E:
</syntaxhighlight>

{{Anker|SchleifeE}}Rebalancierung nach dem Einfügen: Die Schleife zur Überprüfung und Reparatur des Baums steigt vom roten Blatt <math>\mathsf{N}</math> zur Wurzel auf. Ihre [[Schleifeninvariante|Invariante]] ist:
* Die Forderung '''!RR''' (»Nicht Rot-Rot«) gilt für alle Paare {{nowrap|(Knoten←Elter)}} im Baum mit höchstens einer Ausnahme – beim Paar {{nowrap|(<math>\mathsf{N}</math>←<math>\mathsf{P}</math>).}} Dies wird als »Rot-Verletzung« ({{enS|red violation}}) angesehen, welche <math>\mathsf{N}</math> als Problemknoten definiert.<br/>Gilt '''!RR''' auch dort, entweder weil der Elter <math>\mathsf{P}</math> nicht existiert (Fall E1) oder schwarz ist (Fall E2), dann ist der Baum in Rot-Schwarz-Form.
* Zu Beginn jedes Iterationsschritts ist der Problemknoten rot.
* Die Forderung '''S#=''' (»Schwarz-Zahl Gleich«) gilt für den ganzen Baum.

=== Einfügen: Zusammenschau der Fälle ===
Die Zusammenschau bringt die Diagramme in einer auf die Farbkonstellation zugespitzten Form.
{| class="wikitable float-right" style="text-align:center;"
|- class="hintergrundfarbe5" style="font-size:smaller;"
|colspan="4"| »Bedingung« ||rowspan="2"| '''''Fall'''''<br/>→||rowspan="2"| »Rota-<br/>tion« ||rowspan="2"|»Neuzu-<br/>weisung« ||colspan="4"| »Ergebnis« ||rowspan="2"|→<br/>''Test'' ||rowspan="2"| <math>\Delta s</math>
|- class="hintergrundfarbe5"
| <math>\mathsf{P}</math> || <math>\mathsf{G}</math> || <math>\mathsf{U}</math> ||style="width:.8em;"| ''x'' || <math>\mathsf{P}</math> || <math>\mathsf{G}</math> || <math>\mathsf{U}</math> ||style="width:.8em;"| ''x''
|-
| — || || || || [[#Test E1|'''E1''']] || || || — || || || || ✓ ||
|-
| [[Datei:BlackNode.svg|13px]] || || || || [[#Test E2|'''E2''']] || || || [[Datei:BlackNode.svg|13px]] || || || || ✓ ||
|-
| [[Datei:RedNode.svg]] || [[Datei:BlackNode.svg|13px]] || [[Datei:RedNode.svg]] || || [[#Test E3|'''E3''']] || || <math>\mathsf{N}</math>:=<math>\mathsf{G}</math> || ? || ? || ? || ? || E1 || 1
|-
| [[Datei:RedNode.svg]] || [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || i || [[#Test E4|'''E4''']] || <math>\mathsf{P}</math>↶<math>\mathsf{N}</math> || <math>\mathsf{N}</math>:=<math>\mathsf{P}</math> || [[Datei:RedNode.svg]] || [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || o || E5 || 0
|-
| [[Datei:RedNode.svg]] || [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || o || [[#Test E5|'''E5''']] || <math>\mathsf{P}</math>↷<math>\mathsf{G}</math> || || [[Datei:BlackNode.svg|13px]] || [[Datei:RedNode.svg]] || [[Datei:BlackNode.svg|13px]] || || ✓ ||
|-
| [[Datei:RedNode.svg]] || — || || || [[#Test E6|'''E6''']] || || || [[Datei:BlackNode.svg|13px]] || || || || ✓ ||
|-
|colspan="13" style="text-align:left;font-size:smaller;"| Einfügen: Zusammenschau der Fälle<ref>Diese Aufteilung findet sich u.&nbsp;a. bei [[#Pfaff a|Ben Pfaff]].</ref>
|}

Die möglichen Konstellationen lassen sich in sechs Fälle aufteilen, zu denen es Transformationen (enthaltend [[Binärbaum#Rotation in binären Bäumen|Rotation]] und/oder Umfärbung) gibt, die entweder auf der betrachteten Ebene oder über weitere Iterationsschritte auf höheren Ebenen zur Rebalancierung des Baumes führen.

In der nebenstehenden Tabelle wird ein Fall durch eine Zeile repräsentiert, die
* die »Bedingung«, das ist die Konstellation, die den Fall definiert und die dem Abschnitt »Bedingung« des zum Fall gehörigen Diagramms – falls vorhanden – entspricht,
* die ''Fall''nummer,
* die Konstellation nach Umfärbung und/oder Rotation und ggf. Zuweisung in der Spaltengruppe »Ergebnis«
enthält. Eine Konstellation besteht aus maximal 4 Gegebenheiten, und zwar aus den Farben der 3 Knoten <math>\mathsf{P}, \mathsf{G}</math> und <math>\mathsf{U}.</math>
Manche Fälle benötigen darüber hinaus eine vierte Angabe ''x'' zur Kindesrichtung von <math>\mathsf{N},</math> und zwar steht »o« (wie {{enS|outer}}) für eine Rechts-Rechts- oder Links-Links-Kindesrichtung von <math>\mathsf{N}</math> zu <math>\mathsf{P}</math> zu <math>\mathsf{G}</math> und »i« (wie {{enS|inner}}) für Rechts-Links oder Links-Rechts.
Eine Zelle ist leer gelassen, wenn es auf die Angabe nicht ankommt. So gilt bspw. der Beispielcode im [[#Test_E3|Fall E3]] für beide Kindesrichtungen von <math>\mathsf{N}</math> und das, obwohl das zugehörige Diagramm nur eine Kindesrichtung zeigt.

Die Konstellationen in der Gruppe »Bedingung« genügen der [[#SchleifeE|Schleifeninvariante]], und ihre [[Disjunktion#Nicht-ausschließende Disjunktion|logische Summe]] schöpft diese zu 100 % aus.

Die Transformation, deren Fallnummer in der Spalte {{nowrap|''Fall''→}} verlinkt ist, transformiert die Eingabe-Konstellation (als Teilbaum dargestellt im mit »Bedingung« beschrifteten Abschnitt des zum Fall gehörigen Diagramms) in die mit »Rotation« und/oder »Umfärbung« beschrifteten Abschnitte. Steht ein Häkchen »✓« in der Spalte {{nowrap|→''Test''}}, dann reflektiert die Gruppe »Ergebnis« diesen Stand, mit dem alle Rot-Schwarz-Forderungen erfüllt sind und mit dem die Einfügeoperation abgeschlossen ist.
Andernfalls steht dort die Fallnummer derjenigen Bedingung, auf die die transformierte und neu zugewiesene Konstellation zu testen ist, wobei die entsprechende Zuweisung, angegeben in der Spalte »Neuzuweisung« für den Problemknoten <math>\mathsf{N},</math> auch die Knoten <math>\mathsf{P}, \mathsf{G}, \mathsf{U}</math> sowie die Angabe ''x'' zur Kindesrichtung von <math>\mathsf{N}</math> neu zuordnet.
Die Spaltengruppe »Ergebnis« und der mit »Neuzuweisung« beschriftete Abschnitt des Diagramms zeigt die Konstellation nach der Zuweisung; Fragezeichen stehen in den Zellen, auf deren Angabe es in den nachfolgenden Tests ankommt.

In der Spalte {{nowrap|→''Test''}} kommt der Eintrag »E1« nur bei der Transformation_E3 vor. Er bedeutet einen neuen Iterationsschritt, der mit dem Test auf die {{nowrap|<code>while</code>-Bedingung_E1}} in der {{nowrap|<code>do while</code>-Schleife}} beginnt, und zwar zwei Baumebenen (eine Schwarzebene <math>\Delta s</math>) näher an der Wurzel. Danach sind auch die Schwarzhöhen aller relevanten Teilbäume ≥ 1.
Da die Anzahl der Baumebenen mit der Höhe <math>h</math> übereinstimmt, können maximal <math>\tfrac h2</math> Iterationen vorkommen. Nun ist der Aufwand für eine Iteration beschränkt (d.&nbsp;h. in <math>\mathcal{O}(1)</math>) und damit der für die gesamte Einfügeoperation in <math>\mathcal{O}(h) = \mathcal{O}(\log n)</math> (mit oder ohne Suchen). Die reine Rebalancierung ist gemäß Abschnitt [[#Durchschnittliche und amortisierte Laufzeit|Durchschnittliche und amortisierte Laufzeit]] ''im Mittel'' und amortisiert in <math>\mathcal{O}(1).</math>

Bei einem Eintrag in der Spalte »Rotation« ist eine Rotation an der Transformation beteiligt. Man entnimmt der Tabelle sofort, dass bei einer Einfügeoperation maximal zwei Rotationen vorkommen, und zwar bei Fall E5 nach Fall E4. Denn nach einer Rotation kommt kein neuer Iterationsschritt – die Rotationen befinden sich [[Endrekursion|endrekursiv]] am Ende der letzten ausgeführten Iteration.

Die Kindesrichtung von <math>\mathsf{N}</math> entscheidet insbesondere über die nachfolgenden Rotationsrichtungen.
Bei Fall E4 bestimmt sie aber auch die Auswahl des Falles:
Hat <math>\mathsf{P}</math> dieselbe Kindesrichtung wie <math>\mathsf{N},</math> dann ist die Angabe ''x'' (s.&nbsp;Zusammenschau) auf »o« für »außen«, sonst auf »i« für »innen« zu setzen.<ref name="gespiegelt">Eine andere Möglichkeit ist, den Schleifenrumpf der {{nowrap|<code>do while</code>-Schleife}} in zwei Versionen hinzuschreiben, in einer für die Kindesrichtung links und in einer für rechts (so bspw. [[#Pfaff a|Ben Pfaff]]).</ref>

Im folgenden Beispielcode zur Operation Einfügen hält die Variable <code>dir</code> die Kindesrichtung des Knotens <math>\mathsf{P} .</math> Die Diagramme zeigen <math>\mathsf{P}</math> immer als linkes Kind.

Jeder Fall wird unter seiner Fallnummer erläutert und einschließlich Test (auf die ihn charakterisierende »Bedingung«) und Transformation durch ein Stück {{nowrap|[[C (Programmiersprache)|C]]-Code}} genau beschrieben.<ref name="rekursiv">Für die Vorteile der iterativen Programmierung hinsichtlich Platz und Zeit gegenüber einer [[Rekursive Programmierung|rekursiven Programmierung]] s.&nbsp;a.&nbsp;[[Binärer Suchbaum#Iterative Programmierung]]. Darüber hinaus erzwingt erstere eine genauere Beachtung der Knoteneigenschaften.</ref>

=== Einfügen Fall E2 ===
{{Anker|Test E2}}
Der Elter <math>\mathsf{P}</math> des (roten) Problemknotens <math>\mathsf{N}</math> ist schwarz.
{{Absatz}}

Nach Eintritt dieser Bedingung gibt es kein Paar {{nowrap|(Knoten←Elter)}} (mehr), das die {{nowrap|Forderung '''!RR'''}} verletzt. Ferner ist nach Voraussetzung ([[#SchleifeE|Schleifeninvariante]]) die Anzahl der schwarzen Knoten auf allen Pfaden dieselbe.
Damit ist der Baum ohne weitere Aktion in Rot-Schwarz-Form.
<syntaxhighlight lang="c" line start="160">
     if (P->color == BLACK) // Bedingung_E2
       // Transformation_E2:
       return; // Einfügung fertiggestellt
 
     // In den verbleibenden Fällen ist der Elter P rot.
     if (pParent <= &Parents[0]) // Bedingung_E6
       goto Fall_E6; // Der Elter P ist die Wurzel.
</syntaxhighlight>

Im Folgenden ist der Elter <math>\mathsf{P}</math> nicht die Wurzel, so dass der Großelter <math>\mathsf{G}</math> existiert.
Da <math>\mathsf{P}</math> rot ist, muss <math>\mathsf{G}</math> schwarz sein (so bei den folgenden Fällen E3, E4 und E5).

=== Einfügen Fall E3 ===
{{Mehrere Bilder
|Kopfzeile=Einfügen Fall E3<br/>[[#ZE|<small>(→Zeichenerklärung)</small>]]
|Bild1=Red-black_tree_insert_case_B0t.svg
|Untertitel1=Iterationsstufe<br/><math>j\!=\!1</math><br/><small>Neuzuweisung</small><br/><math>j\!=\!2</math>
|Breite1=85
|Bild2=Red-black_tree_perpendic_579_switch.svg
|Breite2=9
|Bild3=Red-black_tree_insert_case_B1t.svg
|Breite3=97
|Untertitel3=<br/><math>j\!\ge\!2</math>; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <small>nach </small><br/><br/><math>j\!\ge\!3</math>
}}

{{Anker|Test E3}}
Sowohl der Onkel <math>\mathsf{U}</math> als auch der Elter <math>\mathsf{P}</math> des Problemknotens <math>\mathsf{N}</math> ist rot.

Die Umfärbung von <math>\mathsf{P}</math> und <math>\mathsf{U}</math> in schwarz und von <math>\mathsf{G}</math> in rot stellt die {{nowrap|Forderung '''!RR'''}} im Teilbaum mit Wurzel <math>\mathsf{G}</math> wieder her (und zwar bei ''beiden'' Kindesrichtungen von <math>\mathsf{N}</math>). Auf keinem Pfad ändert sich die Anzahl der schwarzen Knoten.
Durch diese Transformation_E3 wird die »Rot-Verletzung« um zwei Baum-Ebenen (eine Schwarz-Ebene) nach oben verschoben mit <math>\mathsf{G}</math> als neuem Problemknoten.<ref group="Anm." name="CAuswertung">Man beachte die in der [[C (Programmiersprache)|Programmiersprache C]] festgelegte Art der [[Logischer Operator#frühzeitigesAbbrechenAuswertung|Auswertung]] der
{|
|-
| ||style="width:10em"| &nbsp; Disjunktion: || &nbsp; &nbsp; &nbsp; <code>(X == NIL)</code>
|-
| || || <code>&#124;&#124; (X->color == BLACK)</code>
|-
|colspan="3"| bzw. der
|-
| || &nbsp; Konjunktion: || &nbsp; &nbsp; &nbsp; <code>(X != NIL)</code>
|-
| || || <code>&& (X->color == RED)</code>
|}
die im Fall <code>X == NIL</code> die zweite Bedingung <code>X->color == BLACK</code> resp. <code>X->color == RED</code> ''nicht'' auswertet, sondern sofort zum {{nowrap|<code>else</code>-Zweig}} verzweigt. Im Beispielcode sind die entsprechenden Zeilen <span style="background:#FFFFD0">gelb hinterlegt.</span><br/>
Zusätzliche Bemerkung:<br/>
Die Schwarzhöhe 0 kommt [[#Schwarzhöhe0|''nur in der ersten'' Iteration]] der Reparaturschleife vor. Bei den höheren Iterationsstufen <math>j\ge 2</math> ist die Schwarzhöhe aller besuchten Knoten <code>X</code> positiv, somit auch <code>X != NIL</code> – und dieser Teil der Abfrage kann weggelassen werden.<br/>Weiß man andererseits, dass die Schwarzhöhe eines Knotens 0 ist, dann weiß man auch, dass er, wenn er existiert, nur rot sein kann.<br/>
Damit lässt sich also die genannte Konjunktion/Disjunktion nach [[Loop unrolling|Herausziehen]] der ersten Iteration auf folgende Weise vereinfachen:
{|
|-
| ||style="width:10em"| &nbsp; erste Iteration: || <code>if (X != NIL)</code> || (welches <code>X->color == RED</code> dort immer impliziert)
|-
| ||style="width:10em"| &nbsp; höhere Iteration: || <code>if (X->color == RED)</code> &nbsp; &nbsp; &nbsp; || (da dort immer <code>X != NIL</code>)
|}</ref>
<syntaxhighlight lang="c" highlight="4" line start="180">
     G = *(--pParent);      // Der Großelter G von N existiert.
     dir = (P == G->right); // Kindesrichtung von P
     U = G->child[1−dir];   // Onkel
     if (U == NIL  ||  U->color == BLACK)
       goto Test_E4;        // Der Onkel U ist schwarz.
     // Bedingung_E3: N+P+U rot
     // Transformation_E3:
     // Umfärbung:
     P->color = BLACK;
     U->color = BLACK;
     G->color = RED;
 
     // Iteration zwei Ebenen (1 Schwarzebene) höher
   } while (--pParent >= &Parents[0]);
   // Ende der (do while)-Schleife
</syntaxhighlight>

=== Einfügen Fall E1 ===
{{Anker|Test E1}}
Der Problemknoten (hier: <math>\mathsf{G}</math>) ist die Wurzel.
Nach der obigen Transformation_E3 ist {{nowrap|'''!RR'''}} (»Nicht Rot-Rot«) überall erfüllt, und der Baum in Rot-Schwarz-Form.

Allerdings könnte man eine rote Wurzel ohne Verletzung der Rot-Schwarz-Forderungen immer auf schwarz umfärben<ref name="Schwarzwurzel" /> – was z.&nbsp;B. den Test auf Bedingung_E6 und den [[#Test E6|Fall E6]] überflüssig machen würde.

<syntaxhighlight lang="c" line start="210">
   // Bedingung_E1: pParent < &Parents[0]
   //               ===> G ist die alte und neue Wurzel des Baums T.
   return; // Einfügung fertiggestellt
</syntaxhighlight>

=== Einfügen Fall E4 ===
{{Mehrere Bilder
|Kopfzeile = Einfügen Fall E4<br/>[[#ZE|<small>(→Zeichenerklärung)</small>]]
|align=right
|Bild1=Red-black_tree_insert_case_C0.svg
|Untertitel1=Iterationsstufe<br/><math>j\!=\!1</math>
|Breite1=64
|Bild2=Red-black_tree_perpendic_639era_switch.svg
|Breite2=9
|Bild3=Red-black_tree_insert_case_C1.svg
|Breite3=97
|Untertitel3=<br/><math>j\!\ge\!2</math>
}}

{{Anker|Test E4}}
Der Problemknoten <math>\mathsf{N}</math> hat keinen oder einen schwarzen Onkel und hat eine Kindesrichtung entgegengesetzt zu der seines roten Elters <math>\mathsf{P} ,</math> d.&nbsp;h., <math>\mathsf{N}</math> ist innerer Enkel.

Eine Rotation um <math>\mathsf{P}</math><ref group="Anm." name="PivotsInneresKind3">In der ersten Iterationsstufe <math>j\!=\!1</math> ist der Teilbaum <math>\mathsf{3}</math> leer. Wenn die Knoten mit Elterzeiger implementiert werden, dann ist nach der Rotation der Elterzeiger dieses Teilbaums bei allen Iterationsstufen außer der ersten anzupassen.</ref> vertauscht die Rollen von <math>\mathsf{N}</math> und <math>\mathsf{P},</math> und zwar eine Linksrotation, wenn <math>\mathsf{P}</math> linkes Kind (d.&nbsp;h. {{nowrap|1=<code>dir == LEFT</code>)}} ist, sonst eine Rechtsrotation.
(Im Folgenden wird eine solche Rotation als {{nowrap|<code>dir</code>-Rotation}} bezeichnet.)
Dadurch werden die Pfade des Teilbaums <math>\mathsf{2}</math> so verändert, dass sie durch einen Knoten mehr und die des Teilbaums <math>\mathsf{4}</math> durch einen weniger führen. Da jedoch in beiden Fällen rote Knoten den Unterschied ausmachen, ändert sich an der Anzahl der schwarzen Knoten nichts, womit die {{nowrap|1=Forderung '''S#='''}} und die [[#SchleifeE|Schleifeninvariante]] erfüllt bleibt.

Die Ergebniskonstellation entspricht der Eingangskonstellation des Falles E5 mit <math>\mathsf{P}</math> als dem neuen Problemknoten.

<syntaxhighlight lang="c" line start="230">
 Test_E4:
   if (N != P->child[dir]) {
     // Bedingung_E4: N ist innerer Enkel
     //               && N+P rot && U schwarz
     // Transformation_E4:
     // dir-Rotation um P:
     P->child[1−dir] = N->child[dir]; // NIL oder neuer Zeiger zu Teilbaum 3
     N->child[dir] = P;
     G->child[dir] = N;
     // Zuweisung nach der Transformation:
     N = P; // neuer Problemknoten (rot) und äußerer Enkel
     P = G->child[dir]; // neuer Elter von N (rot)
   }
</syntaxhighlight>

=== Einfügen Fall E5 ===
{{Mehrere Bilder
|align=right
|Kopfzeile = Einfügen Fall E5<br/>[[#ZE|<small>(→Zeichenerklärung)</small>]]
|Bild1=Red-black_tree_insert_case_D0rot.svg
|Untertitel1=Iterationsstufe<br/><math>j\!=\!1</math>
|Breite1=64
|Bild2=Red-black_tree_perpendic_639erc_switch.svg
|Breite2=9
|Bild3=Red-black_tree_insert_case_D1rot.svg
|Breite3=97
|Untertitel3=<br/><math>j\!\ge\!2</math>
}}

{{Anker|Test E5}}
Der Problemknoten <math>\mathsf{N}</math> hat keinen oder einen schwarzen Onkel.
Seine Kindesrichtung ist dieselbe wie die von <math>\mathsf{P} ,</math> d.&nbsp;h., <math>\mathsf{N}</math> ist äußerer Enkel.

Eine (nicht-<code>dir</code>)-Rotation<ref group="Anm." name="eckig" /> um <math>\mathsf{G}</math><ref group="Anm." name="PivotsInneresKind3" /> macht <math>\mathsf{P}</math> zum Elter sowohl von <math>\mathsf{N}</math> als auch von <math>\mathsf{G}.</math> Da <math>\mathsf{P}</math> rot war, muss wegen {{nowrap|Forderung '''!RR'''}} <math>\mathsf{G}</math> schwarz sein. Invertiert man nun die Farben von <math>\mathsf{G}</math> und <math>\mathsf{P},</math> so ist in dem dadurch entstehenden Baum die {{nowrap|Forderung '''!RR'''}} wieder erfüllt. Die {{nowrap|1=Forderung '''S#='''}} bleibt ebenfalls erfüllt, da alle Pfade, die durch einen dieser drei Knoten laufen, vorher durch <math>\mathsf{G}</math> liefen und nun alle durch <math>\mathsf{P}</math> laufen, der inzwischen – wie <math>\mathsf{G}</math> vor der Transformation – der einzige schwarze der drei Knoten ist.
<syntaxhighlight lang="c" line start="270">
   // Bedingung_E5: N ist äußerer Enkel && N+P rot && U schwarz
   // Transformation_E5:
   // (nicht-dir)-Rotation um G:
   G->child[dir] = P->child[1−dir]; // NIL oder neuer Zeiger zu Teilbaum 3
   P->child[1−dir] = G;
   if (--pParent >= &Parents[0]) {
     // Ersetze G bei seinem Elter durch P:
     U = *pParent;
     U->child[G == U->right] = P;
   }
   else // G war die Wurzel
     T->root = P; // P ist die neue Wurzel
   // Umfärbung:
   P->color = BLACK;
   G->color = RED;
   return; // Einfügung fertiggestellt
</syntaxhighlight>

=== Einfügen Fall E6 ===
{{Anker|Test E6}}
Der rote Elter <math>\mathsf{P}</math> des Problemknotens <math>\mathsf{N}</math> ist gleichzeitig die Wurzel des Baums.
{{Absatz}}

Eine Umfärbung von <math>\mathsf{P}</math> in schwarz stellt die {{nowrap|Forderung '''!RR'''}} im ganzen Baum wieder her. Auf jedem Pfad erhöht sich die Anzahl der schwarzen Knoten um 1.
<syntaxhighlight lang="c" line start="310">
 Fall_E6:
   // Der Elter P von N ist die Wurzel des Baums.
   // Transformation_E6:
   // Umfärbung:
   P->color = BLACK;
   // Da P rot war,
   // erhöht sich die Schwarzhöhe des Baumes um 1.
   return; // Einfügung fertiggestellt
 } // Ende RBinsert1
</syntaxhighlight>

== Operation Löschen ==
Das Löschen eines Knotens, sein Name sei <math>\mathsf{N}</math>, aus einem Rot-Schwarz-Baum erfolgt wie bei einem [[Binärer Suchbaum#Löschen|binären Suchbaum]].

Hat der Knoten <math>\mathsf{N}</math> ein oder kein Kind, dann kann die folgende Überlegung übersprungen werden.
:Hat <math>\mathsf{N}</math> aber zwei (echte) Kinder, dann nimmt man, ohne letztlich die Sortierreihenfolge zu stören, als effektiv zu löschenden Knoten seinen hinsichtlich Sortierreihenfolge rechten (resp. linken) [[Binärbaum#in-order-Traversierung|Nachbarknoten]], welcher kein linkes (resp. kein rechtes) Kind haben  kann.<ref>Diese Vorgehensweise wurde zum ersten Mal von T. Hibbard in 1962 vorgeschlagen, zitiert nach [[Robert Sedgewick (Informatiker)|Robert Sedgewick]], Kevin Wayne: [https://github.com/haseebr/competitive-programming/blob/master/Materials/Algorithhms%204th%20Edition%20by%20Robert%20Sedgewick%2C%20Kevin%20Wayne.pdf ''Algorithms Fourth Edition.''] Pearson Education, 2011, ISBN 978-0-321-57351-3, S.&nbsp;410 (englisch, abgerufen am 25. März 2018)</ref> Ein solcher Nachbarknoten ist ein Blatt oder Halbblatt, das [[Binärer Suchbaum#Loe2Kinder|tiefster linker Nachkomme]] des rechten Kindes (resp. tiefster rechter Nachkomme des linken Kindes) von <math>\mathsf{N}</math> ist.<ref group="Anm.">Im Fall, dass die RB-Software die Benutzerdaten nicht kennt und trotzdem generisch sein muss, sind an Stelle der Benutzerdaten die RB-Daten zu vertauschen, so dass der (wirklich zu löschende) Knoten (mit dem Schlüssel und den Benutzerdaten von <math>\mathsf{N}</math>) maximal ein RB-Kind hat. Bei dieser Vorgehensweise bleiben auch bspw. Zeiger auf gültige Knoten gültig.</ref>
{{Anker|Löschen0}}Geht man so vor, dann kann man sich darauf beschränken, dass das initiale <math>\mathsf{N}</math> ''maximal ein'' Kind hat.
Mit <math>\mathsf{P}</math> (wie {{enS|parent}}) sei der Elter von <math>\mathsf{N}</math> und mit <code>dir</code> (wie {{enS|direction}}) die Kindesrichtung von <math>\mathsf{N}</math> (rechtes oder linkes Kind von {{nowrap|<math>\mathsf{P}</math>)}} bezeichnet.

=== Einfache Fälle ===
Den Fall, dass <math>\mathsf{N}</math> die kinderlose Wurzel ist, erledigt man sofort, indem man diese durch einen [[#NIL-Knoten|NIL-Knoten]] ersetzt.

Hat <math>\mathsf{N}</math> genau ein Kind, so ist dieses zwangsläufig [[#HalbblattBlatt|rot]].
Man färbt es schwarz und macht es an der Kindesrichtung <code>dir</code> zum Kind von <math>\mathsf{P}.</math> Damit ist <math>\mathsf{N}</math> aus dem Baum entfernt, und die {{nowrap|Forderung '''!RR'''}} (»Nicht Rot-Rot«) bleibt erfüllt. Ferner verlaufen nun alle Pfade, die durch den gelöschten schwarzen Knoten verliefen, durch sein nunmehr schwarzes Kind, so dass auch die {{nowrap|1=Forderung '''S#='''}} (»Schwarz-Zahl Gleich«) erfüllt bleibt.

Hat <math>\mathsf{N}</math> kein Kind und ist rot, so wird es bei seinem (schwarzen) Elter einfach durch einen NIL-Knoten ersetzt.
Und da alle Pfade, die durch den roten Knoten verliefen, nach seiner Entfernung aus dem Baum durch einen roten Knoten weniger verlaufen, ändert sich an der Anzahl der schwarzen Knoten nichts, womit die {{nowrap|1=Forderung '''S#='''}} erfüllt bleibt.

=== Das Löschen eines schwarzen Blattes ===
Komplizierter sind die Fälle, wo <math>\mathsf{N}</math> nicht die Wurzel ist, kein Kind hat und schwarz, also ein schwarzes Blatt ist.

Als solches hat <math>\mathsf{N}</math> ein (echtes) Geschwister, das {{nowrap|(nicht-<code>dir</code>)-Kind}}<ref group="Anm." name="eckig">Wegen der [[#logGleich|Gleichsetzungen]] <code>LEFT &equiv; 0</code> und <code>RIGHT &equiv; 1</code> spiegelt die [[Negation#Die Negation in der zweiwertigen Logik|logische Negation]]
:nicht-<code>dir &nbsp; &equiv; &nbsp; !dir &nbsp; &equiv; &nbsp; 1−dir</code>
die Richtung <code>LEFT</code> <math>\longleftrightarrow</math> <code>RIGHT</code>. Dabei ist <code>dir = (N == P->right)</code> die Kindesrichtung von <math>\mathsf{N}</math>.<br/>
Im Kontext der Farben spricht man bei Zuweisungen à la <code>RED :&equiv; !BLACK</code> und <code>BLACK :&equiv; !RED</code> von »Invertierung«.</ref> von <math>\mathsf{P},</math> welches mit <math>\mathsf{S}</math> (wie {{enS|sibling}}) bezeichnet sei.
Dessen (möglicherweise leeres) {{nowrap|<code>dir</code>-Kind}} <math>\mathsf{C}</math> (wie {{enS|close}}) ist der »nahe« Neffe von <math>\mathsf{N}</math> mit derselben Kindesrichtung; das andere (ebenfalls möglicherweise leere) Kind <math>\mathsf{D}</math> (wie {{enS|distant}}) der »ferne« Neffe.

Nach der Ersetzung von <math>\mathsf{N}</math> bei <math>\mathsf{P}</math> durch NIL sei diese Stelle im Baum weiterhin durch <math>\mathsf{N}</math> bezeichnet. Die durch <math>\mathsf{N}</math> führenden Pfade enthalten einen schwarzen Knoten weniger als vorher, also einen weniger als die ebenfalls durch <math>\mathsf{P}</math> führenden Pfade durch das Geschwister <math>\mathsf{S}</math>. Somit ergibt sich bei <math>\mathsf{P}</math> eine Verletzung der {{nowrap|1=Forderung '''S#=''',}} eine so genannte »Schwarz-Verletzung« ({{enS|black violation}}). Der Knoten <math>\mathsf{N}</math> wird deshalb als Problemknoten aufgefasst.

Im nachfolgenden Beispielcode ist angenommen, dass eine vorausgehende Suchfunktion, die den zu löschenden Knoten <math>\mathsf{N}</math> lokalisiert hat, den [[Stapelspeicher|Stapel]] {{nowrap|<code>struct RBnode* Parents[]</code>}} von dessen Vorfahren gebildet<ref name="Stapel" /> und dessen Zeiger an die Löschfunktion übergeben hat.
Ist <math>\mathsf{N}</math> die Wurzel, dann zeigt der ebenfalls übergebene Zeiger <code>struct RBnode** pParent</code> vor diesen Stapel (<code>pParent</code> < <code>&Parents[0]</code>).
Andernfalls zeigt er in diesem Stapel auf den Zeiger zum direkten Elter des zu löschenden Knotens, und es ist <code>pParent</code> ≥ <code>&Parents[0]</code> sowie <code>Parents[0]</code> gleich dem Zeiger auf den Wurzelknoten.

Eine andere, häufig verwendete Art, den Aufstieg im Baum zu unterstützen, ist die Implementierung eines Elterzeigers pro Knoten.

Der Kopf einer Funktion <code>RBdelete2</code> zum Löschen eines schwarzen Knotens <math>\mathsf{N}</math> ohne Kind, der nicht die Wurzel ist, könnte dann wie folgt aussehen:<ref group="Anm.">Um der Kürze der Aufschreibung willen wird im Beispielcode einige Male <code>goto</code> verwendet. Es ist leicht, dies durch Verdoppelung des Codes zu vermeiden.</ref>

<syntaxhighlight lang="c" line start="500">
 void RBdelete2(
 RBtree* T,                  // -> Rot-Schwarz-Baum
 struct RBnode*   Parents[], // Liste der -> Vorfahren
 struct RBnode** pParent,    // ->-> Elterknoten von N
 struct RBnode*   N)         // -> zu löschender Knoten, hier: schwarz
 {
   byte dir;         // Richtung ∈ {LEFT, RIGHT}
   struct RBnode* P; // -> Elterknoten von N
   struct RBnode* S; // -> Geschwisterknoten von N
   struct RBnode* C; // -> naher  Neffe
   struct RBnode* D; // -> ferner Neffe
 
   // Für RBdelete2 muss erfüllt sein:
   assert(N != NIL);
   assert(pParent >= Parents[0]); // N ist nicht die Wurzel.
   P = *pParent; // Elter von N
   dir = (N == P->right); // Kindesrichtung von N:
   // Wenn nicht right, dann left:
   assert(N != P->right ? N == P->left : true);
   assert(N->color == BLACK);
   assert(N->left  == NIL);
   assert(N->right == NIL);
   // Ersetze N bei seinem Elter P durch NIL:
   P->child[dir] = NIL;
   goto Start_L; // Sprung in die Schleife
</syntaxhighlight>

{{Anker|SchleifeL}}Rebalancierung nach dem Löschen: Die Schleife zur Überprüfung und Reparatur des Baums steigt vom Problemknoten <math>\mathsf{N},</math> d.&nbsp;i. zunächst das neue Pfadende <code>N = NIL</code>, zur Wurzel auf. Ihre [[Schleifeninvariante|Invariante]] ist:
* Die Anzahl der schwarzen Knoten in den Pfaden durch <math>\mathsf{N}</math> ist um eins kleiner als vorher, wogegen sie in den anderen Pfaden ungeändert ist. (Dies kann durch Abzählen der schwarzen Kreisflächen in der mit »Bedingung« beschrifteten Ausgangskonstellation eines Diagramms nachvollzogen werden.) Das bedeutet, dass, wenn es andere Pfade gibt, beim Elter von <math>\mathsf{N}</math> eine »Schwarz-Verletzung« vorliegt.
* <math>\mathsf{N}</math> hat die Schwarzhöhe <math>j\!-\!\!1</math> und ist in der ersten Iterationsstufe leer (sein Zeigerwert NIL). Dieses Pfadende wird in den Diagrammen der ersten Iterationsstufe durch einen blauen Pfeil nach links [[Datei:nilBlue.svg|grundlinie]] symbolisiert.<br/>In den höheren Iterationsstufen ist <math>\mathsf{N}</math> ein echter schwarzer Knoten und wird in den Diagrammen mit der blauen Kontur des Problemknotens gebracht.<ref group="Anm.">Zu Beginn jedes Iterationsschritts hat das Geschwister <math>\mathsf{S}</math> die Schwarzhöhe {{nowrap|<math>j</math>.}}</ref>
* Die Forderung '''!RR''' (»Nicht Rot-Rot«) ist überall erfüllt.

Die Zusammenschau bringt die Diagramme in einer auf die Farbkonstellation zugespitzten Form.
{| class="wikitable float-right" style="text-align:center;"
|- class="hintergrundfarbe5" style="font-size:smaller;"
|colspan="4"| »Bedingung« ||rowspan="2"|'''''Fall'''''<br/>→||rowspan="2"| »Rota-<br/>tion« ||rowspan="2"|»Neuzu-<br/>weisung« ||colspan="4"| »Ergebnis« ||rowspan="2"|→<br/>''Test'' ||rowspan="2"| <math>\Delta s</math>
|- class="hintergrundfarbe5"
| <math>\mathsf{P}</math> || <math>\mathsf{C}</math> || <math>\mathsf{S}</math> || <math>\mathsf{D}</math> || <math>\mathsf{P}</math> || <math>\mathsf{C}</math> || <math>\mathsf{S}</math> || <math>\mathsf{D}</math>
|-
| — || || || || [[#Test L1|'''L1''']] || || ||style="text-align:left"| — || || || || ✓ ||
|-
| [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || [[#Test L2|'''L2''']] || || <math>\mathsf{N}</math>:=<math>\mathsf{P}</math> || ? || ? || ? || ? || L1 || 1
|-
|rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[File:RedNode.svg]] ||rowspan="3"| [[File:BlackNode.svg|13px]] ||rowspan="3"| [[#Test L3|'''L3''']] ||rowspan="3"| <math>\mathsf{P}</math>↶<math>\mathsf{S}</math> ||rowspan="3"| <math>\mathsf{N}</math>:=<math>\mathsf{N}</math> || [[File:RedNode.svg]] || || [[File:BlackNode.svg|13px]] || [[File:RedNode.svg]] || L6 || 0
|-
|  [[File:RedNode.svg]] || [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || L5 || 0
|-
| [[File:RedNode.svg]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || [[File:BlackNode.svg|13px]] || L4 || 0
|-
| [[Datei:RedNode.svg]] || [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || [[#Test L4|'''L4''']] || || || [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || [[Datei:RedNode.svg]] || [[Datei:BlackNode.svg|13px]] || ✓ ||
|-
| [[Datei:RedOrBlackNode.svg]] || [[Datei:RedNode.svg]] || [[Datei:BlackNode.svg|13px]] || [[Datei:BlackNode.svg|13px]] || [[#Test L5|'''L5''']] || <math>\mathsf{C}</math>↷<math>\mathsf{S}</math> || <math>\mathsf{N}</math>:=<math>\mathsf{N}</math> || [[Datei:RedOrBlackNode.svg]] || || [[Datei:BlackNode.svg|13px]] || [[Datei:RedNode.svg]] || L6 || 0
|-
| [[Datei:RedOrBlackNode.svg]] || || [[Datei:BlackNode.svg|13px]] || [[Datei:RedNode.svg]] || [[#Test L6|'''L6''']] || <math>\mathsf{P}</math>↶<math>\mathsf{S}</math> || || [[Datei:BlackNode.svg|13px]] || || [[Datei:RedOrBlackNode.svg]] || [[Datei:BlackNode.svg|13px]] || ✓ ||
|-
|colspan="13" style="text-align:left; font-size:smaller;"| Löschen: Zusammenschau der Fälle<ref>Die Aufteilung entspricht [[#sdsu|Roger Whitney]].</ref><ref>Auf eine andere Aufteilung (der Bedingungen) der Fälle, aber im Ergebnis ebenfalls auf die Gesamtzahl 6, kommt [http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/276_a.gif University of Science and Technology of China] (zitiert nach [https://stackoverflow.com/questions/23700857/deletion-in-red-black-tree stackoverflow.com]).</ref>
|}

=== Löschen: Zusammenschau der Fälle ===
Die möglichen Farbkonstellationen lassen sich in sechs Fälle gruppieren, zu denen es Transformationen (enthaltend Rotation und/oder Umfärbung) gibt, die entweder auf der betrachteten Ebene oder über weitere Iterationsschritte auf höheren Ebenen zu einer Rebalancierung des Baumes führen.

In der nebenstehenden Tabelle wird ein Fall durch eine Zeile repräsentiert, die
* die »Bedingung«, das ist die Konstellation, die den Fall definiert,
* die ''Fall''nummer,
* die Konstellation nach Transformation und ggf. Zuweisung in der Spaltengruppe »Ergebnis«
enthält. Eine Konstellation (4 Spalten) besteht aus den Farben der 4 Knoten <math>\mathsf{P}, \mathsf{C}, \mathsf{S}, \mathsf{D}.</math>
Eine Zelle ist leer gelassen, wenn es auf die Angabe nicht ankommt. Zweimal [[Datei:RedOrBlackNode.svg|grundlinie]] auf einer Zeile bedeutet zweimal dieselbe Knotenfarbe, schwarz oder rot.

Die Konstellationen in der Gruppe »Bedingung« genügen der [[#SchleifeL|Schleifeninvariante]], und ihre [[Disjunktion#Nicht-ausschließende Disjunktion|logische Summe]] schöpft diese zu 100 % aus.
Sie sind im mit »Bedingung« beschrifteten, dem obersten Abschnitt des zum Fall gehörenden Diagramms nochmals als Teilbaum skizziert.

Die Transformation, deren Fallnummer in der Spalte {{nowrap|''Fall''→}} verlinkt ist, transformiert die Eingabe in Konstellationen, die in den mit »Rotation« und/oder »Umfärbung« beschrifteten Abschnitten des Diagramms des Falles dargestellt sind.
Steht ein Häkchen »✓« in der Spalte {{nowrap|→''Test''}}, dann reflektiert die Gruppe »Ergebnis« den Endstand, und die Löschoperation ist durch die Transformation abgeschlossen.
Andernfalls steht dort die Fallnummer derjenigen Bedingung, auf die die transformierte und neu zugewiesene Konstellation zu testen ist, wobei die entsprechende Zuweisung, angegeben in der Spalte »Neuzuweisung« für den Problemknoten <math>\mathsf{N},</math> auch die Knoten <math>\mathsf{P}, \mathsf{C}, \mathsf{S}, \mathsf{D}</math> eindeutig bestimmt.
Die Spaltengruppe »Ergebnis« und der mit »Neuzuweisung« beschriftete Abschnitt des Diagramms zeigt die Konstellation nach der Zuweisung; Fragezeichen stehen bei den Knoten, auf deren Farbe es in den nachfolgenden Tests ankommt.

Der Eintrag »L1« kommt nur bei der Transformation_L2 vor und bedeutet einen neuen Iterationsschritt auf der um 1 höheren Ebene im Baum (gleichzeitig eine Schwarzebene <math>\Delta s</math>), beginnend mit dem Test auf die Bedingung_L1. Danach sind die Schwarzhöhen aller Teilbäume ≥ 1.
Die Anzahl der Ebenen stimmt mit der Höhe <math>h</math> überein, so dass höchstens <math>h</math> Iterationen vorkommen können. Nun ist der Aufwand für eine Iteration beschränkt (d.&nbsp;h. in <math>\mathcal{O}(1)</math>) und damit der für die gesamte Löschoperation in <math>\mathcal{O}(h) = \mathcal{O}(\log n).</math> Gemäß Abschnitt [[#Durchschnittliche und amortisierte Laufzeit|Durchschnittliche und amortisierte Laufzeit]] ist der Rebalancierungsaufwand ''im Mittel'' sogar konstant.

Bei einem Eintrag in der Spalte ''Rotation'' ist eine [[Binärbaum#Rotation in binären Bäumen|Rotation]] an der Transformation beteiligt. Und die Tabelle zeigt, dass bei einer Löschung maximal drei Rotationen (von Fall L3 über L5 zu L6) erforderlich sind. Denn nach einer Rotation kommt kein neuer Iterationsschritt – die Rotationen befinden sich [[Endrekursion|endrekursiv]] am Ende der letzten Iteration.

Die Kindesrichtung des Problemknotens <math>\mathsf{N}</math> bestimmt sowohl die nachfolgenden Rotationsrichtungen wie die Kindesrichtungen der Neffen <math>\mathsf{C}</math> und <math>\mathsf{D} .</math> Im Beispielcode wird dies mithilfe der Variablen <code>dir</code> {{nowrap|gelöst.<ref name="gespiegelt" />}}
Die Diagramme bei den Fällen zeigen jedoch <math>\mathsf{N}</math> immer links von <math>\mathsf{P}</math>.

<syntaxhighlight lang="c" highlight="14,17" line start="550">
   // Beginn der (do while)-Schleife:
   do {
     // pParent >= &Parents[0]
     // ===> Bedingung_L1 trifft NICHT zu
     N = P; // neuer Problemknoten (kann die Wurzel sein)
     P = *pParent;
     dir = (N == P->right); // Kindesrichtung von N
 Start_L:
     S = P->child[1−dir]; // Geschwister von N
     if (S->color == RED)
       goto Fall_L3; // Bedingung_L3: S rot ===> P+C+D schwarz
     // S ist schwarz:
     D = S->child[1−dir]; // ferner Neffe
     if (D != NIL  &&  D->color == RED)
       goto Fall_L6;      // der ferne Neffe D ist rot
     C = S->child[ dir];  // naher  Neffe
     if (C != NIL  &&  C->color == RED)
       goto Fall_L5;      // der nahe  Neffe C ist rot
     // Beide Neffen sind == NIL (erste Iteration) oder schwarz (später).
     if (P->color == RED)
       goto Fall_L4; // P rot && C+S+D schwarz <==> Bedingung_L4
</syntaxhighlight>

Jeder Fall wird unter seiner Fallnummer erläutert und einschließlich Test (auf die ihn charakterisierende Bedingung) und Transformation durch ein Stück C-Code genau beschrieben.<ref name="rekursiv" /><ref group="Anm." name="CAuswertung" />

=== Löschen Fall L2 ===
{{Mehrere Bilder
|Kopfzeile = Löschen Fall L2<br/>[[#ZE|<small>(→Zeichenerklärung)</small>]]
|Bild1=Red-black_tree_delete_case_B0t.svg
|Untertitel1=Iterationsstufe<br/><math>j\!=\!1</math><br/><small>Neuzuweisung</small><br/><math>j\!=\!2</math>
|Breite1=71
|Bild2=Red-black_tree_perpendic_579_switch.svg
|Breite2=9
|Bild3=Red-black_tree_delete_case_B1t.svg
|Breite3=117
|Untertitel3=<br/><math>j\!\ge\!2</math>; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; <small>nach </small><br/><br/><math>j\!\ge\!3</math>
}}
{{Anker|Test L2}}
Der Elter <math>\mathsf{P}</math> des Problemknotens <math>\mathsf{N}</math> und das Geschwister <math>\mathsf{S}</math> sind schwarz, ebenso die Kinder <math>\mathsf{C}</math> und <math>\mathsf{D}</math> von <math>\mathsf{S},</math> falls sie existieren.

Die Umfärbung des Knotens <math>\mathsf{S}</math> von schwarz in rot vermindert in allen Pfaden, die durch <math>\mathsf{S}</math> führen, die Zahl <math>s</math> der schwarzen Knoten um 1 auf {{nowrap|<math>s\!\!-\!\!1</math>.}}
Das betrifft genau die Pfade, die durch <math>\mathsf{P},</math> aber nicht durch <math>\mathsf{N}</math> führen, welch letztere Pfade vorher schon genau <math>s\!\!-\!\!1</math> schwarze Knoten enthalten haben.
Damit sind es <math>s\!\!-\!\!1</math> schwarze Knoten in den Pfaden, die durch <math>\mathsf{P}</math> führen, und <math>s</math> in denen, die nicht durch <math>\mathsf{P}</math> führen – wenn es denn solche noch gibt.
Somit wird die erste Bedingung der [[#SchleifeL|Schleifeninvariante]] mit nunmehr <math>\mathsf{P}</math> als Problemknoten erfüllt.

<syntaxhighlight lang="c" line start="590">
     // Bedingung_L2: P+C+S+D schwarz
     // Transformation_L2:
     // Umfärbung:
     S->color = RED;
     // Fortsetzung der Überprüfung des Baums
     //   eine Ebene höher durch Testen auf die
     // Bedingung_L1:
   } while (--pParent >= &Parents[0]);
   // Ende der (do while)-Schleife.
</syntaxhighlight>

=== Löschen Fall L1 ===
{{Anker|Test L1}}
Der Problemknoten (hier: <math>\mathsf{P}</math>) ist die Wurzel.

In diesem Fall ist man fertig, da überhaupt alle Pfade durch <math>\mathsf{P}</math> führen (und somit alle Pfade einen schwarzen Knoten weniger enthalten als vorher).
Die Schwarzhöhe des Baumes verringert sich dabei um 1.
<syntaxhighlight lang="c" line start="620">
   // Bedingung_L1: pParent < &Parents[0]
   //               ===> P ist die alte und neue Wurzel des Baums T.
   return; // Löschung fertiggestellt
</syntaxhighlight>

=== Löschen Fall L3 ===
{{Mehrere Bilder
|align=right
|Kopfzeile = Löschen Fall L3<br/>[[#ZE|<small>(→Zeichenerklärung)</small>]]
|Bild1=Red-black_tree_delete_case_A0rot3.svg
|Untertitel1=Iterationsstufe<br/><math>j\!=\!1</math>
|Breite1=91
|Bild2=Red-black_tree_perpendic_865_switch.svg
|Breite2=9
|Bild3=Red-black_tree_delete_case_A1rot3.svg
|Breite3=117
|Untertitel3=<br/><math>j\!\ge\!2</math>
}}

{{Anker|Test L3}}
Das Geschwister <math>\mathsf{S}</math> des Problemknotens <math>\mathsf{N}</math> ist rot.

Eine Rotation um <math>\mathsf{P}</math><ref group="Anm.">Wenn die Knoten mit Elterzeiger implementiert werden, dann ist der Elterzeiger des Knotens <math>\mathsf{C}</math> in allen Iterationen anzupassen, da die Schwarzhöhe von <math>\mathsf{C}</math> auch in der ersten Iteration ≥ 1 ist.</ref> macht <math>\mathsf{S}</math> zum Großelter von <math>\mathsf{N},</math> und zwar eine Linksrotation, wenn <math>\mathsf{N}</math> linkes Kind (d.&nbsp;h. {{nowrap|<code>dir &#61;&#61; LEFT</code>)}} ist, sonst eine Rechtsrotation.
(Im Folgenden wird eine solche Rotation als {{nowrap|<code>dir</code>-Rotation}} bezeichnet.)
Danach invertiert man die Farben von <math>\mathsf{P}</math> und <math>\mathsf{S}.</math> Alle Pfade haben weiterhin dieselbe Anzahl an schwarzen Knoten, aber <math>\mathsf{N}</math> hat nun ein schwarzes Geschwister, <math>\mathsf{C},</math> und einen roten Elter, <math>\mathsf{P},</math> weswegen man nun zu Fall L4, L5 oder L6 weitergehen kann – mit <math>\mathsf{N}</math> als altem und neuem {{nowrap|Problemknoten.<ref group="Anm." name="CAuswertung" />}}
<syntaxhighlight lang="c" highlight="21,24" line start="650">
 Fall_L3:
   // Bedingung_L3: S rot && P+C+D schwarz
   // Transformation_L3:
   C = S->child[dir];   // aufbewahren
   // dir-Rotation um P:
   P->child[1−dir] = C; // neuer Elter von C
   S->child[dir] = P;
   if (--pParent >= &Parents[0]) {
     // Ersetze P bei seinem Elter durch S:
     D = *pParent;
     D->child[P == D->right] = S;
   }
   else // P war die Wurzel
     T->root = S; // S ist die neue Wurzel
   // Umfärbung:
   S->color = BLACK;
   P->color = RED;
   // Zuweisung nach der Transformation:
   S = C; // neues Geschwister von N (schwarz)
   D = S->child[1−dir]; // ferner Neffe
   if (D != NIL  &&  D->color == RED)
     goto Fall_L6;      // der ferne Neffe D ist rot
   C = S->child[ dir];  // naher  Neffe
   if (C != NIL  &&  C->color == RED)
     goto Fall_L5; // der nahe  Neffe C ist rot
   // Beide Neffen sind == NIL (erste Iteration)
   //   oder schwarz (später).
   // Also P rot && C+S+D schwarz <==> Bedingung_L4.
   // Das ist Fall_L4:
</syntaxhighlight>

=== Löschen Fall L4 ===
{{Mehrere Bilder
|align=right
|Kopfzeile = Löschen Fall L4<br/>[[#ZE|<small>(→Zeichenerklärung)</small>]]
|Bild1=Red-black_tree_delete_case_C0.svg
|Untertitel1=Iterationsstufe<br/><math>j\!=\!1</math>
|Breite1=71
|Bild2=Red-black_tree_perpendic_419_switch.svg
|Breite2=9
|Bild3=Red-black_tree_delete_case_C1.svg
|Breite3=117
|Untertitel3=<br/><math>j\!\ge\!2</math>
}}

{{Anker|Test L4}}
Der Elter <math>\mathsf{P}</math> von <math>\mathsf{N}</math> ist rot, aber sowohl das Geschwister <math>\mathsf{S}</math> des Problemknotens <math>\mathsf{N}</math> als auch dessen Kinder <math>\mathsf{C}</math> und <math>\mathsf{D}</math> sind schwarz, falls sie existieren.

Eine Invertierung der Farben von <math>\mathsf{P}</math> und <math>\mathsf{S}</math> lässt die Anzahl der schwarzen Knoten auf den Pfaden, die durch <math>\mathsf{S}</math> laufen, unverändert, fügt aber auf allen Pfaden durch <math>\mathsf{N}</math> einen schwarzen Knoten hinzu und gleicht damit den fehlenden schwarzen Knoten auf diesen Pfaden aus.
<syntaxhighlight lang="c" line start="710">
 Fall_L4:
   // Bedingung_L4: P rot && C+S+D schwarz
   // Transformation_L4:
   // Umfärbung:
   S->color = RED;
   P->color = BLACK;
   return; // Löschung fertiggestellt
</syntaxhighlight>

=== Löschen Fall L5 ===
{{Mehrere Bilder
|align=right
|Kopfzeile = Löschen Fall L5<br/>[[#ZE|<small>(→Zeichenerklärung)</small>]]
|Bild1=Red-black_tree_delete_case_D0rot.svg
|Untertitel1=Iterationsstufe<br/><math>j\!=\!1</math>
|Breite1=71
|Bild2=Red-black_tree_perpendic_919_switch.svg
|Breite2=9
|Bild3=Red-black_tree_delete_case_D1rot.svg
|Breite3=117
|Untertitel3=<br/><math>j\!\ge\!2</math>
}}

{{Anker|Test L5}}
Das Geschwister <math>\mathsf{S}</math> von <math>\mathsf{N}</math> ist schwarz, der nahe Neffe <math>\mathsf{C}</math> rot, während der ferne Neffe <math>\mathsf{D},</math> falls er existiert, schwarz ist.
Der im Diagramm rot-schwarz dargestellte Knoten <math>\mathsf{P}</math> behält seine Farbe, rot oder schwarz.

Eine (nicht-<code>dir</code>)-Rotation um <math>\mathsf{S}</math><ref group="Anm." name="PivotsInneresKind3" /> macht <math>\mathsf{C}</math> zum Elter von <math>\mathsf{S}</math> und zugleich zum Geschwister von <math>\mathsf{N}.</math> Danach invertiert man die Farben von <math>\mathsf{S}</math> und <math>\mathsf{C}.</math>
Dadurch werden die Pfade des Teilbaums <math>\mathsf{2}</math> so verändert, dass sie durch einen roten Knoten weniger und die Pfade durch den Knoten <math>\mathsf{D}</math> durch einen mehr führen. Die Zahl der schwarzen Knoten auf diesen Pfaden bleibt jedoch gleich.
Ferner hat nun <math>\mathsf{N}</math> ein schwarzes Geschwister, <math>\mathsf{C},</math> dessen fernes Kind, <math>\mathsf{S},</math> rot ist, womit man zum Fall L6 weitergehen kann. Weder <math>\mathsf{N}</math> noch <math>\mathsf{P}</math> noch die Schwarzhöhe werden durch diese Transformation beeinflusst.
<syntaxhighlight lang="c" line start="740">
 Fall_L5:
   // Bedingung_L5: S+D schwarz && C rot
   // Transformation_L5:
   // (nicht-dir)-Rotation um S:
   S->child[dir] = C->child[1−dir]; // NIL oder neuer Zeiger zu Teilbaum 3
   C->child[1−dir] = S;
     // dadurch wird S zum fernen Neffen von N
   P->child[1−dir] = C;
   // Umfärbung:
   C->color = BLACK;
   S->color = RED;
   // Zuweisung nach der Transformation:
   D = S; // neuer ferner Neffe
   S = C; // neues Geschwister von N
   // Weiter zu Fall_L6:
</syntaxhighlight>

=== Löschen Fall L6 ===
{{Mehrere Bilder
|align=right
|Kopfzeile = Löschen Fall L6<br/>[[#ZE|<small>(→Zeichenerklärung)</small>]]
|Bild1=Red-black_tree_delete_case_E0rot.svg
|Untertitel1=Iterationsstufe<br/><math>j\!=\!1</math>
|Breite1=71
|Bild2=Red-black_tree_perpendic_639erc_switch.svg
|Breite2=9
|Bild3=Red-black_tree_delete_case_E1rot.svg
|Breite3=96
|Untertitel3=<br/><math>j\!\ge\!2</math>
}}

{{Anker|Test L6}}
Die Farbe des Elters <math>\mathsf{P}</math> ist beliebig.
Das Geschwister <math>\mathsf{S}</math> von <math>\mathsf{N}</math> ist schwarz, und der ferne Neffe <math>\mathsf{D}</math> von <math>\mathsf{N}</math> ist rot.

Eine <code>dir</code>-Rotation um <math>\mathsf{P}</math><ref group="Anm." name="PivotsInneresKind3" /> macht <math>\mathsf{S}</math> zum Großelter von <math>\mathsf{N}.</math>
Nun reicht es, <math>\mathsf{S}</math> die Farbe von <math>\mathsf{P}</math> zu geben und <math>\mathsf{P}</math> sowie <math>\mathsf{D}</math> schwarz zu färben. <math>\mathsf{N}</math> hat immer noch dieselbe Farbe, wodurch die {{nowrap|Forderung '''!RR'''}} erfüllt bleibt. Aber <math>\mathsf{N}</math> hat nun einen zusätzlichen schwarzen Vorfahren: Falls <math>\mathsf{P}</math> vor der Transformation noch nicht schwarz war, so ist er nach der Transformation schwarz, und falls <math>\mathsf{P}</math> schon schwarz war, so hat <math>\mathsf{N}</math> nun <math>\mathsf{S}</math> als schwarzen Großelter, weswegen die Pfade, die durch <math>\mathsf{N}</math> führen, nun einen zusätzlichen schwarzen Knoten passieren.

Bei den Pfaden, die sich ändern und die nicht durch <math>\mathsf{N}</math> führen, gibt es zwei Möglichkeiten:

# Der Pfad führt durch die beliebig eingefärbte Wurzel des Teilbaums <math>\mathsf{3}</math>, die das neue Geschwister von <math>\mathsf{N}</math> ist. Dann muss der Pfad sowohl vor als auch nach der Transformation durch <math>\mathsf{S}</math> und <math>\mathsf{P}</math> führen. Da die beiden Knoten aber nur ihre Farben vertauscht haben, ändert sich an der Anzahl der schwarzen Knoten auf dem Pfad nichts.
# Der Pfad führt durch den neuen Onkel <math>\mathsf{D}</math> von <math>\mathsf{N},</math> welcher das {{nowrap|(nicht-<code>dir</code>)-Kind}} des Geschwisters <math>\mathsf{S}</math> ist. In diesem Fall führte der Pfad vorher durch <math>\mathsf{D}, \mathsf{S}</math> und {{nowrap|<math>\mathsf{P}</math>.}} Nach der Transformation führt er aber nur noch durch <math>\mathsf{D},</math> der von Rot auf Schwarz (die vorige Farbe von <math>\mathsf{S}</math>) umgefärbt wurde, und den Knoten <math>\mathsf{S},</math> welcher die Farbe von <math>\mathsf{P}</math> angenommen hat. Somit ändert sich die Anzahl der schwarzen Knoten eines solchen Pfades nicht.

Da die Anzahl der schwarzen Knoten in den Pfaden, die durch <math>\mathsf{N}</math> führen, sich um 1 erhöht, und in denen, die nicht durch <math>\mathsf{N}</math> führen, sich nicht ändert, ist die {{nowrap|1=Forderung '''S#='''}} wiederhergestellt.
<syntaxhighlight lang="c" line start="770">
 Fall_L6:
   // Bedingung_L6: S schwarz && D rot
   // Transformation_L6:
   // dir-Rotation um P:
   P->child[1−dir] = S->child[dir]; // NIL oder neuer Zeiger zu Teilbaum 3
   S->child[dir] = P;
   if (--pParent >= &Parents[0])    // P war nicht die Wurzel
   {
     // Ersetze P bei seinem Elter durch S:
     N = *pParent;
     N->child[P == N->right] = S;
   }
   else
     T->root = S; // S ist die neue Wurzel
   // Umfärbung:
   S->color = P->color;
   P->color = BLACK;
   D->color = BLACK;
   return; // Löschung fertiggestellt
 } // Ende RBdelete2
</syntaxhighlight>

== Operationen mit ganzen Rot-Schwarz-Bäumen ==
Die folgenden zwei Operationen haben ganze Rot-Schwarz-Bäume als Ein- und Ausgabeoperanden. Sie gehören nicht zum Standardsatz und fehlen in manchen Implementierungen. Es soll aber hier gezeigt werden, dass auch sie mit logarithmischem Aufwand durchgeführt werden können.

=== {{Anker|Verketten|Join}}Verketten (Join) ===
[[Datei:Red-black tree concat.svg|mini|216px|Verkettung von 2 Rot-Schwarz-Bäumen]]
Die Operation <code>JOIN(T<sub>L</sub>,k,T<sub>R</sub>)</code> verkettet (konkateniert) (englisch: ''join'' oder ''concat'') zwei Rot-Schwarz-Bäume über einen Einzelschlüssel mit logarithmischem Aufwand.<ref name="join-tarjan">{{Literatur |Autor=Robert Endre Tarjan |Titel=4. Search Trees 5. Linking and Cutting Trees |Sammelwerk=[[Society for Industrial and Applied Mathematics|SIAM]] |Reihe=Data structures and network algorithms |Datum=1983 |ISBN=978-0-89871-187-5 |Seiten=45-70 |DOI=10.1137/1.9781611970265.ch5}}</ref> Für die Sortierfolge müssen natürlich alle Schlüssel des ersten Baums <code>T<sub>L</sub></code> dem Einzelschlüssel <code>k</code> und dieser allen Schlüsseln des zweiten <code>T<sub>R</sub></code> vorangehen.<ref name="Knuth-S474">Donald E. Knuth: ''The Art of Computer Programming'', Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 474</ref>
Die [[Binärbaum#Traversierung|In-Order-Traversierung]] des verketteten Baums entspricht der Nacheinanderausführung der Traversierung des ersten Baums, gefolgt von der des einzelnen Knotens, gefolgt von der des zweiten Baums.

Skizze des Algorithmus:<br/>Ohne Beschränkung der Allgemeinheit sei der erste Baum nicht niedriger als der zweite, und der zweite habe eine schwarze Wurzel (Knoten <math>\mathsf{H}</math> in der Abbildung) der Schwarzhöhe <math>s</math>. Ferner sei dem zweiten Baum sein erstes Element <math>\mathsf{G}</math> bereits entnommen. Es spielt nachher die Rolle eines „Bindeglieds“.<br/>Man steigt an der rechten Flanke des ersten Baums bis zu einem schwarzen Knoten der Schwarzhöhe <math>s</math> hinunter, sein Name sei <math>\mathsf{F}</math>.
Der Knoten <math>\mathsf{G}</math> wird rot gefärbt und zum rechten Kind des Elters <math>\mathsf{E}</math> von <math>\mathsf{F}</math> gemacht.
Ist <math>\mathsf{E}</math> schwarz, dann ist der verkettete Baum in Rot-Schwarz-Form und die Verkettung abgeschlossen.
Ist <math>\mathsf{E}</math> jedoch rot, dann ist sein linkes Kind schwarz.
Nun lässt sich eine Reparaturschleife anschließen, die zur Wurzel aufsteigend dieselbe [[#SchleifeE|Schleifeninvariante]] hat wie die Operation Einfügen,
und <math>\mathsf{G}</math> ist der Problemknoten der ersten Iterationsstufe.

=== Massenoperationen ===
Aufbauend auf der JOIN-Operation können weitere Massen- und Mengenoperationen gebildet werden,<ref name="join-based">{{Literatur |Autor=Guy Edward Blelloch, Daniel Ferizovic, Yihan Sun |Hrsg=ACM |Titel=Just Join for Parallel Ordered Sets |Reihe=Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016) |Datum=2016 |ISBN=978-1-4503-4210-0 |Seiten=253–264 |arXiv=1602.02120 |DOI=10.1145/2935764.2935768}}</ref>
die allesamt logarithmische Laufzeit haben, so z.&nbsp;B. die komplementäre Operation des Aufspaltens (englisch: ''split'') eines Baums an einem Pfad.

Die ''Massenlöschung'' von allen Schlüsseln in einem zusammenhängenden Bereich [[Quasiordnung#Intervalle|(Intervall)]] kann durch zweimaliges Spalten und einmaliges Verketten geschehen oder, wenn das kleinste oder größte Element mit dabei ist, durch einmaliges Spalten. In ähnlicher Weise lässt sich ein Intervall mit logarithmischem Aufwand als Rot-Schwarz-Baum aus einem Rot-Schwarz-Baum herauspräparieren.

Eine ''Masseneinfügung'' kann durch einmaliges Spalten und zweimaliges Verketten durchgeführt werden, sofern die Menge als Rot-Schwarz-Baum vorbereitet ist und ihre Schlüssel in einem Intervall liegen, das im Zielbaum nicht vorkommt.

=== Mengenoperationen ===
Im selben Aufsatz wurde gezeigt, dass auch die Mengenoperationen [[Menge (Mathematik)#Schnittmenge (Schnitt, auch „Durchschnitt“)|Durchschnitt]], [[Menge (Mathematik)#Vereinigung (Vereinigungsmenge)|Vereinigung]] und [[Menge (Mathematik)#Differenz und Komplement|Differenz]] von digital repräsentierten (endlichen) Mengen sehr effizient (in logarithmischer Zeit) und in „natürlicher“ Parallelität implementiert werden können
(s. [[Binärer Suchbaum#Effiziente Massen- und Mengenoperationen aufbauend auf der JOIN-Operation]]).
Blelloch et.&nbsp;al. zeigen, dass sich diese Algorithmen sich so auf die 4 balancierten Suchbäume (AVL-, Rot-Schwarz-, Splay- und BB[α]) übertragen lassen, dass sich alles Spezifische im JOIN-Algorithmus abspielt.

== Höhenbeweis ==
Wie schon in der Einleitung ausgeführt, ist die besondere Eigenschaft von Rot-Schwarz-Bäumen, dass sie in logarithmischer Zeit – genauer in <math>\mathcal O(\log n)</math> mit <math>n</math> als der Anzahl der Schlüssel – ein Element im Baum ''suchen'', ''löschen'' oder ''einfügen'' können. Diese Operationen sind auf allen binären Suchbäumen von der Höhe <math>h</math> des Baumes abhängig. Je niedriger die Höhe des Baumes ist, desto schneller laufen die Operationen. Kann man nun beweisen, dass ein binärer Suchbaum mit <math>n</math> Elementen nie eine gewisse Höhe (im Falle des Rot-Schwarz-Baumes <math>2 \log_2(n\!+\!2)\!\!-\!\!2</math>) überschreitet, so hat man bewiesen, dass die oben genannten Operationen im schlechtesten Fall logarithmische Kosten haben.

{{Anker|Minimalbäume}}
'''Rot-Schwarz-Bäume mit kleinster Knotenzahl zu gegebener Höhe'''
[[Datei:5 minimal red-black trees nN.svg|320px|mini|Rot-Schwarz-Bäume RB<sub>''h''</sub> der Höhen ''h''=1,2,3,4,5,<br/>jeweils mit minimaler Knotenzahl 1,2,4,6 resp. 10.]]
Zu <math>h\geq 0</math> gibt es einen Rot-Schwarz-Baum der Höhe <math>h</math> mit
:{|
|-
|rowspan=3|<math>\begin{array}{ll} m_h &= 2^{\lfloor(h+1)/2\rfloor} + 2^{\lfloor h/2 \rfloor} - 2 \\
    &{= \begin{cases}
2 \cdot 2^{\tfrac{h}2}-2 = 2^{\tfrac{h}2+1}-2 \\
3 \cdot 2^{\tfrac{h-1}2}-2
\end{cases}}
\end{array}</math> || <small>(mit [[Gauß-Klammer]]n <math>\lfloor \, \rfloor</math>)</small>
|-
| wenn <math>h</math> gerade
|-
| wenn <math>h</math> ungerade
|}
Knoten, und keinen mit weniger.<ref group="Anm.">Diese Minimalbäume spielen bei den Rot-Schwarz-Bäumen eine ähnliche Rolle wie die [[Fibonacci-Baum|Fibonacci-Bäume]] bei den AVL-Bäumen.</ref><ref group="Anm.">Die Wurzel eines minimalen Rot-Schwarz-Baums ''un''gerader Höhe kann natürlich auch schwarz sein.</ref>

'''Beweis'''

Damit ein Rot-Schwarz-Baum einer bestimmten Höhe <math>h</math> eine ''minimale Knotenzahl'' besitzt, muss er genau einen längsten Pfad enthalten, und dieser eine größtmögliche Anzahl roter Knoten, um eine möglichst große Baumhöhe mit möglichst kleiner Schwarzhöhe zu erreichen. Seine Einfärbung hat also unten beim Blatt mit Rot zu beginnen, und sich in der Folge nach oben bis zur Wurzel mit Schwarz und Rot streng abwechselnd fortzusetzen. Außerhalb dieses die Baumhöhe definierenden Pfades hat er nur schwarze Knoten.<ref>[[#Sedgewick|Sedgewick]] 2011 S. 444 Proof sketch</ref> Denn angenommen, es gäbe dort einen roten Knoten, dann beeinträchtigt das Entfernen desselben die Rot-Schwarz-Eigenschaften nicht, sofern einer von seinen zwei (schwarzen) Kindknoten an seine Stelle nachrückt und der andere gleichzeitig einschließlich seines Teilbaums entfernt wird. Alle Teilbäume außerhalb des längsten Pfades sind somit [[Binärbaum#Begriffe|vollständige Binärbäume]] mit ausschließlich schwarzen Knoten.

Es gibt genau einen Rot-Schwarz-Baum der Höhe <math>h=1</math> mit einem roten Blatt, welches gleichzeitig die Wurzel ist. Also ist <math>m_1 = 1</math> in Übereinstimmung mit <math>2^{\lfloor (1+1)/2\rfloor} \!+\!2^{\lfloor 1/2 \rfloor} \!\!-\!\!2 = 2^1\!+\!2^0\!\!-\!\!2.</math>

Bei einem Minimalbaum (RB<sub>''h''</sub> in der Abbildung) der Höhe <math>h>1</math> sind die zwei Kindbäume der Wurzel von unterschiedlicher Höhe: der höhere enthält den die Höhe definierenden längsten Pfad und ist ein Minimalbaum der Höhe <math>h\!\!-\!\!1</math> mit <math>m_{h-1}</math> Knoten und der Schwarzhöhe <math>s:=\lfloor(h\!\!-\!\!1)/2\rfloor</math>; der niedrigere ist ein vollständiger Binärbaum mit Höhe = Schwarzhöhe <math>s,</math> hat also <math>2^s\!\!-\!\!1=2^{\lfloor(h-1)/2\rfloor}\!\!-\!\!1</math> Knoten. Damit ist rekursiv
{|
|-
|style="width:1.0em;"| || <math>m_h</math> || <math>=</math> || <math>(m_{h-1})</math> || || <math>+</math> || <math>(1)</math> || <math>+</math> || <math>(2^{\lfloor(h-1)/2\rfloor}-1)</math>
|-
| || || || (großer Kindbaum) || || || (Wurzel) || || (kleiner Kindbaum)
|-
|colspan="8"| woraus man
|-
| || <math>m_h</math> || <math>=</math> || <math>(2^{\lfloor h/2 \rfloor} + 2^{\lfloor(h-1)/2\rfloor} - 2)</math> ||style="width:2.0em;"| || || || <math>+</math> || <math>2^{\lfloor(h-1)/2\rfloor}</math>
|-
| || || <math>=</math> ||colspan="5"| <math>2^{\lfloor h/2 \rfloor} + 2^{\lfloor(h+1)/2\rfloor} - 2</math>
|}
ausrechnet.&nbsp;&nbsp;■

Der [[Funktionsgraph|Graph]] der Funktion <math>m_h</math> ist [[Konvexe und konkave Funktionen|konvex]] nach unten und stückweise [[Lineare Funktion|linear]] mit den Ecken an den Punkten <math>(h=2k\;|\;m_h=2^{k+1}\!\!-\!\!2)</math> mit <math>k \in \N .</math> Ferner ist <math>m_h=</math> A027383(''h''–1) für <math>h\geq 1</math> mit der {{nowrap|{{OEIS|A027383}}.}}

;Umformung
Wegen <math>3 > 2^{\tfrac32}</math> (eine Folge von <math>9>8</math>) haben wir für ungerades <math>h</math> die Ungleichung
: <math>m_h = 3 \cdot 2^{\tfrac{h-1}2}-2 = 3\cdot 2^{-\tfrac32}\cdot 2^{\tfrac{h+2}2}-2 > 2 \cdot 2^{\tfrac{h}2}-2,</math>
so dass sich für alle (geraden wie ungeraden) <math>h</math>
: <math>m_h \geq 2 \cdot 2^{\tfrac{h}2}-2</math>
ergibt.
Da <math>m_h</math> die kleinste Knotenzahl <math>n</math> für alle Rot-Schwarz-Bäume der Höhe <math>h</math> ist, gilt
: <math>2 \cdot 2^{\tfrac{h}2}-2 \leq m_h \leq n ,</math>
so dass <math>h</math> sich im Intervall
{|
|-
|style="width:1.0em;"| ||style="text-align:center;"| <math>\log_2(n+1)</math> ||style="width:4.5em;"| <math>\leq h \leq</math> || <math>2 \log_2(n+2)-2 = 2 \log_2 (n/2 +1)</math> ||style="width:12em;text-align:right"| <math>\bigl[ < 2 \log_2(n+1) \; \bigr]</math>
|-
| || (vollständiger Binärbaum) || ||style="text-align:center;"| (minimaler RB-Baum)
|}
befindet.<ref>Gleichheit am oberen Rand gilt für minimale RB-Bäume RB<sub>2''k''</sub> gerader Baumhöhe <math>h = 2 \cdot k</math> mit <math>n = 2 \cdot 2^k-2</math> Knoten und nur für diese. Damit ist die Ungleichung geringfügig genauer als das weitverbreitete <math>h < 2 \log_2(n+1) ,</math> z.&thinsp;B. in [[#Cormen2001|Cormen]] S. 264.</ref><ref group="Anm.">Diese RB-Bäume gestatten darüber hinaus nur eine einzige Einfärbung, sind aber nicht die einzigen RB-Bäume mit dieser Eigenschaft.<br/>Zur Höhe <math>h</math> gibt es <math>2^{h-1}</math> Formen von Minimalbäumen, da die Position des längsten Pfades der Position eines externen Blattes des vollständigen Binärbaums der Höhe <math>h\!\!-\!\!1</math> entspricht und durch diese Position die Lage aller anderen Knoten bestimmt ist. (Die Abbildung zeigt die äußerste linke Position.)</ref>

;Folgerung
Somit folgt die Behauptung, dass ein Rot-Schwarz-Baum eine maximale Höhe <math>h</math> von <math>2 \log_2(n\!+\!2)\!\!-\!\!2</math> hat und damit die Operationen ''suchen'', ''einfügen'' und ''löschen'' in logarithmischer Zeit erledigen kann. Drückt man dieses Ergebnis in der [[Landau-Symbole|O-Notation]] aus, so ergibt sich für die Kosten der oben genannten Operationen, dass sie alle in <math>\mathcal O(\log n)</math> liegen mit <math>n</math> als der Zahl der Schlüssel.<ref group="Anm.">Als eine Datenstruktur, die im homogenen [[Arbeitsspeicher]] (Hauptspeicher) untergebracht ist, ist der Rot-Schwarz-Baum durch dessen Größe beschränkt, also auch die Höhe des Baums und die Längen der Pfade von Blatt zu Wurzel.
Der Programmierer wird seinen Anwendern gegenüber eher die Knotenzahl einschränken als die Baumhöhe, die für den Anwender eher zufälliger Natur ist und ihn normalerweise nicht interessiert.<br/>
{{Anker|Stapelgröße}}Die folgende Tabelle gibt zu jeder Knotenzahl <math>n</math> eine Höhenangabe <math>h</math> zurück, die von einem Rot-Schwarz-Baum mit <math>\leq n</math> Elementen nicht überschritten wird. Gängig sind Hauptspeicher mit 32 Bit und 64 Bit breiten virtuellen [[Byte|8-Bit-Byte]]-Adressen. Da in einem 32-Bit-Adressraum maximal <math>2^{32}</math> Bytes untergebracht werden können und ein Knoten mindestens 2 Kind-Zeiger à je 4 Bytes benötigt, kann bei Benutzerdaten (Schlüssel + Wert) von <math>b</math> Bytes pro Knoten ein Baum mit maximal <math>n = 2^{32}/(2\cdot 4 \!+\! b)</math> Knoten untergebracht werden; bei <math>b = 3</math> sind das <math>n = 390451572 .</math> Wie die Tabelle zeigt, kann im 32-Bit-Adressraum die Höhe <math>h=55</math> durch einen Rot-Schwarz-Baum unmöglich überschritten werden.<br/>Für einen Adressraum mit 8 Byte breiten Adressen und <math>b=1</math> Byte Benutzerdaten hat man <math>n \le 2^{64}/(2\cdot 8 \!+\! b)</math><math>= 1085102592571150095 ,</math> so dass <math>h \leq 117</math> bleibt und beim Einsatz von <math>8 h = 8\cdot 117 = 936</math> Bytes für den Elter-Stapel dieser nicht überlaufen kann.
{| class="wikitable left" style="text-align:right;"
|+Umfang von Rot-Schwarz-Bäumen
|-
!style="width:1.8em;"| ||style="text-align:right;"| Anzahl Knoten <math>n \leq</math>||Baumhöhe <math>h \leq</math>||Nutzlänge <math>b \leq</math>
|-
| rowspan="10" | {{vertikal|32-Bit-Adressen}}||⋮||⋮||⋮
|-
|33554429||47||120
|-
|50331645||48||77
|-
|67108861||49||56
|-
|100663293||50||34
|-
|134217725||51||24
|-
|201326589||52||13
|-
|268435453||53||8
|-
|402653181||54||2
|-
|536870909||55||0
|-
| rowspan="10" |{{vertikal|64-Bit-Adressen}}||⋮||⋮||⋮
|-
|72057594037927933||109||240
|-
|108086391056891901||110||154
|-
|144115188075855869||111||112
|-
|216172782113783805||112||69
|-
|288230376151711741||113||48
|-
|432345564227567613||114||26
|-
|576460752303423485||115||16
|-
|864691128455135229||116||5
|-
|1152921504606846973||117||0
|}
Mit den Bezeichnungen [[#Höhenbeweis|im Text]] ist <math>n = m_{h+1}-1,</math> eine Maßgabe, die so knapp wie möglich unterhalb der Knotenzahl des nächstgrößeren Minimalbaums bleibt.
Ist der Speicherbedarf für alle Knoten gleich, können die Benutzerdaten pro Knoten maximal
:{|
|-
| rowspan="2" style="vertical-align:middle"| <math>b =
\begin{cases}
\\
\\
\end{cases}
</math>
|<math>2^{32}/n-2\cdot 4</math>|| ||im 32-Bit-Adressraum (4 Bytes/Adresse)
|-
|<math>2^{64}/n-2\cdot 8</math>|| ||im 64-Bit-Adressraum (8 Bytes/Adresse)
|}
Bytes umfassen.

'''Fazit'''

Ist der [[Stapelspeicher]] {{nowrap|<code>struct RBnode* Parents[]</code>}} für die Elter-Zeiger bei einem 32-Bit-Adressraum auf wenigstens <math>h = 54</math> Einträge mit insgesamt <math>4 h = 4\cdot 54 = 216</math> Bytes ausgelegt, so kann er unmöglich überlaufen.<br/>Dasselbe gilt bei einem 64-Bit-Adressraum für <math>h = 117</math> und einem Elter-Stapel der Größe <math>8 h = 8\cdot 117 = 936</math> Bytes.<br/>Bevor nämlich in beiden Fällen der Elter-Stapel überläuft, ist der Adressraum schon geplatzt.<br/>[[#Pfaff a|Ben Pfaff]] hat <code>#define RB_MAX_HEIGHT 128</code>.</ref>

== Durchschnittliche und amortisierte Laufzeit ==
Der Rot-Schwarz-Baum bietet [[Amortisierte Laufzeitanalyse|''amortisiert konstante'']] [[#Rebalancierung|Rebalancierungskosten]]<ref>Mehlhorn und Sanders widmen dem Thema in [[#Mehlhorn2|Mehlhorn 2008]] das Kapitel ''7.4 Amortized Analysis of Update Operations'' mit dem Theorem 7.3, S. 158:
:„Consider an (a,b)-tree with b ≥ 2a that is initially empty. For any sequence of n insert or remove operations, the total number of split or fuse operations is {{nowrap|''O''(n).“}}
In den Kontext der Rot-Schwarz-Bäume übersetzt heißt das:
:„Für eine beliebige Folge von <math>n</math> Einfüge- und Löschoperationen in einen anfänglich leeren Rot-Schwarz-Baum ist die Anzahl der Farbwechsel und Rotationen in {{nowrap|<math>\mathcal{O}(n)</math>.“}}
Damit ist der Aufwand pro Operation in einer solchen Sequenz in <math>\mathcal{O}(1),</math> also amortisiert konstant.
Im Beweis, der für [[2-3-4-Baum|(2,4)-Bäume]] geführt wird und bei dem die [[Account-Methode]] zum Zug kommt, werden nur die ''split''- und ''fuse''-Operationen abgerechnet – ein Aufsuchen der betroffenen Stelle im Baum wird überhaupt nicht erwähnt und auch nicht mitgezählt. Die Aussage bezieht sich also auf die ''reinen'' Reparaturkosten.</ref> und damit auch ''im Mittel konstante''.

Anwendungen von (binären) Suchbäumen, die neben Sequenzen von Einfügungen und Löschungen auch Suchoperationen enthalten, sind [[asymptotisch]] durch die logarithmische Laufzeit der letzteren dominiert.
Interessant ist der amortisiert konstante Modifikations-Aufwand jedoch, wenn der Suchbaum [[Persistente Datenstruktur|persistent]] gehalten werden soll, d.&nbsp;h. alle Versionen zugänglich bleiben sollen (s.&nbsp;a.&nbsp;[[Persistent data structure]]).<ref name="persistentRB" /><ref>[http://wiki.edinburghhacklab.com/PersistentRedBlackTreeSet Lightweight Java implementation of Persistent Red-Black Trees]</ref>

== Anzahlen von Rot-Schwarz-Bäumen ==
Die Folge [[OEIS:A001131|A001131]]<math>(n\!+\!1)</math> in OEIS gibt in Abhängigkeit von der Knotenzahl <math>n</math> die Gesamtzahl der Rot-Schwarz-Bäume, {{OEIS|A001137}} derer mit schwarzer Wurzel und {{OEIS|A001138}} derer mit roter Wurzel.

[[Datei:3 red-black trees nN.svg|86px|mini|Die 3 RB-Bäume mit 3 Schlüsseln]]
Die nebenstehende Abbildung zeigt den balancierten Binärbaum mit 3 Schlüsseln in 3 verschiedenen regelkonformen Rot-Schwarz-Einfärbungen.
Beim [[#Suchen|Suchen]] und [[#Traversieren|Traversieren]] ist wegen der identischen Verzweigungen der 3 Bäume alles Verhalten einschließlich Laufzeit gleich. Unterschiede gibt es aber bei Modifikationen, bspw. bei Einfügungen: Bei der linken Einfärbung sind alle Einfügungen vom Typ Transformation_E3 gefolgt von Transformation_E1, bei den rechten 2 Einfärbungen sind alle vom Typ Transformation_E2.

Zwar wird in einem reinen Einfügeszenario von den 3 möglichen Bäumen mit 3 Knoten (Schlüsseln) nur der eine Baum mit schwarzer Wurzel und 2 roten Kindern (der linke in der Abbildung) gebildet. Bezieht man jedoch Löschungen mit ein, dann kommen die zwei anderen Rot-Schwarz-Bäume (rechts in der Abbildung) hinzu,<br/>[[Datei:3 from 4.svg|162px|text-oben|rechts|4 Einfügungen und 1 Löschung]] und zwar der mit roter Wurzel über
:4 Einfügungen und 1 Löschung<br/>[[Datei:3 from 6.svg|306px|text-oben|rechts|6 Einfügungen und 3 Löschungen]]
und der mit schwarzer Wurzel über
:6 Einfügungen und 3 Löschungen
{{Absatz}}
und dies mit den oben beschriebenen Algorithmen für Einfügung und Löschung – jeweils bei geeignet gewählter Schlüsselfolge, die durch den Knoten mit blauer Kontur angegeben ist.

== Verwandtschaft mit 2-3-4-Bäumen ==
[[Datei:RB-to-2-3-4 2.svg|mini|180px|links|2 Kinder]]
[[Datei:RB-to-2-3-4 3L.svg|180px|mini|3 Kinder]]
[[Datei:RB-to-2-3-4 3R.svg|180px|mini|3 Kinder]]
[[Datei:RB-to-2-3-4 4.svg|mini|180px|links|4 Kinder]]
Die 4 kleinen Grafiken links und rechts zeigen, wie kleine Bausteine eines Rot-Schwarz-Baums (linke Hälften der Grafiken) mit einem (dicken) Knoten eines [[2-3-4-Baum]]s (rechte Hälften der Grafiken) zur Entsprechung gebracht werden können.
Man erzeugt aus einem Rot-Schwarz-Baum einen 2-3-4-Baum, indem man rote Kinder entsprechend ihrer Kindesrichtung links oder rechts als Datenelemente in den schwarzen Elterknoten hereinholt.<ref>[[#Mehlhorn1|Mehlhorn 1988]] S. 193</ref><ref>Wenn man die zwei Wahlmöglichkeiten bei 3 Kindern auf eine (bspw. auf die erste, die obere) einschränkt, kommt man zu den LLRB (Abkürzung für {{enS|left-leaning red–black}}) Bäumen, die im Wesentlichen dieselben informationstheoretischen Eigenschaften haben, bei deren Implementierung aber laut Sedgewick weniger Fälle zu unterscheiden sind (s.&nbsp;[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.282 Robert Sedgewick. Left-leaning Red–Black Trees] und [http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf PDF]).</ref>
<div style="clear:both;"></div>
[[Datei:Red-black tree example (B-tree analogy).svg|378px|mini|Der Rot-Schwarz-Baum des Beispiels dargestellt als 2-3-4-Baum]]
Umgekehrt kann man einen 2-3-4-Baum ganz einfach in einen Rot-Schwarz-Baum überführen: Aus einem Knoten mit 2 Datenelementen und 3 Kindzeigern (wie der Knoten [NIL,1,6] in der Abbildung) wird ein schwarzer Knoten ([[Datenelement]]) mit 1 Kindzeiger und einem roten Kindknoten (Datenelement), der noch 2 Kindzeiger enthält; aus einem Knoten mit 3 Datenelementen und 4 Kindzeigern (wie die Knoten [8,13,17] und [22,25,27] in der Abbildung) wird ein schwarzer Knoten (Datenelement) mit 2 roten Kindknoten (jeweils 1 Datenelement und 2 Kindzeiger).

Darüber hinaus gibt es Entsprechungen bei den Modifikationsoperationen (Einfügen, Löschen) zwischen Farbwechsel und Rotationen auf Seite der Rot-Schwarz-Bäume und den Aktionen Spalten ({{enS|split}}) und Verschmelzen ({{enS|fuse}}) bei den 2-3-4-Bäumen.

Im Gegensatz zu 2-3-4-Bäumen muss man bei Rot-Schwarz-Bäumen nicht den »Füllzustand« (Speicherausnutzung, {{enS|fill factor}}) der Knoten beobachten und verwalten, weshalb letztere als sehr effiziente Art der Implementierung der 2-3-4-Bäume gelten.<ref>[[#Mehlhorn1|Mehlhorn 1988]] S. 187</ref>

== Vergleich mit AVL-Baum ==
Die Menge der [[AVL-Baum|AVL-Bäume]] ist eine [[Teilmenge|echte Teilmenge]] in der Menge der Rot-Schwarz-Bäume. Denn jeder Binärbaum, der [[AVL-Baum#Das AVL-Kriterium|das AVL-Kriterium]] erfüllt, lässt sich in einer das Rot-Schwarz-Kriterium erfüllenden Weise {{nowrap|einfärben.<ref>{{Internetquelle |autor=Paul E. Black |url=https://xlinux.nist.gov/dads//HTML/redblack.html |titel=Red-black tree |werk=Dictionary of Algorithms and Data Structures |hrsg=[[National Institute of Standards and Technology]] |datum=2015-04-13 |sprache=en |abruf=2016-07-02}}</ref><ref>s.&nbsp;„One should be able to color any AVL tree, without restructuring or rotation, to transform it into a Red-Black tree.“ Junghyun Chae in [http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948 AVL Trees vs. Red-Black Trees?] abgerufen am 14. Oktober 2015 und Beweis in [[AVL-Baum#VergleichRB]].</ref>}}

[[Datei:Red-black, but not AVL tree nN.svg|mini|122px|Rot-Schwarz-, aber nicht AVL-Baum]]
Es gibt aber Rot-Schwarz-Bäume, die das AVL-Kriterium nicht erfüllen. Die nebenstehende Abbildung zeigt zum Beispiel einen Rot-Schwarz-Baum mit 6 Knoten und der [[binärer Suchbaum#Suchtiefen und Pfadlängensummen|externen Pfadlängensumme]] 21, während 20 die größte externe Pfadlängensumme bei AVL-Bäumen (und zugleich die kleinstmögliche für ''alle'' Binärbäume) dieser Knotenzahl ist. Konsequenterweise ist auch die Worst-Case-Höhe des AVL-Baums kleiner als die des Rot-Schwarz-Baums, und zwar asymptotisch um den Faktor {{nowrap|(2 log<sub>2</sub> [[Goldener Schnitt|Φ]])<sup>−1</sup> ≈ 0,720.}} Allgemein werden AVL-Bäume als besser balanciert und ihr Suchverhalten als günstiger angesehen.

Die Laufzeiten für alle angeführten Operationen unterscheiden sich im Mittel und im Worst Case asymptotisch nur um einen konstanten Faktor, gehören also derselben [[Landau-Symbole|Komplexitätsklasse]] an. Der Rot-Schwarz-Baum bietet allerdings [[#Durchschnittliche und amortisierte Laufzeit|amortisiert konstante]] Einfüge- und Löschkosten (jeweils nur Rebalancierung – ''ohne'' Navigation). Beim AVL-Baum sind nur die Einfügekosten amortisiert konstant, die Löschkosten immerhin ''im Mittel'' konstant.

Realistische Anwendungssituationen mit Performancedaten und -vergleichen – auch mit weiteren Suchalgorithmen und Spielarten der Datenstrukturen – finden sich bei [[#Pfaff b|Ben Pfaff]]. Seine Ergebnisse zeigen in 79 Messungen unter anderem die sehr große Ähnlichkeit von AVL-Bäumen (''AVL'') und Rot-Schwarz-Bäumen (''RB'') mit Laufzeitverhältnissen {{bruch|''AVL''|''RB''}} zwischen 0,677 und 1,077 bei einem [[Median]] von ≈0,947 und einem [[Geometrisches Mittel|geometrischen Mittelwert]] von ≈0,910.

Der Speicherplatzbedarf ist praktisch identisch: 1 Bit für das Rot-Schwarz-Attribut gegenüber 2 Bits<ref group="Anm.">oder auch nur 1 Bit (s.&nbsp;[[AVL-Baum#BF 1 Bit|AVL-Implementierung]])</ref> für den AVL-Balance-Faktor. Während die Balance-Faktoren eines AVL-Baums direkt von seiner [[Graphentheorie|(graphentheoretischen)]] Gestalt abhängen, sind bei Rot-Schwarz-Bäumen derselben Gestalt – außer bei den [[#Minimalbäume|Minimalbäumen]] gerader Höhe – unterschiedliche Einfärbungen möglich (s.&nbsp;Abschnitt [[#Anzahlen von Rot-Schwarz-Bäumen|Anzahlen von Rot-Schwarz-Bäumen]]). Dabei wirken sich die Unterschiede der Einfärbungen nur auf die Modifikations- und nicht auf die Navigationsoperationen aus. Des Weiteren kann jede mögliche Gestalt eines AVL-Baums durch gezielte Einfügungen auch hergestellt werden. Bezogen auf die Baumform gilt dies auch für Rot-Schwarz-Bäume; es gibt aber Baumformen, bei denen durchaus regelkonforme Einfärbungen in einem reinen Einfügeszenario nicht bewirkt werden können.

Eine Folge dieser etwas größeren Freiheitsgrade ist, dass im Rot-Schwarz-Baum die für die Einfügung oder Löschung erforderlichen Farbänderungen und Rotationen schon während des Suchvorgangs – also beim Abstieg – vorgenommen werden können.<ref>
{{Cite web
|title = Red Black Trees
|language=en
|url = http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
|website = eternallyconfuzzled.com
|accessdate = 2015-10-14
|archiveurl = https://web.archive.org/web/20070927222509/http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx
|archivedate = 2007-09-27
|offline = yes}} (Eternally Confuzzled)
</ref>
Diese {{nowrap|»Top-Down-Strategie«<ref>[[#Mehlhorn1|Mehlhorn 1988]] S. 197–198.</ref>}} ist bspw. für [[Nebenläufigkeit|nebenläufige]] und persistente Programmierung {{nowrap|interessant.<ref group="Anm.">Die [[Lock|Sperren]], die bei einem der Veränderung unterworfenen Baum der Erhaltung seiner [[ACID|Konsistenz]] dienen, können bei der Top-Down-Strategie von der Wurzel beginnend zu den Blättern fortschreitend gesetzt werden. Halten sich alle den Baum bearbeitenden Prozesse an solche (und ggf. weitere) Protokolle, kann ein [[Deadlock (Informatik)|Deadlock]] vermieden werden.</ref><ref>s.&nbsp;a. [http://attractivechaos.wordpress.com/2008/10/02/comparison-of-binary-search-trees/ Comparison of Binary Search Trees] abgerufen am 14. Oktober 2015; oder Paul Callahan in [http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948 AVL Trees vs. Red-Black Trees?] abgerufen am 14. Oktober 2015</ref>}}

So bleibt beim Einfügen der frisch eingefügte Knoten rot. Das bedeutet, dass eine zugehörige Suchfunktion im Abstieg den Baum entlang dem betroffenen Pfad (in logarithmischer Zeit) so vorbereiten kann, dass das endgültige Einfügen unmittelbar bei einem schwarzen Elter in Form eines roten Knotens geschehen oder eben (nach gfl. Inspektion des Elters) auch unterbleiben kann. Genauso kann beim Löschen eine (andere) Suchfunktion den Baum im Abstieg so vorbereiten, dass der zu löschende Knoten rot ist. In beiden Fällen bleibt der Baum sowohl beim Durchführen wie beim Unterlassen der Modifikation ein gültiger Rot-Schwarz-Baum, einer Modifikation, die beim Einfügen nur aus dem Setzen eines einzigen Zeigers besteht und beim Löschen nur geringfügig komplizierter ist. Demgegenüber gibt es beim AVL-Baum Baumformen, bei denen die Entscheidung betreffend den Vollzug der Modifikation nicht mit derart geringer Implikation offen gehalten werden kann.

== Verwendung von Rot-Schwarz-Bäumen ==
Im [[Java Development Kit]] sind die Klassen <code>TreeSet</code><ref>[http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html Java Class TreeSet auf docs.oracle.com]</ref> und <code>TreeMap</code><ref>[http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html Java Class TreeMap auf docs.oracle.com]</ref> als Rot-Schwarz-Bäume implementiert. Sie stellen geordnete Mengen bzw. geordnete [[Assoziatives Datenfeld|Dictionarys]] zur Verfügung.

== Weitere Bäume ==
* [[2-3-4-Baum]]
* [[AVL-Baum]]
* [[B-Baum]]
* [[Heap (Datenstruktur)]]
* [[Suchbaum]]

== Literatur ==
* {{Anker|Pfaff a}}Ben Pfaff: ''An Introduction to Binary Search Trees and Balanced Trees.'' Free Software Foundation, Boston 2004, [ftp://ftp.gnu.org/gnu/avl/avl-2.0.3.pdf.gz ftp.gnu.org] (PDF gzip; 1662&nbsp;kB; abgerufen am 13. Januar 2019).
* {{Anker|Pfaff b}}Ben Pfaff: ''Performance Analysis of BSTs in System Software.'' Stanford University, 2004, [http://www.stanford.edu/~blp/papers/libavl.pdf stanford.edu] (PDF; 316&nbsp;kB).
* {{Anker|Cormen2001}}{{BibISBN|0262032937|Seite=273–301}}
* {{BibISBN|3893194622|Seite=260–270}}
* {{Anker|Sedgewick}}[[Robert Sedgewick (Informatiker)|Robert Sedgewick]], Kevin Wayne: [http://bookshelf.theopensourcelibrary.org/AlgorithmsFourthEdition.pdf ''Algorithms Fourth Edition.''] Pearson Education, 2011, ISBN 978-0-321-57351-3, S. 432–447.
* Andrew Binstock, Jon Rex: ''Practical Algorithms for Programmers.'' Addison-Wesley Professional, 1995, ISBN 0-201-63208-X.
* {{Anker|Mehlhorn1}}Kurt Mehlhorn: ''Datenstrukturen und effiziente Algorithmen.'' Teubner Stuttgart 1988, ISBN 3-519-12255-3.
* {{Anker|Mehlhorn2}}{{BibISBN|9783540779773}}
* {{Anker|sdsu}}Roger Whitney (San Diego State University): [http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html#RTFToC2 ''CS 660: Red–Black tree notes'']
* [http://mathworld.wolfram.com/Red-BlackTree.html ''Mathworld: Red–Black Tree'']

== Weblinks ==

* [http://fbim.fh-regensburg.de/~saj39122/gikasch/start.html Java-Applet zur Arbeitsweise eines Rot-Schwarz-Baumes]
* [http://leechuck.de/ginfin/baum1/infoprojekt2.html Semesterarbeit zum Thema Rot-Schwarz-Bäume]

== Anmerkungen ==
<references group="Anm." />

== Einzelnachweise ==
<references />

{{Lesenswert|5. November 2005|10544578}}

[[Kategorie:Suchbaum]]
[[Kategorie:Datenstruktur]]