Rot-Schwarz-Baum

Ein Rot-Schwarz-Baum, auch RS-Baum oder RB-Baum, (englisch red–black tree oder RB tree) ist eine Datenstruktur vom Typ binärer Suchbaum, die „sehr schnellen“ Zugriff auf die in ihr gespeicherten Schlüssel garantiert. Rot-Schwarz-Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben,[1] welcher sie symmetric binary B-trees nannte. Der heutige Name geht auf Leonidas J. Guibas und Robert Sedgewick zurück, die 1978 die rot-schwarze Farbkonvention einführten.[2] 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 Balance des Baums in einer Weise festlegen, dass die Höhe eines Baums mit ${\displaystyle n}$ Elementen nie größer als ${\displaystyle 2\log _{2}(n\!+\!2)\!-\!2}$ sein kann.[Anm. 1] Somit können die wichtigsten Operationen in Suchbäumen – Suchen, Einfügen und Löschen – garantiert in ${\displaystyle {\mathcal {O}}(\log n)}$ (s. Landau-Symbole) ausgeführt werden.

Rot-Schwarz-Baum
	Komplexität bei ${\displaystyle n}$ Elementen
Platz	${\displaystyle {\mathcal {O}}(n)}$
Operation	im Mittel, amortisiert	Worst Case
Suchen	${\displaystyle {\mathcal {O}}(\log n)}$	${\displaystyle {\mathcal {O}}(\log n)}$
Querschritt	${\displaystyle {\mathcal {O}}(1)}$	${\displaystyle {\mathcal {O}}(\log n)}$
Min, Max	${\displaystyle {\mathcal {O}}(\log n)}$	${\displaystyle {\mathcal {O}}(\log n)}$
Einfügen	${\displaystyle {\mathcal {O}}(1)}$^†	${\displaystyle {\mathcal {O}}(\log n)}$
Löschen	${\displaystyle {\mathcal {O}}(1)}$^†	${\displaystyle {\mathcal {O}}(\log n)}$
^† ohne Navigation (nur Rebalancierung)
Platz- und Zeit-Komplexitäten

Definition

Zusätzlich z​u den Eigenschaften d​es binären Suchbaums h​at jeder Knoten d​es Rot-Schwarz-Baums e​in weiteres Attribut, genannt Farbe, d​as zwei Werte annehmen kann, genannt »rot« (engl. RED) und »schwarz« (engl. BLACK). Diese Einfärbung h​at die folgenden z​wei Forderungen z​u erfüllen:[3]

Forderung !RR (»Nicht Rot Rot«):	Ein Kindknoten eines roten Knotens ist schwarz.
Forderung S#= (»Schwarz Zahl Gleich«):	Jeder Pfad von einem gegebenen Knoten zu einem seiner Nachfahren mit Ausgangsgrad ≤1, d. h. zu Blättern oder Halbblättern, im Folgenden kurz »Pfadenden« genannt,[4] enthält die gleiche Anzahl schwarzer Knoten.

Rot-Schwarz-Baum
der Baumhöhe 4 und der Schwarzhöhe 2

Eine unmittelbare Folge aus den Forderungen ist, dass ein Halbblatt (bspw. der Knoten ${\displaystyle {\mathsf {1}}}$ im Beispielbaum) schwarz und sein (einzelnes) Kind (der Knoten ${\displaystyle {\mathsf {6}}}$) rot sein muss, denn beide sind Pfadenden, und der Pfad zum Pfadende ${\displaystyle {\mathsf {1}}}$_links ist um genau den Knoten ${\displaystyle {\mathsf {6}}}$ kürzer.

Aus beiden Forderungen zusammen f​olgt ähnlich unmittelbar, d​ass ein schwarzer Knoten, d​er nicht d​ie Wurzel ist, e​in Geschwister hat.

Schwarzhöhe, Baumhöhe

Die auf allen Pfaden von Pfadende zu Wurzel gleiche Anzahl ${\displaystyle s}$ schwarzer Knoten wird die Schwarzhöhe (englisch black height)[5][6] 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 ${\displaystyle {\mathsf {6,22,27}}}$ im Beispielbaum – oder ein 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 ≥ 1. Die roten Knoten ${\displaystyle {\mathsf {8,17}},}$ aber auch die schwarzen Knoten ${\displaystyle {\mathsf {1,11,15,25}},}$ haben Schwarzhöhe 1. Die schwarzen Knoten ${\displaystyle {\mathsf {1,25}}}$ haben Baumhöhe 2, die Knoten ${\displaystyle {\mathsf {11,15}}}$ Baumhöhe 1, und ${\displaystyle {\mathsf {1}}}$ ist der einzige Knoten mit Ausgangsgrad 1, das einzige Halbblatt.

Durch d​ie zwei Forderungen[7] w​ird die wichtigste Eigenschaft v​on Rot-Schwarz-Bäumen sichergestellt:

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

Bei d​en herausgehobenen Operationen Suchen, Einfügen u​nd Löschen i​st der a​uf einer Ebene d​es Baums anfallende Aufwand konstant. Also i​st die Laufzeit höchstens proportional z​ur Anzahl d​er Knoten i​n einem Pfad, d​ie wieder d​urch die Höhe limitiert ist, welche ihrerseits d​urch den Logarithmus d​er Knotenzahl limitiert ist.

NIL-Knoten

Dieser Artikel n​immt die i​m Artikel Binärer Suchbaum i​n dessen Abb. 1A aufgezeigte u​nd bei vielen Baumstrukturen übliche Sichtweise ein, b​ei der d​ie Knoten d​ie Schlüssel tragen (»knotenorientierte Speicherung«), unabhängig davon, o​b sie interne Knoten o​der (interne) Blätter sind.

Derselbe Rot-Schwarz-Baum mit NIL-Knoten
(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 (englisch auch »missing nodes«[8]) zwischen den Schlüsseln stehen. Die Darstellung mit  NIL -Knoten bringt das einseitige Pfadende ${\displaystyle {\mathsf {1}}}$_links (links am Knoten ${\displaystyle {\mathsf {1}}}$) ähnlich deutlich heraus wie die paarigen Pfadenden an den Knoten ${\displaystyle {\mathsf {6,11,15,22,27}}.}$ Völlig unabhängig von der grafischen Darstellung lassen sich die NIL-Knoten sowohl als unterschiedslose Nullzeiger (Felder mit dem Zeigerwert NULL) wie als unterschiedslose Zeiger zu ein und demselben Wächterknoten implementieren. Diese Option beim Zeigerwert wird zur Unterscheidung vom Nullzeiger im Text als NIL-Zeiger oder NIL und im Beispielcode als NIL kenntlich gemacht.

Werden d​ie NIL-Knoten jedoch a​ls individuelle Knoten aufgefasst, d​ann kommt für s​ie eine Forderung hinzu, s​o dass folgende d​rei Forderungen aufzustellen sind:[9]^: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 h​at für d​as Verständnis d​er Sachverhalte vernachlässigbaren Nutzen u​nd hat b​ei „naiver“ Implementierung e​her einen ungünstigen Einfluss.[Anm. 2]

Datenstruktur

Der nachfolgende Beispielcode, der in der Programmiersprache C formuliert ist, nimmt Bezug auf eine Deklaration des Baumknotens der folgenden Art:

 struct RBnode  // Knotenfeld
 {
   struct RBnode* child[2]; // zwei Zeiger zu Kindknoten,
                // == NIL bedeutet:
                //   kein Knoten an dieser Stelle
   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

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. a. W.: der von einem NIL-Knoten gewurzelte Teilbaum ist leer und hat Schwarz- und Baumhöhe 0. Sein Zeigerwert X == NIL ist weniger wichtig als der Ort, wo dieser Wert in der 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.
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.
Funktionell entspricht er exakt dem NIL-Knoten, ohne dass ihm allerdings irgendeine Individualität zukäme.

Werden d​er Datenstruktur Rot-Schwarz-Baum Operationen z​um Zugriff u​nd zur Verwaltung beigegeben, s​o werden d​iese nur d​ann als zugehörig angesehen, w​enn sie d​ie Rot-Schwarz-Forderungen aufrechterhalten, i​ndem sie insbesondere d​en Baum n​ach einer modifizierenden Operation überprüfen u​nd wenn nötig reparieren. So erweitert w​ird die Datenstruktur z​u einem Abstrakten Datentyp (ADT). Bei Suchbäumen g​ibt es i​m Englischen dafür a​uch die Charakterisierung a​ls self-balancing tree.

Navigationsoperationen

Die Navigationsoperationen, d​as sind d​ie verschiedenen Suchoperationen, d​as Traversieren, Aufsuchen erstes o​der letztes Element u​nd ähnliche, lassen d​en Baum unverändert (nur lesender Zugriff) u​nd funktionieren i​m Prinzip a​uf jedem binären Suchbaum. Die dortigen Algorithmen u​nd Angaben z​ur Komplexität gelten genauso für Rot-Schwarz-Bäume – m​it der Präzisierung, d​ass die Höhe d​es Rot-Schwarz-Baums s​ich immer logarithmisch z​ur Anzahl d​er Knoten verhält.

Das Suchen e​ines Elements (oder e​iner Lücke) anhand seines Schlüssels i​st die wichtigste u​nter den Navigationsoperationen. (Die (Höhen-)Balancierung d​es Rot-Schwarz-Baums versucht, a​uf diese Operation h​in zu optimieren.) Sie unterstützt e​ine Art »direkten Zugriff« (im Gegensatz z​um sequentiellen Zugriff d​er Traversierung) u​nd wird i​n der Regel a​ls vorausgehende Operation b​ei den Modifikationsoperationen (Einfügen o​der Löschen) z​um Auffinden d​es betroffenen Knotens eingesetzt.

Das Suchen s​etzt eine totale Quasiordnung a​uf der Menge d​er Schlüssel voraus, d​ie am flexibelsten d​urch eine Vergleichsfunktion realisiert wird. Wenn Duplikate i​m Baum erlaubt s​ein sollen, d​ann empfiehlt s​ich eine leicht abgewandelte Suchfunktion.

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 erste Iterationsstufe eines Falles und die rechte die höheren Iterationsstufen desselben Falles beschreibt. Die mittlere Spalte unterteilt die Transformation in mindestens zwei Abschnitte:

1. Der erste (mit »Bedingung« beschriftete) Abschnitt zeigt die Ausgangskonstellation,
2. eine eventuelle »Rotation« folgt im nächsten Schritt,
3. danach eine »Umfärbung«, falls erforderlich.
4. Wenn der Baum dann noch nicht rebalanciert ist, zeigt der letzte (mit »Zuweisung« beschriftete) Abschnitt die Konstellation nach der erneuten Zuweisung des Problemknotens ${\displaystyle {\mathsf {N}}}$ und der durch ihn bestimmten anderen Knoten. Diese Konstellation wird zur Weiterbehandlung an einen entsprechenden Fall übergeben.

Obwohl die Konstellation der ersten Iterationsstufe in der der höheren im Prinzip enthalten ist, wird sie um der größeren Deutlichkeit willen gebracht, und zwar ohne leere Teilbäume.
Beim Löschen wird in der ersten Iterationsstufe das Pfadende, das einen schwarzen Knoten verloren hat (und das dem Problemknoten ${\displaystyle {\mathsf {N}}}$ entspricht, der hier leer ist), durch einen blauen Pfeil nach links markiert.

1. Der alte Problemknoten (${\displaystyle {\mathsf {N}}}$ im Abschnitt »Bedingung« eines Diagramms) hat eine blaue Kontur; und wenn die Operation nicht beendet ist, dann auch der neue (im Abschnitt »Zuweisung«).
2. Das Symbol stellt einen (echten) schwarzen und einen (echten) roten Knoten dar.
3. Das Symbol stellt einen !RR-konform bei seinem Elter angebundenen Teilbaum dar. Er hat die Schwarzhöhe ${\displaystyle j\!-\!\!1}$ mit ${\displaystyle j}$ als der Iterationsstufe.
   In der ersten Iterationsstufe ist die Schwarzhöhe 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.
4. Das Dreieck (ohne die kleine schwarze Kreisfläche an der Spitze) symbolisiert einen !RR-konform bei seinem Elter angebundenen Teilbaum, dessen Schwarzhöhe ${\displaystyle j\!-\!\!2}$ ist mit ${\displaystyle j}$ als der Iterationsstufe. Seine Schwarzhöhe ist also um 1 niedriger als die der -Teilbäume. In der ersten Iterationsstufe wäre die Schwarzhöhe negativ, was so zu interpretieren ist, dass schon sein Elter leer ist.
5. Zweimal 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 ${\displaystyle {\mathsf {N}}}$ in einen Rot-Schwarz-Baum unterscheiden sich nicht von denen eines allgemeinen binären Suchbaums: Der Zeiger zum neuen Knoten ersetzt einen 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 ${\displaystyle {\mathsf {P}}}$ – für das Fehlen 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 ${\displaystyle {\mathsf {N}}}$ reflektiert, im Funktionsparameter dir ∈ {LEFT,RIGHT} übergeben wird.[Anm. 3] Ferner wird angenommen, dass diese Suchfunktion den Stapel struct RBnode* Parents[] der Vorfahren von ${\displaystyle {\mathsf {P}}}$ gebildet hat.[10] Der ebenfalls übergebene Zeiger struct RBnode** pParent zeigt in diesem Stapel auf den Zeiger des direkten Elters des einzufügenden Knotens. Wenn der Baum leer ist, ist pParent < &Parents[0] (und dir irrelevant). Andernfalls ist Parents[0] gleich dem Zeiger auf den Wurzelknoten, pParent ≥ &Parents[0], und dir die Kindesrichtung des neuen Knotens.

Der Knoten ${\displaystyle {\mathsf {N}}}$ wird zunächst rot gefärbt, damit die Schwarzhöhe des Baumes erhalten bleibt.[11]

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« (englisch rebalancing) bezeichnet.

Der neue Knoten ${\displaystyle {\mathsf {N}}}$ (wie englisch node) ist der gerade betrachtete »Problemknoten«. Sein Elter ist ${\displaystyle {\mathsf {P}}}$ (wie englisch parent). Der Großelter sei ${\displaystyle {\mathsf {G}}}$ (wie englisch grandparent) und der Onkel (das Geschwister des Elters) ${\displaystyle {\mathsf {U}}}$ (wie englisch uncle) genannt.

Der Kopf d​er Funktion RBinsert1 z​um Einfügen e​ines Knotens n​ach einer vorher erfolgten u​nd nicht erfolgreichen Suchoperation könnte w​ie folgt aussehen:[Anm. 4]

 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); // muss ein echter 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_E0 trifft NICHT zu.)
     N = G; // neuer Problemknoten (kann die Wurzel sein)
     P = *pParent; // -> Elterknoten von N
 Start_E:

Rebalancierung nach dem Einfügen: Die Schleife zur Überprüfung und Reparatur des Baums steigt vom roten Blatt ${\displaystyle {\mathsf {N}}}$ zur Wurzel auf. Ihre Invariante ist:

• Die Forderung !RR (»Nicht Rot Rot«) gilt für alle Paare (Knoten←Elter) im Baum mit höchstens einer Ausnahme – beim Paar (${\displaystyle {\mathsf {N}}}$←${\displaystyle {\mathsf {P}}}$). Dies wird als »Rot-Verletzung« (englisch red violation) angesehen, welche ${\displaystyle {\mathsf {N}}}$ als »Problemknoten« definiert.
  Gilt !RR auch dort, entweder weil der Elter ${\displaystyle {\mathsf {P}}}$ nicht existiert (Fall E0) oder schwarz ist (Fall E1), 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.

Die Zusammenschau bringt d​ie Diagramme i​n einer a​uf die Farbkonstellation zugespitzten Form.

Bedingung

Fall →

Rota- tion

Zuwei- sung

Ergebnis

→ Test

${\displaystyle \Delta s}$

${\displaystyle {\mathsf {P}}}$

${\displaystyle {\mathsf {G}}}$

${\displaystyle {\mathsf {U}}}$

x

${\displaystyle {\mathsf {P}}}$

${\displaystyle {\mathsf {G}}}$

${\displaystyle {\mathsf {U}}}$

x

—

E0

—

✓

E1

✓

E2

${\displaystyle {\mathsf {N}}}$:=${\displaystyle {\mathsf {G}}}$

?

?

?

?

E0

1

i

E3

${\displaystyle {\mathsf {P}}}$↶${\displaystyle {\mathsf {N}}}$

${\displaystyle {\mathsf {N}}}$:=${\displaystyle {\mathsf {P}}}$

o

E4

0

o

E4

${\displaystyle {\mathsf {P}}}$↷${\displaystyle {\mathsf {G}}}$

✓

—

E5

✓

Einfügen: Zusammenschau der Fälle

Einfügen: Zusammenschau d​er Fälle[12]

Die möglichen Konstellationen lassen s​ich in s​echs Fälle aufteilen, z​u denen e​s Transformationen (enthaltend Rotation und/oder Umfärbung) gibt, d​ie entweder a​uf der betrachteten Ebene o​der über weitere Iterationsschritte a​uf höheren Ebenen z​ur Rebalancierung d​es Baumes führen.

In d​er nebenstehenden Tabelle w​ird ein Fall d​urch 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 Fallnummer,
• 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 ${\displaystyle {\mathsf {P}},{\mathsf {G}}}$ und ${\displaystyle {\mathsf {U}}.}$ Manche Fälle benötigen darüber hinaus eine vierte Angabe x zur Kindesrichtung von ${\displaystyle {\mathsf {N}},}$ und zwar steht »o« (wie englisch outer) für eine Rechts-Rechts- oder Links-Links-Kindesrichtung von ${\displaystyle {\mathsf {N}}}$ zu ${\displaystyle {\mathsf {P}}}$ zu ${\displaystyle {\mathsf {G}}}$ und »i« (wie englisch 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 Fall E2 für beide Kindesrichtungen von ${\displaystyle {\mathsf {N}}}$ und das, obwohl das zugehörige Diagramm nur eine Kindesrichtung zeigt.

Die Konstellationen i​n der Gruppe Bedingung genügen d​er Schleifeninvariante, u​nd ihre logische Summe schöpft d​iese zu 100 % aus.

Die Transformation, deren Fallnummer in der Spalte 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 →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 Zuweisung für den Problemknoten ${\displaystyle {\mathsf {N}},}$ auch die Knoten ${\displaystyle {\mathsf {P}},{\mathsf {G}},{\mathsf {U}}}$ sowie die Angabe x zur Kindesrichtung von ${\displaystyle {\mathsf {N}}}$ neu zuordnet. Die Spaltengruppe Ergebnis und der mit »Zuweisung« 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 →Test kommt der Eintrag »E0« nur bei der Transformation_E2 vor. Er bedeutet einen neuen Iterationsschritt, der mit dem Test auf die while-Bedingung_E0 in der do while-Schleife beginnt, und zwar zwei Baumebenen (eine Schwarzebene ${\displaystyle \Delta s}$) näher an der Wurzel. Danach sind auch die Schwarzhöhen aller Teilbäume ≥ 1. Da die Anzahl der Baumebenen mit der Höhe ${\displaystyle h}$ übereinstimmt, können maximal ${\displaystyle {\tfrac {h}{2}}}$ Iterationen vorkommen. Nun ist der Aufwand für eine Iteration beschränkt (d. h. in ${\displaystyle {\mathcal {O}}(1)}$) und damit der für die gesamte Einfügeoperation in ${\displaystyle {\mathcal {O}}(h)={\mathcal {O}}(\log n)}$ (mit oder ohne Suchen). Die reine Rebalancierung ist gemäß Abschnitt Durchschnittliche und amortisierte Laufzeit im Mittel und amortisiert in ${\displaystyle {\mathcal {O}}(1).}$

Bei e​inem Eintrag i​n der Spalte Rotation i​st eine Rotation a​n der Transformation beteiligt. Man entnimmt d​er Tabelle sofort, d​ass bei e​iner Einfügeoperation maximal z​wei Rotationen vorkommen, u​nd zwar b​ei Fall E4 n​ach Fall E3. Denn n​ach einer Rotation k​ommt kein n​euer Iterationsschritt – d​ie Rotationen befinden s​ich endrekursiv a​m Ende d​er letzten ausgeführten Iteration.

Die Kindesrichtung von ${\displaystyle {\mathsf {N}}}$ entscheidet insbesondere über die nachfolgenden Rotationsrichtungen. Bei Fall E3 bestimmt sie aber auch die Auswahl des Falles: Hat ${\displaystyle {\mathsf {P}}}$ dieselbe Kindesrichtung wie ${\displaystyle {\mathsf {N}},}$ dann ist die Angabe x (s. Zusammenschau) auf »o« für »außen«, sonst auf »i« für »innen« zu setzen.[13]

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

Jeder Fall w​ird unter seiner Fallnummer erläutert u​nd einschließlich Test (auf d​ie ihn charakterisierende Bedingung) u​nd Transformation d​urch ein Stück C-Code g​enau beschrieben.[14]

Einfügen Fall E1: Der Elter ${\displaystyle {\mathsf {P}}}$ des (roten) Problemknotens ${\displaystyle {\mathsf {N}}}$ ist schwarz.

Nach Eintritt dieser Bedingung gibt es kein Paar (Knoten←Elter) (mehr), das die Forderung !RR verletzt. Ferner ist nach Voraussetzung (Schleifeninvariante) die Anzahl der schwarzen Knoten auf allen Pfaden dieselbe. Damit ist der Baum ohne weitere Aktion in Rot-Schwarz-Form.

     if (P->color == BLACK) // Bedingung_E1
       // Transformation_E1:
       return; // Einfügung fertiggestellt
 
     // In den verbleibenden Fällen ist der Elter P rot.
     if (pParent <= &Parents[0]) // Bedingung_E5
       goto Fall_E5; // Der Elter P ist die Wurzel.

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

(→Zeichenerklärung)

1. Iteration

Höhere Iteration

Einfügen Fall E2: Sowohl der Onkel ${\displaystyle {\mathsf {U}}}$ als auch der Elter ${\displaystyle {\mathsf {P}}}$ des Problemknotens ${\displaystyle {\mathsf {N}}}$ ist rot.

Die Umfärbung von ${\displaystyle {\mathsf {P}}}$ und ${\displaystyle {\mathsf {U}}}$ in schwarz und von ${\displaystyle {\mathsf {G}}}$ in rot stellt die Forderung !RR im Teilbaum mit Wurzel ${\displaystyle {\mathsf {G}}}$ wieder her (und zwar bei beiden Kindesrichtungen von ${\displaystyle {\mathsf {N}}}$). Auf keinem Pfad ändert sich die Anzahl der schwarzen Knoten. Durch diese Transformation_E2 wird die »Rot-Verletzung« um zwei Baum-Ebenen (eine Schwarz-Ebene) nach oben verschoben mit ${\displaystyle {\mathsf {G}}}$ als neuem Problemknoten.[Anm. 5]

     G = *(--pParent);      // Der Großelter G von N existiert.
     dir = (P == G->right); // Kindesrichtung von P
     U = G->child[!dir];    // Onkel
     if (U == NIL  ||  U->color == BLACK)
       goto Test_E3;        // Der Onkel U ist schwarz.
     // Bedingung_E2: N+P+U rot
     // Transformation_E2:
     // 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

Einfügen Fall E0: Der Problemknoten (hier: ${\displaystyle {\mathsf {G}}}$) ist die Wurzel. (Wie oben angemerkt, könnte eine rote Wurzel ohne Verletzung der Rot-Schwarz-Forderungen auf schwarz umgefärbt werden[7] – was den Test auf Bedingung_E5 und den Fall E5 überflüssig machen würde.)

Nach d​er obigen Transformation_E2 i​st !RR (»Nicht Rot Rot«) überall erfüllt, u​nd der Baum i​n Rot-Schwarz-Form.

   // Bedingung_E0: pParent < &Parents[0]
   //               ===> G ist die alte und neue Wurzel des Baums T.
   return; // Einfügung fertiggestellt

1. Iteration

Höhere Iteration

Einfügen Fall E3: Der Problemknoten ${\displaystyle {\mathsf {N}}}$ hat keinen oder einen schwarzen Onkel und hat eine Kindesrichtung entgegengesetzt zu der seines roten Elters ${\displaystyle {\mathsf {P}},}$ d. h., ${\displaystyle {\mathsf {N}}}$ ist innerer Enkel.

Eine Rotation um ${\displaystyle {\mathsf {P}}}$[Anm. 6] vertauscht die Rollen von ${\displaystyle {\mathsf {N}}}$ und ${\displaystyle {\mathsf {P}},}$ und zwar eine Linksrotation, wenn ${\displaystyle {\mathsf {P}}}$ linkes Kind (d. h. dir == LEFT) ist, sonst eine Rechtsrotation. (Im Folgenden wird eine solche Rotation als dir-Rotation bezeichnet.) Dadurch werden die Pfade des Teilbaums ${\displaystyle {\mathsf {2}}}$ so verändert, dass sie durch einen Knoten mehr und die des Teilbaums ${\displaystyle {\mathsf {4}}}$ 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 Forderung S#= und die Schleifeninvariante erfüllt bleibt.

Die Ergebniskonstellation entspricht der Eingangskonstellation des Falles E4 mit ${\displaystyle {\mathsf {P}}}$ als dem neuen Problemknoten.

 Test_E3:
   if (N != P->child[dir]) { // Bedingung_E3: N ist innerer Enkel
                             //               && N+P rot && U schwarz
     // Transformation_E3:
     // dir-Rotation um P:
     P->child[!dir] = N->child[dir]; // neuer Elter für Teilbaum 3
     N->child[dir] = P;
     G->child[dir] = N;
     // Neuzuweisung nach der Transformation:
     N = P; // neuer Problemknoten (rot) und äußerer Enkel
     P = G->child[dir]; // neuer Elter von N (rot)
   }

1. Iteration

Höhere Iteration

Einfügen Fall E4: Der Problemknoten ${\displaystyle {\mathsf {N}}}$ hat keinen oder einen schwarzen Onkel. Seine Kindesrichtung ist dieselbe wie die von ${\displaystyle {\mathsf {P}},}$ d. h., ${\displaystyle {\mathsf {N}}}$ ist äußerer Enkel.

Eine (nicht-dir)-Rotation um ${\displaystyle {\mathsf {G}}}$[Anm. 6] macht ${\displaystyle {\mathsf {P}}}$ zum Elter sowohl von ${\displaystyle {\mathsf {N}}}$ als auch von ${\displaystyle {\mathsf {G}}.}$ Da ${\displaystyle {\mathsf {P}}}$ rot war, muss wegen Forderung !RR ${\displaystyle {\mathsf {G}}}$ schwarz sein. Invertiert man nun die Farben von ${\displaystyle {\mathsf {G}}}$ und ${\displaystyle {\mathsf {P}},}$ so ist in dem dadurch entstehenden Baum die Forderung !RR wieder erfüllt. Die Forderung S#= bleibt ebenfalls erfüllt, da alle Pfade, die durch einen dieser drei Knoten laufen, vorher durch ${\displaystyle {\mathsf {G}}}$ liefen und nun alle durch ${\displaystyle {\mathsf {P}}}$ laufen, der inzwischen – wie ${\displaystyle {\mathsf {G}}}$ vor der Transformation – der einzige schwarze der drei Knoten ist.

   // Bedingung_E4: N ist äußerer Enkel && N+P rot && U schwarz
   // Transformation_E4:
   // (nicht-dir)-Rotation um G:
   G->child[dir] = P->child[!dir]; // neuer Elter für Teilbaum 3
   P->child[!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

Einfügen Fall E5: Der rote Elter ${\displaystyle {\mathsf {P}}}$ des Problemknotens ${\displaystyle {\mathsf {N}}}$ ist gleichzeitig die Wurzel des Baums.

Eine Umfärbung von ${\displaystyle {\mathsf {P}}}$ in schwarz stellt die Forderung !RR im ganzen Baum wieder her. Auf jedem Pfad erhöht sich die Anzahl der schwarzen Knoten um 1.

 Fall_E5:
   // Der Elter P von N ist die Wurzel des Baums.
   // Transformation_E5:
   // 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

Operation Löschen

Das Löschen eines Knotens, sein Name sei ${\displaystyle {\mathsf {R}}}$ (wie englisch remove), aus einem Rot-Schwarz-Baum erfolgt wie bei einem binären Suchbaum.

Den Fall, dass ${\displaystyle {\mathsf {R}}}$ die kinderlose Wurzel ist, erledigt man sofort, indem man sie durch einen Nullknoten ersetzt.

Hat der Knoten ${\displaystyle {\mathsf {R}}}$ ein oder gar kein Kind, dann bleibt er der Löschknoten. Hat ${\displaystyle {\mathsf {R}}}$ aber zwei Kinder, dann nimmt man, ohne letztlich die Sortierreihenfolge zu stören, als effektiven Löschknoten seinen hinsichtlich Reihenfolge linken oder rechten Nachbarn (dieser kann kein rechtes resp. kein linkes Kind haben!) – natürlich, nachdem man vorher die Benutzerdaten ausgetauscht hat.[15] Die Löschung kann also durch die Entfernung eines Knotens mit maximal einem Kind durchgeführt werden, eines Knotens, der weiterhin mit ${\displaystyle {\mathsf {R}}}$ benannt sei. Mit ${\displaystyle {\mathsf {P}}}$ (wie englisch parent) sei der Elter von ${\displaystyle {\mathsf {R}}}$ und mit dir (wie englisch direction) die Kindesrichtung von ${\displaystyle {\mathsf {R}}}$ (rechtes oder linkes Kind von ${\displaystyle {\mathsf {P}}}$) bezeichnet.

Einfache Fälle

Hat ${\displaystyle {\mathsf {R}}}$ genau ein Kind, so ist dieses zwangsläufig rot. Man färbt es schwarz und macht es an der Kindesrichtung dir zum Kind von ${\displaystyle {\mathsf {P}}.}$ Damit ist ${\displaystyle {\mathsf {R}}}$ aus dem Baum entfernt, und die 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 Forderung S#= (»Schwarz Zahl Gleich«) erfüllt bleibt.

Hat ${\displaystyle {\mathsf {R}}}$ kein Kind und ist rot, so wird es bei seinem (schwarzen) Elter einfach durch einen Nullknoten 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 Forderung S#= erfüllt bleibt.

Das Löschen eines schwarzen Blattes

Am kompliziertesten ist der Fall, wo ${\displaystyle {\mathsf {R}}}$ nicht die Wurzel ist, kein Kind hat und schwarz, also ein schwarzes Blatt ist.

Nach der Ersetzung von ${\displaystyle {\mathsf {R}}}$ bei ${\displaystyle {\mathsf {P}}}$ durch NIL enthalten die durch dieses Pfadende führenden Pfade einen schwarzen Knoten weniger als vorher, somit einen weniger als die übrigen Pfade (sofern es solche gibt) – in Verletzung der Forderung S#=. Deshalb sei diese Position ${\displaystyle {\mathsf {N}}}$ im Baum als »Problemknoten« bezeichnet.

Der Knoten ${\displaystyle {\mathsf {R}}}$ war nicht die Wurzel und, da er schwarz war, hatte er ein (echtes) Geschwister, das (nicht-dir)-Kind[Anm. 7] von ${\displaystyle {\mathsf {P}},}$ welches mit ${\displaystyle {\mathsf {S}}}$ (wie englisch sibling) bezeichnet sei. Dessen (möglicherweise leeres) dir-Kind ${\displaystyle {\mathsf {C}}}$ (wie englisch close) ist der »nahe« Neffe von ${\displaystyle {\mathsf {N}}}$ mit derselben Kindesrichtung; das andere (ebenfalls möglicherweise leere) Kind ${\displaystyle {\mathsf {D}}}$ (wie englisch distant) der »ferne« Neffe.

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

Der Kopf einer Funktion RBdelete2 zum Löschen eines schwarzen Knotens ${\displaystyle {\mathsf {R}}}$ ohne Kind, der nicht die Wurzel ist, könnte dann wie folgt aussehen:[Anm. 8]

 void RBdelete2(
 RBtree* T,                  // -> Rot-Schwarz-Baum
 struct RBnode*   Parents[], // Liste der -> Vorfahren
 struct RBnode** pParent,    // ->-> Elterknoten von R
 struct RBnode*   R)         // -> zu löschender Knoten, hier: schwarz
 {
   byte dir;         // Richtung ∈ {LEFT, RIGHT}
   struct RBnode* N; // -> Problemknoten
   struct RBnode* P; // -> Elterknoten von R, später 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(R != NIL);
   assert(pParent >= Parents[0]); // R ist nicht die Wurzel.
   P = *pParent; // Elter von R
   dir = (R == P->right); // Kindesrichtung von R:
   // Wenn nicht right, dann left:
   assert(R != P->right ? R == P->left : true);
   assert(R->color == BLACK);
   assert(R->left  == NIL);
   assert(R->right == NIL);
   // Ersetze R bei seinem Elter P durch NIL:
   P->child[dir] = NIL;
   goto Start_L; // Sprung in die Schleife

Rebalancierung nach dem Löschen: Die Schleife zur Überprüfung und Reparatur des Baums steigt vom »Problemknoten« ${\displaystyle {\mathsf {N}},}$ d. i. zunächst das neue Pfadende N = NIL, zur Wurzel auf. Ihre Invariante ist:

• Die Anzahl der schwarzen Knoten in den Pfaden durch ${\displaystyle {\mathsf {N}}}$ 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, bei ${\displaystyle {\mathsf {N}}}$ eine sog. »Schwarz-Verletzung« (englisch black violation) vorliegt.
• Ist ${\displaystyle j}$ die Iterationsstufe, dann hat ${\displaystyle {\mathsf {N}}}$ die Schwarzhöhe ${\displaystyle j\!-\!\!1}$ 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 symbolisiert.
  In den höheren Iterationsstufen ist ${\displaystyle {\mathsf {N}}}$ ein echter schwarzer Knoten und wird in den Diagrammen mit der blauen Kontur des Problemknotens gebracht.[Anm. 9]
• Die Forderung !RR (»Nicht Rot Rot«) ist überall erfüllt.

Die Zusammenschau bringt d​ie Diagramme i​n einer a​uf die Farbkonstellation zugespitzten Form.

Bedingung

Fall →

Rota- tion

Zuwei- sung

Ergebnis

→ Test

${\displaystyle \Delta s}$

${\displaystyle {\mathsf {P}}}$

${\displaystyle {\mathsf {C}}}$

${\displaystyle {\mathsf {S}}}$

${\displaystyle {\mathsf {D}}}$

${\displaystyle {\mathsf {P}}}$

${\displaystyle {\mathsf {C}}}$

${\displaystyle {\mathsf {S}}}$

${\displaystyle {\mathsf {D}}}$

—

L0

—

✓

L1

${\displaystyle {\mathsf {N}}}$:=${\displaystyle {\mathsf {P}}}$

?

?

?

?

L0

1

L2

${\displaystyle {\mathsf {P}}}$↶${\displaystyle {\mathsf {S}}}$

${\displaystyle {\mathsf {N}}}$:=${\displaystyle {\mathsf {N}}}$

?

?

L3

0

L3

✓

L4

${\displaystyle {\mathsf {C}}}$↷${\displaystyle {\mathsf {S}}}$

${\displaystyle {\mathsf {N}}}$:=${\displaystyle {\mathsf {N}}}$

L5

0

L5

${\displaystyle {\mathsf {P}}}$↶${\displaystyle {\mathsf {S}}}$

✓

Löschen: Zusammenschau der Fälle

Löschen: Zusammenschau d​er Fälle[16][17]

Die möglichen Farbkonstellationen lassen s​ich in s​echs Fälle gruppieren, z​u denen e​s Transformationen (enthaltend Rotation und/oder Umfärbung) gibt, d​ie entweder a​uf der betrachteten Ebene o​der über weitere Iterationsschritte a​uf höheren Ebenen z​u einer Rebalancierung d​es Baumes führen.

In d​er nebenstehenden Tabelle w​ird ein Fall d​urch eine Zeile repräsentiert, die

• die Bedingung, das ist die Konstellation, die den Fall definiert,
• die Fallnummer,
• die Konstellation nach Transformation und ggf. Zuweisung in der Spaltengruppe Ergebnis

enthält. Eine Konstellation (4 Spalten) besteht aus den Farben der 4 Knoten ${\displaystyle {\mathsf {P}},{\mathsf {C}},{\mathsf {S}},{\mathsf {D}}.}$ Eine Zelle ist leer gelassen, wenn es auf die Angabe nicht ankommt. Zweimal auf einer Zeile bedeutet zweimal dieselbe Knotenfarbe, schwarz oder rot.

Die Konstellationen in der Gruppe Bedingung genügen der Schleifeninvariante, und ihre logische Summe schöpft diese zu 100 % aus. Sie sind im mit »Bedingung« beschrifteten Abschnitt im zum Fall gehörigen Diagramm nochmals als Teilbaum skizziert.

Die Transformation, deren Fallnummer in der Spalte 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 →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 Zuweisung für den Problemknoten ${\displaystyle {\mathsf {N}},}$ auch die Knoten ${\displaystyle {\mathsf {P}},{\mathsf {C}},{\mathsf {S}},{\mathsf {D}}}$ eindeutig bestimmt. Die Spaltengruppe Ergebnis und der mit »Zuweisung« 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 »L0« kommt nur bei der Transformation_L1 vor und bedeutet einen neuen Iterationsschritt auf der um 1 höheren Ebene im Baum (gleichzeitig eine Schwarzebene ${\displaystyle \Delta s}$), beginnend mit dem Test auf die Bedingung_L0. Danach sind die Schwarzhöhen aller Teilbäume ≥ 1. Die Anzahl der Ebenen stimmt mit der Höhe ${\displaystyle h}$ überein, so dass höchstens ${\displaystyle h}$ Iterationen vorkommen können. Nun ist der Aufwand für eine Iteration beschränkt (d. h. in ${\displaystyle {\mathcal {O}}(1)}$) und damit der für die gesamte Löschoperation in ${\displaystyle {\mathcal {O}}(h)={\mathcal {O}}(\log n).}$ Gemäß Abschnitt Durchschnittliche und amortisierte Laufzeit ist der Rebalancierungsaufwand im Mittel sogar konstant.

Bei e​inem Eintrag i​n der Spalte Rotation i​st eine Rotation a​n der Transformation beteiligt. Und d​ie Tabelle zeigt, d​ass bei e​iner Löschung maximal d​rei Rotationen (von Fall L2 über L4 z​u L5) erforderlich sind. Denn n​ach einer Rotation k​ommt kein n​euer Iterationsschritt – d​ie Rotationen befinden s​ich endrekursiv a​m Ende d​er letzten Iteration.

Die Kindesrichtung des Problemknotens ${\displaystyle {\mathsf {N}}}$ bestimmt sowohl die nachfolgenden Rotationsrichtungen wie die Kindesrichtungen der Neffen ${\displaystyle {\mathsf {C}}}$ und ${\displaystyle {\mathsf {D}}.}$ Im Beispielcode wird dies mithilfe der Variablen dir gelöst.[13] Die Diagramme bei den Fällen zeigen jedoch ${\displaystyle {\mathsf {N}}}$ immer links von ${\displaystyle {\mathsf {P}}}$.

   // Beginn der (do while)-Schleife:
   do {
     // pParent >= &Parents[0]
     // ===> Bedingung_L0 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[!dir]; // Geschwister von N
     if (S->color == RED)
       goto Fall_L2; // Bedingung_L2: S rot ===> P+C+D schwarz
     // S ist schwarz:
     D = S->child[!dir]; // ferner Neffe
     if (D != NIL  &&  D->color == RED)
       goto Fall_L5;     // der ferne Neffe D ist rot
     C = S->child[ dir]; // naher  Neffe
     if (C != NIL  &&  C->color == RED)
       goto Fall_L4;     // der nahe  Neffe C ist rot
     // Beide Neffen sind == NIL (erste Iteration) oder schwarz (später).
     if (P->color == RED)
       goto Fall_L3; // P rot && C+S+D schwarz <==> Bedingung_L3

Jeder Fall w​ird unter seiner Fallnummer erläutert u​nd einschließlich Test (auf d​ie ihn charakterisierende Bedingung) u​nd Transformation d​urch ein Stück C-Code g​enau beschrieben.[14][Anm. 5]

(→Zeichenerklärung)

1. Iteration

Höhere Iteration

Löschen Fall L1: Der Elter ${\displaystyle {\mathsf {P}}}$ des Problemknotens ${\displaystyle {\mathsf {N}}}$ und das Geschwister ${\displaystyle {\mathsf {S}}}$ sind schwarz, ebenso die Kinder ${\displaystyle {\mathsf {C}}}$ und ${\displaystyle {\mathsf {D}}}$ von ${\displaystyle {\mathsf {S}},}$ falls sie existieren.

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

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

Löschen Fall L0: Der Problemknoten (hier: ${\displaystyle {\mathsf {P}}}$) ist die Wurzel.

In diesem Fall ist man fertig, da überhaupt alle Pfade durch ${\displaystyle {\mathsf {P}}}$ führen (und somit alle Pfade einen schwarzen Knoten weniger enthalten als vorher). Die Schwarzhöhe des Baumes verringert sich dabei um 1.

   // Bedingung_L0: pParent < &Parents[0]
   //               ===> P ist die alte und neue Wurzel des Baums T.
   return; // Löschung fertiggestellt

1. Iteration

Höhere Iteration

Löschen Fall L2: Das Geschwister ${\displaystyle {\mathsf {S}}}$ des Problemknotens ${\displaystyle {\mathsf {N}}}$ ist rot.

Eine Rotation um ${\displaystyle {\mathsf {P}}}$[Anm. 10] macht ${\displaystyle {\mathsf {S}}}$ zum Großelter von ${\displaystyle {\mathsf {N}},}$ und zwar eine Linksrotation, wenn ${\displaystyle {\mathsf {N}}}$ linkes Kind (d. h. dir == LEFT) ist, sonst eine Rechtsrotation. (Im Folgenden wird eine solche Rotation als dir-Rotation bezeichnet.) Danach invertiert man die Farben von ${\displaystyle {\mathsf {P}}}$ und ${\displaystyle {\mathsf {S}}.}$ Alle Pfade haben weiterhin dieselbe Anzahl an schwarzen Knoten, aber ${\displaystyle {\mathsf {N}}}$ hat nun ein schwarzes Geschwister, ${\displaystyle {\mathsf {C}},}$ und einen roten Elter, ${\displaystyle {\mathsf {P}},}$ weswegen man nun zu Fall L3, L4 oder L5 weitergehen kann – mit ${\displaystyle {\mathsf {N}}}$ als altem und neuem Problemknoten.[Anm. 5]

 Fall_L2:
   // Bedingung_L2: S rot && P+C+D schwarz
   // Transformation_L2:
   C = S->child[dir];  // aufbewahren
   // dir-Rotation um P:
   P->child[!dir] = C; // neuer Elter von C
   S->child[dir] = P;
   if (--pParent >= &Parents[0]) {
     // Ersetze P bei seinem Elter durch S:
     R = *pParent;
     R->child[P == R->right] = S;
   }
   else // P war die Wurzel
     T->root = S; // S ist die neue Wurzel
   // Umfärbung:
   S->color = BLACK;
   P->color = RED;
   // Neuzuweisung nach der Transformation:
   S = C; // neues Geschwister von N (schwarz)
   D = S->child[!dir]; // ferner Neffe
   if (D != NIL  &&  D->color == RED)
     goto Fall_L5;     // der ferne Neffe D ist rot
   C = S->child[ dir]; // naher  Neffe
   if (C != NIL  &&  C->color == RED)
     goto Fall_L4; // der nahe  Neffe C ist rot
   // Beide Neffen sind == NIL (erste Iteration)
   //   oder schwarz (später).
   // Also P rot && C+S+D schwarz <==> Bedingung_L3.
   // Das ist Fall_L3:

1. Iteration

Höhere Iteration

Löschen Fall L3: Der Elter ${\displaystyle {\mathsf {P}}}$ von ${\displaystyle {\mathsf {N}}}$ ist rot, aber sowohl das Geschwister ${\displaystyle {\mathsf {S}}}$ des Problemknotens ${\displaystyle {\mathsf {N}}}$ als auch dessen Kinder ${\displaystyle {\mathsf {C}}}$ und ${\displaystyle {\mathsf {D}}}$ sind schwarz, falls sie existieren.

Eine Invertierung der Farben von ${\displaystyle {\mathsf {P}}}$ und ${\displaystyle {\mathsf {S}}}$ lässt die Anzahl der schwarzen Knoten auf den Pfaden, die durch ${\displaystyle {\mathsf {S}}}$ laufen, unverändert, fügt aber auf allen Pfaden durch ${\displaystyle {\mathsf {N}}}$ einen schwarzen Knoten hinzu und gleicht damit den fehlenden schwarzen Knoten auf diesen Pfaden aus.

 Fall_L3:
   // Bedingung_L3: P rot && C+S+D schwarz
   // Transformation_L3:
   // Umfärbung:
   S->color = RED;
   P->color = BLACK;
   return; // Löschung fertiggestellt

1. Iteration

Höhere Iteration

Löschen Fall L4: Das Geschwister ${\displaystyle {\mathsf {S}}}$ von ${\displaystyle {\mathsf {N}}}$ ist schwarz, der nahe Neffe ${\displaystyle {\mathsf {C}}}$ rot, während der ferne Neffe ${\displaystyle {\mathsf {D}},}$ falls er existiert, schwarz ist. Der im Diagramm rot-schwarz dargestellte Knoten ${\displaystyle {\mathsf {P}}}$ behält seine Farbe, rot oder schwarz.

Eine (nicht-dir)-Rotation um ${\displaystyle {\mathsf {S}}}$[Anm. 6] macht ${\displaystyle {\mathsf {C}}}$ zum Elter von ${\displaystyle {\mathsf {S}}}$ und zugleich zum Geschwister von ${\displaystyle {\mathsf {N}}.}$ Danach invertiert man die Farben von ${\displaystyle {\mathsf {S}}}$ und ${\displaystyle {\mathsf {C}}.}$ Dadurch werden die Pfade des Teilbaums ${\displaystyle {\mathsf {2}}}$ so verändert, dass sie durch einen roten Knoten weniger und die Pfade durch den Knoten ${\displaystyle {\mathsf {D}}}$ durch einen mehr führen. Die Zahl der schwarzen Knoten auf diesen Pfaden bleibt jedoch gleich. Ferner hat nun ${\displaystyle {\mathsf {N}}}$ ein schwarzes Geschwister, ${\displaystyle {\mathsf {C}},}$ dessen fernes Kind, ${\displaystyle {\mathsf {S}},}$ rot ist, womit man zum Fall L5 weitergehen kann. Weder ${\displaystyle {\mathsf {N}}}$ noch ${\displaystyle {\mathsf {P}}}$ noch die Schwarzhöhe werden durch diese Transformation beeinflusst.

 Fall_L4:
   // Bedingung_L4: S+D schwarz && C rot
   // Transformation_L4:
   // (nicht-dir)-Rotation um S:
   S->child[dir] = C->child[!dir]; // neuer Elter für Teilbaum 3
   C->child[!dir] = S;
     // dadurch wird S zum fernen Neffen von N
   P->child[!dir] = C;
   // Umfärbung:
   C->color = BLACK;
   S->color = RED;
   // Neuzuweisung nach der Transformation:
   D = S; // neuer ferner Neffe
   S = C; // neues Geschwister von N
   // Weiter zu Fall_L5:

1. Iteration

Höhere Iteration

Löschen Fall L5: Die Farbe des Elters ${\displaystyle {\mathsf {P}}}$ ist beliebig. Das Geschwister ${\displaystyle {\mathsf {S}}}$ von ${\displaystyle {\mathsf {N}}}$ ist schwarz, und der ferne Neffe ${\displaystyle {\mathsf {D}}}$ von ${\displaystyle {\mathsf {N}}}$ ist rot.

Eine dir-Rotation um ${\displaystyle {\mathsf {P}}}$[Anm. 6] macht ${\displaystyle {\mathsf {S}}}$ zum Großelter von ${\displaystyle {\mathsf {N}}.}$ Nun reicht es, ${\displaystyle {\mathsf {S}}}$ die Farbe von ${\displaystyle {\mathsf {P}}}$ zu geben und ${\displaystyle {\mathsf {P}}}$ sowie ${\displaystyle {\mathsf {D}}}$ schwarz zu färben. ${\displaystyle {\mathsf {N}}}$ hat immer noch dieselbe Farbe, wodurch die Forderung !RR erfüllt bleibt. Aber ${\displaystyle {\mathsf {N}}}$ hat nun einen zusätzlichen schwarzen Vorfahren: Falls ${\displaystyle {\mathsf {P}}}$ vor der Transformation noch nicht schwarz war, so ist er nach der Transformation schwarz, und falls ${\displaystyle {\mathsf {P}}}$ schon schwarz war, so hat ${\displaystyle {\mathsf {N}}}$ nun ${\displaystyle {\mathsf {S}}}$ als schwarzen Großelter, weswegen die Pfade, die durch ${\displaystyle {\mathsf {N}}}$ führen, nun einen zusätzlichen schwarzen Knoten passieren.

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

1. Der Pfad führt durch die beliebig eingefärbte Wurzel des Teilbaums ${\displaystyle {\mathsf {3}}}$, der zum neuen Geschwister von ${\displaystyle {\mathsf {N}}}$ wird. Dann muss der Pfad sowohl vor als auch nach der Transformation durch ${\displaystyle {\mathsf {S}}}$ und ${\displaystyle {\mathsf {P}}}$ führen. Da die beiden Knoten aber nur ihre Farben vertauscht haben, ändert sich an der Anzahl der schwarzen Knoten auf dem Pfad nichts.
2. Der Pfad führt durch den neuen Onkel ${\displaystyle {\mathsf {D}}}$ von ${\displaystyle {\mathsf {N}},}$ welcher das (nicht-dir)-Kind des Geschwisters ${\displaystyle {\mathsf {S}}}$ ist. In diesem Fall führte der Pfad vorher durch ${\displaystyle {\mathsf {D}},{\mathsf {S}}}$ und ${\displaystyle {\mathsf {P}}}$. Nach der Transformation führt er aber nur noch durch ${\displaystyle {\mathsf {D}},}$ der von Rot auf Schwarz (die vorige Farbe von ${\displaystyle {\mathsf {S}}}$) umgefärbt wurde, und den Knoten ${\displaystyle {\mathsf {S}},}$ welcher die Farbe von ${\displaystyle {\mathsf {P}}}$ 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 ${\displaystyle {\mathsf {N}}}$ führen, sich um 1 erhöht, und in denen, die nicht durch ${\displaystyle {\mathsf {N}}}$ führen, sich nicht ändert, ist die Forderung S#= wiederhergestellt.

 Fall_L5:
   // Bedingung_L5: S schwarz && D rot
   // Transformation_L5:
   // dir-Rotation um P:
   P->child[!dir] = S->child[dir]; // neuer Elter für 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

Operationen mit ganzen Rot-Schwarz-Bäumen

Die folgenden z​wei Operationen h​aben ganze Rot-Schwarz-Bäume a​ls Ein- u​nd Ausgabeoperanden. Sie gehören n​icht zum Standardsatz u​nd fehlen i​n manchen Implementierungen. Es s​oll aber h​ier gezeigt werden, d​ass auch s​ie mit logarithmischem Aufwand durchgeführt werden können.

Verketten (Join)

Verkettung von 2 Rot-Schwarz-Bäumen

Die Operation JOIN(TL,k,TR) verkettet (konkateniert) (englisch: join oder concat) zwei Rot-Schwarz-Bäume über einen Einzelschlüssel mit logarithmischem Aufwand.[18] Für die Sortierfolge müssen natürlich alle Schlüssel des ersten Baums TL dem Einzelschlüssel k und dieser allen Schlüsseln des zweiten TR vorangehen.[19] Die 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:
Ohne Beschränkung der Allgemeinheit sei der erste Baum nicht niedriger als der zweite, und der zweite habe eine schwarze Wurzel (Knoten ${\displaystyle {\mathsf {H}}}$ in der Abbildung) der Schwarzhöhe ${\displaystyle s}$. Ferner sei dem zweiten Baum sein erstes Element ${\displaystyle {\mathsf {G}}}$ bereits entnommen. Es spielt nachher die Rolle eines „Bindeglieds“.
Man steigt an der rechten Flanke des ersten Baums bis zu einem schwarzen Knoten der Schwarzhöhe ${\displaystyle s}$ hinunter, sein Name sei ${\displaystyle {\mathsf {F}}}$. Der Knoten ${\displaystyle {\mathsf {G}}}$ wird rot gefärbt und zum rechten Kind des Elters ${\displaystyle {\mathsf {E}}}$ von ${\displaystyle {\mathsf {F}}}$ gemacht. Ist ${\displaystyle {\mathsf {E}}}$ schwarz, dann ist der verkettete Baum in Rot-Schwarz-Form und die Verkettung abgeschlossen. Ist ${\displaystyle {\mathsf {E}}}$ jedoch rot, dann ist sein linkes Kind schwarz. Nun lässt sich eine Reparaturschleife anschließen, die zur Wurzel aufsteigend dieselbe Schleifeninvariante hat wie die Operation Einfügen, und ${\displaystyle {\mathsf {G}}}$ ist der Problemknoten der ersten Iterationsstufe.

Massenoperationen

Aufbauend auf der JOIN-Operation können weitere Massen- und Mengenoperationen gebildet werden,[20] die allesamt logarithmische Laufzeit haben, so z. B. die komplementäre Operation des Aufspaltens (englisch: split) eines Baums an einem Pfad.

Die Massenlöschung v​on allen Schlüsseln i​n einem zusammenhängenden Bereich (Intervall) k​ann durch zweimaliges Spalten u​nd einmaliges Verketten geschehen oder, w​enn das kleinste o​der größte Element m​it dabei ist, d​urch einmaliges Spalten. In ähnlicher Weise lässt s​ich ein Intervall m​it logarithmischem Aufwand a​ls Rot-Schwarz-Baum a​us einem Rot-Schwarz-Baum herauspräparieren.

Eine Masseneinfügung k​ann durch einmaliges Spalten u​nd zweimaliges Verketten durchgeführt werden, sofern d​ie Menge a​ls Rot-Schwarz-Baum vorbereitet i​st und i​hre Schlüssel i​n einem Intervall liegen, d​as im Zielbaum n​icht vorkommt.

Mengenoperationen

Im selben Aufsatz wurde gezeigt, dass auch die Mengenoperationen Durchschnitt, Vereinigung und 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. 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 ${\displaystyle {\mathcal {O}}(\log n)}$ mit ${\displaystyle n}$ 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 ${\displaystyle h}$ 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 ${\displaystyle n}$ Elementen nie eine gewisse Höhe (im Falle des Rot-Schwarz-Baumes ${\displaystyle 2\log _{2}(n\!+\!2)\!\!-\!\!2}$) überschreitet, so hat man bewiesen, dass die oben genannten Operationen im schlechtesten Fall logarithmische Kosten haben.

Rot-Schwarz-Bäume mit kleinster Knotenzahl zu gegebener Höhe

Rot-Schwarz-Bäume RB_h der Höhen h=1,2,3,4,5,
jeweils mit minimaler Knotenzahl 1,2,4,6 resp. 10.

Zu ${\displaystyle h\geq 0}$ gibt es einen Rot-Schwarz-Baum der Höhe ${\displaystyle h}$ mit

${\displaystyle m_{h}=2^{\lfloor (h+1)/2\rfloor }+2^{\lfloor h/2\rfloor }-2}$

Knoten, und keinen mit weniger (${\displaystyle \lfloor \,\rfloor }$ steht für die Gauß-Klammer).[Anm. 11]

Beweis

Damit ein Rot-Schwarz-Baum einer bestimmten Höhe ${\displaystyle h}$ 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.[21] 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 vollständige Binärbäume mit ausschließlich schwarzen Knoten.

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

Bei einem Minimalbaum (RB_h in der Abbildung) der Höhe ${\displaystyle h>1}$ 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 ${\displaystyle h\!\!-\!\!1}$ mit ${\displaystyle m_{h-1}}$ Knoten und der Schwarzhöhe ${\displaystyle s:=\lfloor (h\!\!-\!\!1)/2\rfloor }$; der niedrigere ist ein vollständiger Binärbaum mit Höhe = Schwarzhöhe ${\displaystyle s,}$ hat also ${\displaystyle 2^{s}\!\!-\!\!1=2^{\lfloor (h-1)/2\rfloor }\!\!-\!\!1}$ Knoten. Damit ist rekursiv

	${\displaystyle m_{h}}$	${\displaystyle =}$	${\displaystyle (m_{h-1})}$		${\displaystyle +}$	${\displaystyle (1)}$	${\displaystyle +}$	${\displaystyle (2^{\lfloor (h-1)/2\rfloor }-1)}$
			(großer Kindbaum)			(Wurzel)		(kleiner Kindbaum)
woraus man
	${\displaystyle m_{h}}$	${\displaystyle =}$	${\displaystyle (2^{\lfloor h/2\rfloor }+2^{\lfloor (h-1)/2\rfloor }-2)}$				${\displaystyle +}$	${\displaystyle 2^{\lfloor (h-1)/2\rfloor }}$
		${\displaystyle =}$	${\displaystyle 2^{\lfloor h/2\rfloor }+2^{\lfloor (h+1)/2\rfloor }-2}$

ausrechnet.  ■

Der Graph der Funktion ${\displaystyle m_{h}}$ ist konvex nach unten und stückweise linear mit den Ecken an den Punkten ${\displaystyle (h=2k\;|\;m_{h}=2^{k+1}\!\!-\!\!2)}$ mit ${\displaystyle k\in \mathbb {N} .}$ Ferner ist ${\displaystyle m_{h}=}$ A027383(h–1) für ${\displaystyle h\geq 1}$ mit der Folge A027383 in OEIS.

Umformung

Wegen ${\displaystyle 3>2^{\tfrac {3}{2}}}$ (eine Folge von ${\displaystyle 9>8}$) haben wir für ungerades ${\displaystyle h}$ die Ungleichung

${\displaystyle m_{h}=3\cdot 2^{\tfrac {h-1}{2}}-2=3\cdot 2^{-{\tfrac {3}{2}}}\cdot 2^{\tfrac {h+2}{2}}-2>2\cdot 2^{\tfrac {h}{2}}-2,}$

so dass sich für alle (geraden wie ungeraden) ${\displaystyle h}$

${\displaystyle m_{h}\geq 2\cdot 2^{\tfrac {h}{2}}-2}$

ergibt. Da ${\displaystyle m_{h}}$ die kleinste Knotenzahl ${\displaystyle n}$ für alle Rot-Schwarz-Bäume der Höhe ${\displaystyle h}$ ist, gilt

${\displaystyle 2\cdot 2^{\tfrac {h}{2}}-2\leq m_{h}\leq n,}$

so dass ${\displaystyle h}$ sich im Intervall

	${\displaystyle \log _{2}(n+1)}$	${\displaystyle \leq h\leq }$	${\displaystyle 2\log _{2}(n+2)-2=2\log _{2}(n/2+1)}$	${\displaystyle {\bigl [}<2\log _{2}(n+1)\;{\bigr ]}}$
	(vollständiger Binärbaum)		(minimaler RB-Baum)

befindet.[22][Anm. 12]

Folgerung

Somit folgt die Behauptung, dass ein Rot-Schwarz-Baum eine maximale Höhe ${\displaystyle h}$ von ${\displaystyle 2\log _{2}(n\!+\!2)\!\!-\!\!2}$ hat und damit die Operationen suchen, einfügen und löschen in logarithmischer Zeit erledigen kann. Drückt man dieses Ergebnis in der O-Notation aus, so ergibt sich für die Kosten der oben genannten Operationen, dass sie alle in ${\displaystyle {\mathcal {O}}(\log n)}$ liegen mit ${\displaystyle n}$ als der Zahl der Schlüssel.[Anm. 13]

Durchschnittliche und amortisierte Laufzeit

Der Rot-Schwarz-Baum bietet amortisiert konstante Rebalancierungskosten[23] u​nd damit a​uch 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 persistent gehalten werden soll, d. h. alle Versionen zugänglich bleiben sollen (s. a. en:Persistent data structure).[8][24]

Anzahlen von Rot-Schwarz-Bäumen

Die Folge A001131${\displaystyle (n\!+\!1)}$ in OEIS gibt in Abhängigkeit von der Knotenzahl ${\displaystyle n}$ die Gesamtzahl der Rot-Schwarz-Bäume, Folge A001137 in OEIS derer mit schwarzer Wurzel und Folge A001138 in OEIS derer mit roter Wurzel.

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 und 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_E2 gefolgt von Transformation_E0, bei den rechten 2 Einfärbungen sind alle vom Typ Transformation_E1.

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,

4 Einfügungen und 1 Löschung

u​nd zwar d​er mit r​oter Wurzel über

4 Einfügungen und 1 Löschung

6 Einfügungen und 3 Löschungen

und d​er mit schwarzer Wurzel über

6 Einfügungen und 3 Löschungen

und d​ies mit d​en oben beschriebenen Algorithmen für Einfügung u​nd Löschung – jeweils b​ei geeignet gewählter Schlüsselfolge, d​ie durch d​en Knoten m​it blauer Kontur angegeben ist.

Verwandtschaft mit 2-3-4-Bäumen

2 Kinder

3 Kinder

3 Kinder

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-Baums (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.[25][26]

Der Rot-Schwarz-Baum des Beispiels dargestellt als 2-3-4-Baum

Umgekehrt k​ann man e​inen 2-3-4-Baum g​anz einfach i​n einen Rot-Schwarz-Baum überführen: Aus e​inem Knoten m​it 2 Datenelementen u​nd 3 Kindzeigern (wie d​er Knoten [NIL,1,6] i​n der Abbildung) w​ird ein schwarzer Knoten (Datenelement) m​it 1 Kindzeiger u​nd einem r​oten Kindknoten (Datenelement), d​er noch 2 Kindzeiger enthält; a​us einem Knoten m​it 3 Datenelementen u​nd 4 Kindzeigern (wie d​ie Knoten [8,13,17] u​nd [22,25,27] i​n der Abbildung) w​ird ein schwarzer Knoten (Datenelement) m​it 2 r​oten Kindknoten (jeweils 1 Datenelement u​nd 2 Kindzeiger).

Darüber hinaus g​ibt es Entsprechungen b​ei den Modifikationsoperationen (Einfügen, Löschen) zwischen Farbwechsel u​nd Rotationen a​uf Seite d​er Rot-Schwarz-Bäume u​nd den Aktionen Spalten (englisch split) u​nd Verschmelzen (englisch fuse) b​ei den 2-3-4-Bäumen.

Im Gegensatz z​u 2-3-4-Bäumen m​uss man b​ei Rot-Schwarz-Bäumen n​icht den »Füllzustand« (Speicherausnutzung, englisch fill factor) d​er Knoten beobachten u​nd verwalten, weshalb letztere a​ls sehr effiziente Art d​er Implementierung d​er 2-3-4-Bäume gelten.[27]

Vergleich mit AVL-Baum

Die Menge d​er AVL-Bäume i​st eine echte Teilmenge i​n der Menge d​er Rot-Schwarz-Bäume. Denn j​eder Binärbaum, d​er das AVL-Kriterium erfüllt, lässt s​ich in e​iner das Rot-Schwarz-Kriterium erfüllenden Weise einfärben.[28][29]

Rot-Schwarz-, aber nicht AVL-Baum

Es g​ibt aber Rot-Schwarz-Bäume, d​ie das AVL-Kriterium n​icht erfüllen. Die nebenstehende Abbildung z​eigt zum Beispiel e​inen Rot-Schwarz-Baum m​it 6 Knoten u​nd der externen Pfadlängensumme 21, während 20 d​ie größte externe Pfadlängensumme b​ei AVL-Bäumen (und zugleich d​ie kleinstmögliche für alle Binärbäume) dieser Knotenzahl ist. Konsequenterweise i​st auch d​ie Worst-Case-Höhe d​es AVL-Baums kleiner a​ls die d​es Rot-Schwarz-Baums, u​nd zwar asymptotisch u​m den Faktor (2 log₂ Φ)⁻¹ ≈ 0,720. Allgemein werden AVL-Bäume a​ls besser balanciert u​nd ihr Suchverhalten a​ls günstiger angesehen.

Die Laufzeiten für a​lle angeführten Operationen unterscheiden s​ich im Mittel u​nd im Worst Case asymptotisch n​ur um e​inen konstanten Faktor, gehören a​lso derselben Komplexitätsklasse an. Der Rot-Schwarz-Baum bietet allerdings amortisiert konstante Einfüge- u​nd Löschkosten (jeweils n​ur Rebalancierung – ohne Navigation). Beim AVL-Baum s​ind nur d​ie Einfügekosten amortisiert, d​ie Löschkosten immerhin im Mittel konstant.

Realistische Anwendungssituationen m​it Performancedaten u​nd -vergleichen – a​uch mit weiteren Suchalgorithmen u​nd Spielarten d​er Datenstrukturen – finden s​ich bei Ben Pfaff. Seine Ergebnisse zeigen i​n 79 Messungen u​nter anderem d​ie sehr große Ähnlichkeit v​on AVL-Bäumen (AVL) u​nd Rot-Schwarz-Bäumen (RB) m​it Laufzeitverhältnissen ^AVL⁄_RB zwischen 0,677 u​nd 1,077 b​ei einem Median v​on ≈0,947 u​nd einem geometrischen Mittelwert v​on ≈0,910.

Der Speicherplatzbedarf i​st praktisch identisch: 1 Bit für d​as Rot-Schwarz-Attribut gegenüber 2 Bits[Anm. 14] für d​en AVL-Balance-Faktor. Während d​ie Balance-Faktoren e​ines AVL-Baums direkt v​on seiner (graphentheoretischen) Gestalt abhängen, s​ind bei Rot-Schwarz-Bäumen derselben Gestalt – außer b​ei den Minimalbäumen gerader Höhe – unterschiedliche Einfärbungen möglich (s. Abschnitt Anzahlen v​on Rot-Schwarz-Bäumen). Dabei wirken s​ich die Unterschiede d​er Einfärbungen n​ur auf d​ie Modifikations- u​nd nicht a​uf die Navigationsoperationen aus. Des Weiteren k​ann jede mögliche Gestalt e​ines AVL-Baums d​urch gezielte Einfügungen a​uch hergestellt werden. Bezogen a​uf die Baumform g​ilt dies a​uch für Rot-Schwarz-Bäume; e​s gibt a​ber Baumformen, b​ei denen durchaus regelkonforme Einfärbungen i​n einem reinen Einfügeszenario n​icht 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.[30] Diese »Top-Down-Strategie«[31] ist bspw. für nebenläufige und persistente Programmierung interessant.[Anm. 15][32]

So bleibt b​eim Einfügen d​er frisch eingefügte Knoten rot. Das bedeutet, d​ass eine zugehörige Suchfunktion i​m Abstieg d​en Baum entlang d​em betroffenen Pfad (in logarithmischer Zeit) s​o vorbereiten kann, d​ass das endgültige Einfügen unmittelbar b​ei einem schwarzen Elter i​n Form e​ines roten Knotens geschehen o​der eben (nach gfl. Inspektion d​es Elters) a​uch unterbleiben kann. Genauso k​ann beim Löschen e​ine (andere) Suchfunktion d​en Baum i​m Abstieg s​o vorbereiten, d​ass der z​u löschende Knoten r​ot ist. In beiden Fällen bleibt d​er Baum sowohl b​eim Durchführen w​ie beim Unterlassen d​er Modifikation e​in gültiger Rot-Schwarz-Baum, e​iner Modifikation, d​ie beim Einfügen n​ur aus d​em Setzen e​ines einzigen Zeigers besteht u​nd beim Löschen n​ur geringfügig komplizierter ist. Demgegenüber g​ibt es b​eim AVL-Baum Baumformen, b​ei denen d​ie Entscheidung betreffend d​en Vollzug d​er Modifikation n​icht mit derart geringer Implikation o​ffen gehalten werden kann.

Verwendung von Rot-Schwarz-Bäumen

Im Java Development Kit s​ind die Klassen TreeSet[33] u​nd TreeMap[34] a​ls Rot-Schwarz-Bäume implementiert. Sie stellen geordnete Mengen bzw. geordnete Dictionarys z​ur Verfügung.

Weitere Bäume

• 2-3-4-Baum
• AVL-Baum
• B-Baum
• Heap (Datenstruktur)
• Suchbaum

Literatur

• Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Boston 2004, ftp.gnu.org (PDF gzip; 1662 kB; abgerufen am 13. Januar 2019).
• Ben Pfaff: Performance Analysis of BSTs in System Software. Stanford University, 2004, stanford.edu (PDF; 316 kB).
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7, S. 273–301.
• Robert Sedgewick: Algorithmen in C++. Addison-Wesley, 1992, ISBN 3-89319-462-2, S. 260–270 (englisch).
• Robert Sedgewick, Kevin Wayne: 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.
• Kurt Mehlhorn: Datenstrukturen und effiziente Algorithmen. Teubner Stuttgart 1988, ISBN 3-519-12255-3.
• Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-77977-3, doi:10.1007/978-3-540-77978-0.
• Roger Whitney (San Diego State University): CS 660: Red–Black tree notes
• Mathworld: Red–Black Tree

Weblinks

• Java-Applet zur Arbeitsweise eines Rot-Schwarz-Baumes
• Semesterarbeit zum Thema Rot-Schwarz-Bäume

Einzelnachweise

1. Rudolf Bayer: Symmetric Binary B-Trees. Data Structure and Maintenance Algorithms. In: Acta Informatica. 1, 1972, S. 290–306. doi:10.1007/BF00289509.
2. Leo J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. In: IEEE Computer Society (Hrsg.): Proceedings of the 19th Annual Symposium on Foundations of Computer Science. 1978, S. 8–21.
3. Der Text folgt Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. Zu anderen Varianten der Forderungen s. die Anmerkung NIL-Knoten.
4. bei Ben Pfaff non-branching node
5. Bei Ben Pfaff ist die Schwarzhöhe eines Knotens die einheitliche Anzahl schwarzer Knoten auf allen Pfaden zu den Pfadenden im von ihm gewurzelten Teilbaum.
6. Mehlhorn 2008 S. 155 färbt die Kanten rot/schwarz und zählt als Schwarztiefe (englisch black depth) eines Knotens die Zahl der schwarzen Kanten von ihm zur Wurzel.
7. Einige Autoren fordern noch, dass die Wurzel des Baums schwarz zu färben sei. Nicht jedoch z. B. Mehlhorn 2008 und Sedgewick. Tatsächlich ist diese Forderung ohne mathematische Bedeutung und stört die Rekursivität. Denn ist die Wurzel rot, so müssen ihre Kinder gemäß Forderung !RR schwarz sein, und bei ihrer Umfärbung in schwarz wird keine der anderen Forderungen verletzt. 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 Elterknoten voraussetzen kann.
8. 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 (cs.cmu.edu)
9. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge MA 2001, ISBN 0-262-03293-7.
10. Die Implementierung kommt auf diese Weise (wie auch Ben Pfaff – zumindest konzeptionell) ohne einen bei den Knoten gespeicherten Elterzeiger aus.
    Zur Größe eines solchen Stapels s. Stapelgröße.
    Werden allerdings mehrere Zugriffspfade zum selben Suchbaum benötigt, dann kann die Implementierung mit Elterzeiger bessere Laufzeiten ergeben als die Wiederholung von Suchvorgängen.
11. Ben Pfaff bringt außer der Variante des Textes auch eine Variante mit einem ersten eingefügten Knoten schwarzer Farbe.
12. Diese Aufteilung findet sich u. a. bei Ben Pfaff.
13. Eine andere Möglichkeit ist, den Schleifenrumpf der do while-Schleife in zwei Versionen hinzuschreiben, in einer für die Kindesrichtung links und in einer für rechts (so bspw. Ben Pfaff).
14. Für die Vorteile der iterativen Programmierung hinsichtlich Platz und Zeit gegenüber einer rekursiven Programmierung s. a. Binärer Suchbaum#Iterative Programmierung. Darüber hinaus erzwingt erstere eine genauere Beachtung der Knoteneigenschaften.
15. Diese Vorgehensweise wurde zum ersten Mal von T. Hibbard in 1962 vorgeschlagen, zitiert nach Robert Sedgewick, Kevin Wayne: Algorithms Fourth Edition. Pearson Education, 2011, ISBN 978-0-321-57351-3, p. 410 (englisch, abgerufen am 25. März 2018)
16. Die Aufteilung entspricht Roger Whitney.
17. Auf eine andere Aufteilung (der Bedingungen) der Fälle, aber im Ergebnis ebenfalls auf die Gesamtzahl 6, kommt University of Science and Technology of China (zitiert nach stackoverflow.com).
18. Robert Endre Tarjan: 4. Search Trees 5. Linking and Cutting Trees. In: SIAM (= Data structures and network algorithms). 1983, ISBN 978-0-89871-187-5, S. 45–70, doi:10.1137/1.9781611970265.ch5.
19. Donald E. Knuth: The Art of Computer Programming, Band 3, Sorting and Searching, 2. Auflage, Addison-Wesley, 1998, S. 474
20. Guy Edward Blelloch, Daniel Ferizovic, Yihan Sun: Just Join for Parallel Ordered Sets. Hrsg.: ACM (= Symposium on Parallel Algorithms and Architectures, Proc. of 28th ACM Symp. Parallel Algorithms and Architectures (SPAA 2016)). 2016, ISBN 978-1-4503-4210-0, S. 253–264, doi:10.1145/2935764.2935768, arxiv:1602.02120.
21. Sedgewick 2011 S. 444 Proof sketch
22. Gleichheit am oberen Rand gilt für minimale RB-Bäume RB_2k gerader Baumhöhe ${\displaystyle h=2\cdot k}$ mit ${\displaystyle n=2\cdot 2^{k}-2}$ Knoten und nur für diese. Damit ist die Ungleichung geringfügig genauer als das weitverbreitete ${\displaystyle h<2\log _{2}(n+1),}$ z. B. in Cormen S. 264.
23. Mehlhorn und Sanders widmen dem Thema in 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 O(n).“

    In den Kontext der Rot-Schwarz-Bäume übersetzt heißt das:

    „Für eine beliebige Folge von ${\displaystyle n}$ Einfüge- und Löschoperationen in einen anfänglich leeren Rot-Schwarz-Baum ist die Anzahl der Farbwechsel und Rotationen in ${\displaystyle {\mathcal {O}}(n)}$.“

    Damit ist der Aufwand pro Operation in einer solchen Sequenz in ${\displaystyle {\mathcal {O}}(1),}$ also amortisiert konstant. Im Beweis, der für (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.
24. Lightweight Java implementation of Persistent Red-Black Trees
25. Mehlhorn 1988 S. 193
26. 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 englisch 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. Robert Sedgewick. Left-leaning Red–Black Trees und PDF).
27. Mehlhorn 1988 S. 187
28. Paul E. Black: Red-black tree. In: Dictionary of Algorithms and Data Structures. National Institute of Standards and Technology, 13. April 2015, abgerufen am 2. Juli 2016 (englisch).
29. s. „One should be able to color any AVL tree, without restructuring or rotation, to transform it into a Red-Black tree.“ Junghyun Chae in AVL Trees vs. Red-Black Trees? abgerufen am 14. Oktober 2015 und Beweis in AVL-Baum#VergleichRB.
30. Red Black Trees. In: eternallyconfuzzled.com. Abgerufen am 14. Oktober 2015. (Eternally Confuzzled)
31. Mehlhorn 1988 S. 197–198.
32. s. a. Comparison of Binary Search Trees abgerufen am 14. Oktober 2015; oder Paul Callahan in AVL Trees vs. Red-Black Trees? abgerufen am 14. Oktober 2015
33. Java Class TreeSet auf docs.oracle.com
34. Java Class TreeMap auf docs.oracle.com

Anmerkungen

1. Diese Abschätzung ist scharf (s. Abschnitt Höhenbeweis) und für ${\displaystyle n>0}$ wegen

   ${\displaystyle 2\log _{2}(n+2)-2=2\log _{2}(n/2+1)<2\log _{2}(n+1)}$

   marginal genauer als das vielzitierte

   ${\displaystyle 2\log _{2}(n+1)}$.

2. 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 ${\displaystyle n}$ Schlüssel tragenden Knoten braucht man ${\displaystyle n\!+\!1}$ NIL-Knoten, womit sich der Rot-Schwarz-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.
3. Dabei ist dir == LEFT       ${\displaystyle \Longleftrightarrow }$       Schlüssel von ${\displaystyle {\mathsf {N}}}$ < Schlüssel von ${\displaystyle {\mathsf {P}}}$.
   S. a. Binärer Suchbaum#Suchen, wenn Duplikate zulässig.
4. Die Kurzschreibweise mit dem Pfeil -> ist erklärt im Artikel Verbund (Datentyp).
5. Man beachte die in der Programmiersprache C festgelegte Art der Auswertung der

   	Disjunktion:	(X == NIL)
   		|| (X->color == BLACK)
   bzw. der
   	Konjunktion:	(X != NIL)
   		&& (X->color == RED)

   die im Fall X == NIL die zweite Bedingung X->color == BLACK resp. X->color == RED nicht auswertet, sondern sofort zum else-Zweig verzweigt. Im Beispielcode sind die entsprechenden Zeilen gelb hinterlegt.
   Zusätzliche Bemerkung:
   Die Schwarzhöhe 0 kommt nur in der ersten Iterationsstufe der Reparaturschleife vor; bei den höheren Iterationsstufen ist die Schwarzhöhe aller besuchten Knoten positiv, somit auch (X != NIL) – und dieser Teil der Abfrage kann weggelassen werden.
   Weiß man andererseits, dass die Schwarzhöhe eines Knotens 0 ist, dann kann er, wenn er existiert nur rot sein. Wenn nun die erste Iteration aus der Schleife herausgezogen wird, dann kann sich die Abfrage dort auf (X != NIL) beschränken, wogegen bei den höheren Iterationsstufen nur auf color abgefragt werden muss.
6. In der ersten Iterationsstufe ist der Teilbaum ${\displaystyle {\mathsf {3}}}$ 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.
7. Wegen der Gleichsetzungen LEFT ≡ 0 und RIGHT ≡ 1 spiegelt die logische Negation

   nicht-dir   ≡   !dir   ≡   (1−dir)

   die Richtung LEFT ${\displaystyle \longleftrightarrow }$ RIGHT. Dabei ist dir = (R == P->right) die Kindesrichtung von ${\displaystyle {\mathsf {R}}}$.
   Im Kontext der Farben spricht man bei Zuweisungen à la RED :≡ !BLACK und BLACK :≡ !RED von »Invertierung«.
8. Um der Kürze der Aufschreibung willen wird im Beispielcode einige Male goto verwendet. Es ist leicht, dies durch Verdoppelung des Codes zu vermeiden.
9. Zu Beginn jedes Iterationsschritts hat das Geschwister ${\displaystyle {\mathsf {S}}}$ die Schwarzhöhe ${\displaystyle j.}$
10. Wenn die Knoten mit Elterzeiger implementiert werden, dann ist der Elterzeiger des Knotens ${\displaystyle {\mathsf {C}}}$ in allen Iterationen anzupassen, da die Schwarzhöhe von ${\displaystyle {\mathsf {C}}}$ auch in der ersten Iteration ≥ 1 ist.
11. Diese Minimalbäume spielen bei den Rot-Schwarz-Bäumen eine ähnliche Rolle wie die Fibonacci-Bäume bei den AVL-Bäumen.
12. Diese RB-Bäume gestatten darüber hinaus nur eine einzige Einfärbung, sind aber nicht die einzigen RB-Bäume mit dieser Eigenschaft.
    Zur Höhe ${\displaystyle h}$ gibt es ${\displaystyle 2^{h-1}}$ Formen von Minimalbäumen, da die Position des längsten Pfades der Position eines externen Blattes des vollständigen Binärbaums der Höhe ${\displaystyle h\!\!-\!\!1}$ entspricht und durch diese Position die Lage aller anderen Knoten bestimmt ist. (Die Abbildung zeigt die äußerste linke Position.)
13. 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.
    Die folgende Tabelle gibt zu jeder Knotenzahl ${\displaystyle n}$ eine Höhenangabe ${\displaystyle h}$ zurück, die von einem Rot-Schwarz-Baum mit ${\displaystyle \leq n}$ Elementen nicht überschritten wird. Gängig sind Hauptspeicher mit 32 Bit und 64 Bit breiten virtuellen 8-Bit-Byte-Adressen. Da in einem 32-Bit-Adressraum maximal ${\displaystyle 2^{32}}$ Bytes untergebracht werden können und ein Knoten mindestens 2 Kind-Zeiger à je 4 Bytes benötigt, kann bei Benutzerdaten (Schlüssel + Wert) von ${\displaystyle b}$ Bytes pro Knoten ein Baum mit maximal ${\displaystyle n=2^{32}/(2\cdot 4\!+\!b)}$ Knoten untergebracht werden; bei ${\displaystyle b=3}$ sind das ${\displaystyle n=390451572.}$ Wie die Tabelle zeigt, kann im 32-Bit-Adressraum die Höhe ${\displaystyle h=55}$ durch einen Rot-Schwarz-Baum unmöglich überschritten werden.
    Für einen Adressraum mit 8 Byte breiten Adressen und ${\displaystyle b=1}$ Byte Benutzerdaten hat man ${\displaystyle n\leq 2^{64}/(2\cdot 8\!+\!b)}$${\displaystyle =1085102592571150095,}$ so dass ${\displaystyle h\leq 117}$ bleibt und beim Einsatz von ${\displaystyle 8h=8\cdot 117=936}$ Bytes für den Elter-Stapel dieser nicht überlaufen kann.

    Umfang von Rot-Schwarz-Bäumen

    	Anzahl Knoten ${\displaystyle n\leq }$	Baumhöhe ${\displaystyle h\leq }$	Nutzlänge ${\displaystyle b\leq }$
    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
    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 im Text ist ${\displaystyle n=m_{h+1}-1,}$ 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

    ${\displaystyle b={\begin{cases}\\\\\end{cases}}}$	${\displaystyle 2^{32}/n-2\cdot 4}$		im 32-Bit-Adressraum (4 Bytes/Adresse)
    	${\displaystyle 2^{64}/n-2\cdot 8}$		im 64-Bit-Adressraum (8 Bytes/Adresse)

    Bytes umfassen. Fazit Ist der Stapelspeicher struct RBnode* Parents[] für die Elter-Zeiger bei einem 32-Bit-Adressraum auf wenigstens ${\displaystyle h=54}$ Einträge mit insgesamt ${\displaystyle 4h=4\cdot 54=216}$ Bytes ausgelegt, so kann er unmöglich überlaufen.
    Dasselbe gilt bei einem 64-Bit-Adressraum für ${\displaystyle h=117}$ und einem Elter-Stapel der Größe ${\displaystyle 8h=8\cdot 117=936}$ Bytes.
    Bevor nämlich in beiden Fällen der Elter-Stapel überläuft, ist der Adressraum schon geplatzt.
    Ben Pfaff hat #define RB_MAX_HEIGHT 128.
14. oder auch nur 1 Bit (s. AVL-Implementierung)
15. Die Sperren, die bei einem der Veränderung unterworfenen Baum der Erhaltung seiner 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 vermieden werden.