199 Rot-Schwarz-Baum

Rot-Schwarz-Baum

Rot-Schwarz-Baum
Komplexität
bei Elementen
Platz
Operation im Mittel Worst Case
Suchen
Querschritt
Min, Max
Einfügen
Löschen
Platz- und Zeit-Komplexitäten

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 Werte 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 werden durch drei Forderungen erreicht, die zusammen garantieren, dass ein Rot-Schwarz-Baum immer balanciert ist, wodurch die Höhe eines Rot-Schwarz-Baumes mit Schlüsseln (Elementen) nie größer als wird.[3] Somit können die wichtigsten Operationen in Suchbäumen – Suchen, Einfügen und Löschen – garantiert in (s. Landau-Symbole) ausgeführt werden.

Definition

Zusätzlich zu den Eigenschaften des binären Suchbaums hat jeder Knoten des Rot-Schwarz-Baums ein weiteres Attribut, genannt Farbe, das zwei Werte annehmen kann, genannt rot (engl. RED) und schwarz (engl. BLACK). Diese Einfärbung hat die drei folgenden Forderungen zu erfüllen:[4]

Forderung !RR (Nicht Rot Rot): Ist ein Knoten rot, so sind beide Kinder schwarz.
Forderung S#= (Schwarz Zahl Gleich): Jeder Pfad von einem gegebenen Knoten zu einem seiner Nachfahren mit Ausgangsgrad ≤1[5] enthält die gleiche Anzahl schwarzer Knoten.
Rot-Schwarz-Baum der Höhe 4 und der Schwarztiefe 2

Datenstruktur

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 ggf. reparieren. So erweitert wird die Datenstruktur zu einem Abstrakten Datentyp (ADT). Bei Suchbäumen gibt es im Englischen dafür auch die Charakterisierung als self-balancing tree.

Weitere Definitionen und Folgerungen

Die auf allen Pfaden von Wurzel zu Blatt gleiche Anzahl schwarzer Knoten wird die Schwarztiefe[6] (engl. häufig black-height) des Baums genannt. Als Schwarzhöhe eines Knotens bezeichnen wir in diesem Artikel die einheitliche Anzahl schwarzer Knoten auf allen Pfaden zu den Blättern im von ihm gewurzelten Teilbaum. Nach dieser Definition ist ein Knoten der Schwarzhöhe 0 ein rotes internes Blatt, wie bspw. der Knoten in der Abb., wogegen die Knoten und die Schwarzhöhe 1 haben.

Durch die zwei Forderungen[7] wird die wichtigste Eigenschaft von Rot-Schwarz-Bäumen sichergestellt:

Wegen der Forderung !RR kann es auf keinem Pfad von der Wurzel zu einem Blatt mehr rote als schwarze Knoten geben, während auf dem kürzesten Pfad im Extremfall nur schwarze Knoten vorhanden sind. Da die Forderung S#= jedoch festlegt, dass die Anzahl der schwarzen Knoten auf allen Pfaden gleich sein muss, kann der Pfad, auf dem sich jeweils ein roter mit einem schwarzen Knoten abwechselt, maximal doppelt so lang sein wie ein Pfad, auf dem nur schwarze Knoten liegen. Hierdurch ist ein Rot-Schwarz-Baum immer gut genug balanciert – auf jeden Fall so gut, dass das Verhältnis zwischen der Höhe des Baums und dem Logarithmus der Knotenzahl 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 asymptotisch kleinerer maximaler Pfadlänge (= Höhe) .

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.

Anmerkung
Dieser Artikel nimmt die im Artikel Binärer Suchbaum in dessen Abb. 1A aufgezeigte und bei vielen Baumstrukturen übliche Sichtweise ein, bei der die Knoten die Schlüssel tragen („knotenorientierte Speicherung“), unabhängig davon, ob sie interne Knoten oder (interne) Blätter sind.[8]
Stark verbreitet in der Literatur über Rot-Schwarz-Bäume ist die im Artikel Binärer Suchbaum in dessen Abb. 1B aufgezeigte Sichtweise, bei der die internen Knoten die Schlüssel tragen (ebenfalls „knotenorientierte Speicherung“), aber die Blätter als extern angesehen werden und die (randlosen) Intervalle zwischen den Schlüsseln markieren. In dieser Sichtweise der Rot-Schwarz-Bäume haben die Schlüssel tragenden Knoten immer genau zwei Kinder, und die schlüssellosen (externen) Blätter, genannt „NIL-Knoten“, tragen die Farbe schwarz. Da bei dieser Sichtweise ein Pfad von der Wurzel bis zu einem NIL-Knoten läuft, ist klar, dass außer der Wurzel jeder schwarze Knoten ein Geschwister hat. Das gilt bei der gewählten, anderen Sichtweise genauso, ist aber nicht so offensichtlich.
Der Nutzeffekt dieser Betrachtungsweise ist bezogen auf das Verständnis der Sachverhalte marginal und bezogen auf die Implementierung nachteilig.[9]

Navigationsoperationen

Die Navigationsoperationen, das sind die 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ä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.

Das Suchen eines Elements anhand seines Schlüssels ist die wichtigste unter den Navigationsoperationen. Die Höhen-Balancierung des Rot-Schwarz-Baums versucht, auf diese Operation hin zu optimieren. Sie ermöglicht eine Art „direkten Zugriff“ (im Gegensatz zum sequentiellen Zugriff der Traversierung). Sie wird in der Regel als vorausgehende Operation bei den Modifikationsoperationen (Einfügen oder Löschen) eingesetzt.

Das Suchen setzt eine totale Quasiordnung auf der Menge der Schlüssel voraus, die am flexibelsten durch eine Vergleichsfunktion realisiert wird.

Operation Einfügen

Die ersten Aktionen beim Einfügen eines neuen Elements in den Rot-Schwarz-Baum sind dieselben wie bei einem binären Suchbaum: Der Zeiger zum neuen Knoten ersetzt einen Nullzeiger, der entweder für die Wurzel steht, falls der Baum leer ist, oder für den Zeiger zum linken bzw. rechten Kindknoten bei einem Schlüssel tragenden Knoten , der in dieser Richtung kein Kind hat.

Im unten stehenden Beispielcode wird angenommen, dass diese Richtung – die das letzte Ungleichergebnis einer Suchfunktion (nach dem zu gehörigen Schlüssel) reflektiert – in einer Variablen d ∈ {UNDEFINED,LEFT,RIGHT}[10] übergeben wird. Ferner wird angenommen, dass diese Suchfunktion den Stapel struct node* Parents[] der Vorfahren von gebildet hat. Wenn der Baum nicht leer ist, ist der Zeiger Parents[0] gleich dem Zeiger auf den Wurzelknoten.

Der Knoten wird zunächst rot gefärbt, damit die Schwarztiefe des Baumes erhalten bleibt.

Die darauf folgenden Aktionen überprüfen, ob die Rot-Schwarz-Eigenschaften im Baum eingehalten sind und stellen sie ggf. wieder her. Letztere Reparatur wird als „Rebalancierung“ (engl. rebalancing) bezeichnet.

Der neue Knoten werde (wie engl. node) genannt, sein Elter (wie engl. parent), der Großelter (wie engl. grandparent) und der Onkel mit (wie engl. uncle). ist beim ersten Iterationsschritt der gerade betrachtete „Problemknoten“.

Der Kopf der Funktion RBinsert1 zum Einfügen eines Knotens nach einer vorher erfolgten und nicht erfolgreichen Suchoperation könnte wie folgt aussehen:

 void RBinsert1(
   RBtree* T,                // -> Rot-Schwarz-Baum
   struct node*   Parents[], // Liste der -> Vorfahren
   struct node** pParents,   // ->-> Nachbarknoten (wird zum Elterknoten von N)
   byte d,                   // (Kindes-)Richtung der Einfügung  {LEFT, RIGHT}
   struct node* N)           // -> einzufügender Knoten
  {
   struct node* G, U;

   N->color = RED;
   if (pParents >= &Parents[0]) // N ist nicht die neue Wurzel
    {
     P = *pParents;   // -> Nachbarknoten (wird zum Elterknoten von N)
     P->child[d] = N; // neuer Knoten als d-Kind von P

     do // Beginn der (do while)-Schleife
      {
       P = *pParents; // -> Elterknoten von N

Einfügen: Schleifeninvariante:

  1. Zu Beginn jedes Iterationsschritts ist der Problemknoten rot. (Er hat im Diagramm des resp. Falles eine blaue Kontur.)
  2. ist nicht die Wurzel und  != NULL.
  3. Die Forderung !RR »Kein roter Knoten hat ein rotes Kind« gilt im ganzen Baum – mit der einzigen möglichen Ausnahme beim Paar .
    Gilt sie auch dort, dann ist der Baum in Rot-Schwarz-Form.
  4. Die Forderung S#= »Die Anzahl der schwarzen Knoten von jedem beliebigen Knoten zu einem Blatt ist auf allen Pfaden gleich« gilt für den ganzen Baum.
  5. In den Diagrammen stellen die kleinen nummerierten Dreiecke (Rot-Schwarz-)Teilbäume dar. Diese Teilbäume haben alle dieselbe Schwarztiefe, die auch 0 sein kann.
Bedingung Fall
Rota-
tion
Zuwei-
sung
Ergebnis
Test
x x
RedOrBlackNode.svg 0 RedOrBlackNode.svg
RedNode.svg BlackNode.svg 1 RedNode.svg BlackNode.svg
RedNode.svg RedNode.svg 2 RedNode.svg BlackNode.svg
RedNode.svg RedNode.svg BlackNode.svg RedNode.svg 3 := RedNode.svg ? ? ? 0
RedNode.svg RedNode.svg BlackNode.svg BlackNode.svg i 4 := RedNode.svg RedNode.svg BlackNode.svg BlackNode.svg o 4
RedNode.svg RedNode.svg BlackNode.svg BlackNode.svg o 5 RedNode.svg BlackNode.svg RedNode.svg BlackNode.svg
Einfügen: Zusammenschau der Fälle

Einfügen: Zusammenschau der Fälle

Die möglichen Konstellationen lassen sich in sechs Fälle aufteilen, 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 Reparatur des Baumes führen.

In der nebenstehenden Tabelle wird ein Fall durch eine Zeile repräsentiert, die

  1. die Bedingung, d. i. die Konstellation, die den Fall definiert,
  2. die Fallnummer,
  3. die Konstellation nach Transformation und ggf. Zuweisung in der Spaltengruppe Ergebnis

enthält. Eine Konstellation besteht aus fünf Gegebenheiten, und zwar aus den vier Farben der Knoten und . Manche Fälle benötigen darüber hinaus eine fünfte Angabe x zur Kindesrichtung von , und zwar steht o (wie engl. outer) für eine Rechts-Rechts- oder Links-Links-Kindesrichtung von zu zu und i (wie engl. inner) für Rechts-Links oder Links-Rechts. Eine Zelle ist leer gelassen, wenn es bei dem Fall auf die entsprechende Angabe nicht ankommt.

Die Konstellationen in der Gruppe Bedingung genügen der Schleifeninvariante, und ihre logische Summe schöpft diese genau aus.

Die Transformation, deren Fallnummer in der Spalte Fall → verlinkt ist, transformiert die Eingabe-Konstellation (linke Seite im zum Fall gehörigen Diagramm) in eine andere auf der rechten Seite des Diagramms. Steht ein „–“ 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 für den Problemknoten in der Spalte Zuweisung, auch die neuen Knoten sowie die Angabe x zur Kindesrichtung von definiert. Die Gruppe Ergebnis zeigt dann die Konstellation nach der Zuweisung.

In der Spalte → Test kommt der Eintrag „0“ nur bei der Transformation_E3 vor und bedeutet u. U. einen neuen Iterationsschritt. Dieser beginnt mit dem Test auf Bedingung_E0 in der do while-Anweisung – zwei Ebenen höher. Da die Anzahl der Ebenen mit der Höhe übereinstimmt, können maximal Iterationen vorkommen. Nun ist der Aufwand für eine Iteration beschränkt (d. h. in ) und damit der für die gesamte Einfügeoperation in . Im Mittel ist der Aufwand gemäß Abschnitt #Durchschnittliche und amortisierte Laufzeit sogar konstant.

Bei einem Eintrag in der Spalte Rotation ist eine Rotation an der Transformation beteiligt. Man entnimmt der Tabelle sofort, dass bei einer Einfügung maximal 2 Rotationen vorkommen. Denn nach einer Rotation (Transformation_E4 und Transformation_E5) gibt es keine weitere Iteration – die Rotationen befinden sich endrekursiv am Ende der letzten Iteration.

Im folgenden Beispielcode entscheidet die Kindesrichtung von insbesondere über die nachfolgenden Rotationsrichtungen. Hat dieselbe Kindesrichtung wie , dann ist die Variable „x“ (in der Zusammenschau) auf „o“ für „außen“, sonst auf „i“ für „innen“ zu setzen.[11] Die Diagramme bei den Fällen zeigen nur eine Kindesrichtung, und zwar ist immer links von .

Jeder Fall wird unter seiner Nummer erläutert und einschließlich Test (if-Abfragen) und Transformation durch ein Stück C-Code genau beschrieben.[12]

Einfügen Fall 1: Der Elter des Problemknotens ist schwarz. (Damit gilt die Forderung !RR im ganzen Baum.)

Nach Voraussetzung (Schleifeninvariante) ist die Anzahl der schwarzen Knoten (Schwarztiefe) auf allen Pfaden dieselbe. Alle Paare Elter→Knoten erfüllen die Forderung !RR. Damit ist der Baum (ohne weitere Aktion) schon in Rot-Schwarz-Form.

       // Bedingung_E1
       if (P->color == BLACK)
         // Transformation_E1:
         return; // Einfügung fertiggestellt

Einfügen Fall 2: Der Elter des Problemknotens ist rot. Der Elter ist gleichzeitig die Wurzel des Baums.

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

       if (--pParents < &Parents[0]) // Bedingung_E2
        {
         // Der Elter P von N ist die Wurzel des Baums
         // Transformation_E2:
         P->color = BLACK;
         // Da P ein roter Knoten war,
         // erhöht sich die Schwarztiefe des Baumes um 1.
         return; // Einfügung fertiggestellt
        }

Einfügen Fall 3: Der Elter ist nicht die Wurzel, so dass der Großelter existiert, der mindestens ein Kind, den Onkel , hat. Sowohl der Onkel als auch der Elter des Problemknotens ist rot.

Einfügen Fall 3

Die Umfärbung von und in schwarz und von in rot stellt die Forderung !RR im Teilbaum mit Wurzel wieder her. Auf keinem Pfad ändert sich die Anzahl der schwarzen Knoten. Durch diese Transformation_E3 wird das Problem um zwei Ebenen nach oben verschoben mit als dem neuen Problemknoten.[13]

      G = *pParents; // Der Großelter G von N existiert (ist ein Knoten).
      if (P == G->left)
       {
        d = LEFT;
        U = P->right; // Onkel von N
       }
      else
       {
        d = RIGHT;
        U = P->left;  // Onkel von N
       }
      if (U != NULL && U->color == RED) // Bedingung_E3
       {
        // Transformation_E3:
        P->color = BLACK;
        U->color = BLACK;
        G->color = RED;
        N = G; // neuer Problemknoten (kann die Wurzel sein)
        continue; // Iteration zwei Ebenen höher (es ist N == *pParents)
       }

</syntaxhighlight>

Einfügen Fall 4: Der Problemknoten hat keinen oder einen schwarzen Onkel und hat eine Kindesrichtung entgegengesetzt zu der seines roten Elters , d. h., ist innerer Enkel.

Einfügen Fall 4

Eine entsprechende Rotation um vertauscht die Rollen von und , und zwar eine Linksrotation, wenn linkes Kind (und d == LEFT) ist, sonst eine Rechtsrotation. (Im Folgenden wird eine solche Rotation als d-Rotation bezeichnet.) Dadurch werden die Pfade des Teilbaums (s. Diagramm) so verändert, dass sie durch einen zusätzlichen, während die des Teilbaums durch einen Knoten 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#= erfüllt bleibt.

Die Ergebniskonstellation entspricht der Eingangskonstellation des Falles 4 mit als dem neuen Problemknoten.

       if (N != P->child[d]) // Bedingung_E4
        {
         // N ist rechts an P und P links an G (===> N ist innerer Enkel)
         //   oder
         // N ist links an P und P rechts an G (===> N ist innerer Enkel)
         // Transformation_E4:
         // rotate(P,d); // d-Rotation um P
         P->child[LEFT+RIGHT-d] = N->child[d]; // im Diagramm: Teilbaum 2
         N->child[d] = P;
         U = P; // aufbewahren
         P = N; // neuer Elter (rot)
         N = U; // neuer Problemknoten (rot),
                // d-Kind von P und
                // äußerer Enkel von G
                // (nicht die Wurzel)
        }

Einfügen Fall 5: Der Problemknoten hat keinen oder einen schwarzen Onkel. Seine Kindesrichtung ist dieselbe wie die von , also ist äußerer Enkel.

Einfügen Fall 5

Eine (nicht-d)-Rotation um macht zum Elter sowohl von als auch von . Da rot war, muss wegen Forderung !RR schwarz sein. Vertauscht man nun die Farben von und , 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 liefen und nun alle durch laufen, der inzwischen – wie vor der Transformation – der einzige schwarze der drei Knoten ist.

       // Bedingung_E5
       // N (rot) ist äußerer Enkel.
       // Transformation_E5:
       // rotate(G,LEFT+RIGHT-d); // (nicht-d)-Rotation um G
       G->child[d] = P->child[LEFT+RIGHT-d]; // im Diagramm: Teilbaum 3
       P->child[LEFT+RIGHT-d] = G;
       P->color = BLACK;
       G->color = RED;
       return; // Einfügung fertiggestellt
      }

     // Hierher nur nach  continue;  des Falles 2:
     while (--pParents >= &Parents[0]) // Ende der (do while)-Schleife.
    }
   // pParents < &Parents[0]

Einfügen Fall 0: Der Problemknoten ist die (ggf. neue) Wurzel. Wie oben angemerkt, könnte eine rote Wurzel ohne Verletzung der Rot-Schwarz-Forderungen auf schwarz umgefärbt werden[7] – was die Abfrage auf Bedingung_E2 und den Fall 2 überflüssig machen würde.

   // Bedingung_E0: N ist die Wurzel des Baums T
   // Transformation_E0:
   T->root = N; // neue Wurzel
   return; // Einfügung fertiggestellt
  } // Ende RBinsert1

Operation Löschen

Das Löschen eines Knotens, sein Name sei (wie engl. remove), aus einem Rot-Schwarz-Baum erfolgt wie bei einem binären Suchbaum. Hat ein oder gar kein Kind, dann bleibt er der Löschknoten. Hat aber zwei Kinder, dann nimmt man, ohne letztendlich die Sortierreihenfolge zu stören, als effektiven Löschknoten einen seiner Nachbarknoten – natürlich, nachdem man vorher die Benutzerdaten ausgetauscht hat.[14] Wir werden also die Löschung durch die Entfernung eines Knotens mit maximal einem Kind durchführen, eines Knotens, den wir weiterhin mit benennen.

Einfache Fälle

Hat genau ein Kind, so sei dieses mit (wie engl. node) bezeichnet; es muss ein roter Knoten sein. Hat kein Kind, so sei der Nullzeiger. In beiden Fällen sei (wie engl. parent) der Elter von und d (wie engl. direction) die Kindesrichtung von (rechtes oder linkes Kind von ). Und in beiden Fällen wird an der Kindesrichtung d von durch ersetzt.

Die nun folgenden Aktionen überprüfen, ob die Rot-Schwarz-Eigenschaften im Baum eingehalten sind und stellen sie ggf. wieder her.

Ist rot, so hat es kein Kind. Denn ein solches müsste wegen der Forderung !RR schwarz sein und könnte wegen der Forderung S#= nicht einzeln sein. Da alle Pfade, die ursprünglich durch den gelöschten roten Knoten verliefen, nun durch einen roten Knoten weniger verlaufen, ändert sich an der Anzahl der schwarzen Knoten nichts, womit die Forderung S#= erfüllt bleibt.

Ebenfalls einfach zu lösen ist der Fall, wenn schwarz ist und rot. Man färbt schwarz und macht ihn an der Kindesrichtung d zum Kind von . Damit ist aus dem Baum entfernt, und die Forderung !RR bleibt erfüllt. Ferner verlaufen nun alle Pfade, die durch den gelöschten schwarzen Knoten verliefen, durch sein nunmehr schwarzes Kind, wodurch Forderung S#= erfüllt bleibt.

Das Löschen eines schwarzen internen Blattes

Übrig bleibt der Fall, dass der schwarze Knoten gar kein Kind hat, also ein schwarzes internes Blatt ist.

Nach der Ersetzung von bei durch einen Nullzeiger, bezeichnet als , enthalten die durch ihn führenden Pfade einen schwarzen Knoten weniger als vorher, somit einen weniger als die nicht durch führenden Pfade (sofern es diese gibt) – in Verletzung der Forderung S#=.

Im nachfolgenden Beispielcode ist angenommen, dass eine vorausgehende Suchfunktion, die den zu löschenden Knotens lokalisiert hat, den Stapel struct node* Parents[] von dessen Vorfahren gebildet und an die Löschfunktion übergeben hat. Wenn der Baum nicht leer ist, ist der Zeiger Parents[0] gleich dem Zeiger auf den Wurzelknoten.

Der Kopf einer Funktion RBdelete2 zum Löschen eines schwarzen Knotens ohne Kind könnte dann wie folgt aussehen:

 void RBdelete2(
   RBtree* T,                // -> Rot-Schwarz-Baum
   struct node*   Parents[], // Liste der -> Vorfahren
   struct node** pParents,   // ->-> Elterknoten von R
   struct node* R)           // zu löschender Knoten, hier: schwarz
  {
   byte d;                   // Richtung ∈ {LEFT, RIGHT}
   struct node* N = NULL;    // Problemknoten (zunächst ein Nullzeiger)
   struct node* P, S, C;

   if (pParents >= &Parents[0]) // R ist nicht die Wurzel
    {
     P = *pParents; // Elter von R
     // Ersetze R bei P durch N:
     if (R == P->left)
      {
       P->left = N;
       d = LEFT;     // Kindesrichtung von N
       S = P->right; // Geschwister von R, jetzt von N
      }
     else
      {
       P->right = N;
       d = RIGHT;    // Kindesrichtung von N
       S = P->left;  // Geschwister von R, jetzt von N
      }

Der Knoten war nicht die Wurzel und, da er schwarz war, hatte er ein Geschwister, das (nicht-d)-Kind[10] von . Es ist nunmehr das Geschwister von und sei mit (wie engl. sibling) bezeichnet.

In den Diagrammen bezeichnen wir sein nahes Kind (das der Kindesrichtung d) mit (wie engl. close nephew) und das ferne Kind mit (wie engl. distant nephew).

Löschen: Schleifeninvariante:

  1. Zu Beginn jedes Iterationsschritts ist der gerade betrachtete Problemknoten schwarz. (In dem zum Fall gehörigen Diagramm hat er eine blaue Kontur.)
  2. ist nicht die Wurzel und  != NULL.
  3. Die Forderung !RR »Kein roter Knoten hat ein rotes Kind« ist überall erfüllt.
  4. Die Anzahl der schwarzen Knoten auf den Pfaden, die nicht durch führen, ist ungeändert. Enthalten die Pfade durch einen schwarzen Knoten weniger, dann ist die Forderung S#= »Die Anzahl der schwarzen Knoten von jedem beliebigen Knoten zu einem Blatt ist auf allen Pfaden gleich« verletzt, und die Reparatur muss fortgesetzt werden.
    Andernfalls ist der Baum in Rot-Schwarz-Form.
  5. In den Diagrammen stellen die kleinen nummerierten Dreiecke (Rot-Schwarz-)Teilbäume dar.
    Tragen sie eine kleine schwarze Scheibe an der Spitze, dann ist ihre Schwarztiefe um 1 höher als die der anderen, welch letztere auch 0 sein kann.

Damit kommen in den linken Hälften der Diagramme eines Löschen-Falls die durch führenden Pfade auf eine (kleine oder große) schwarze Kreisfläche weniger.

Bedingung Fall
Rota-
tion
Zuwei-
sung
Ergebnis
Test
RedOrBlackNode.svg 0 RedOrBlackNode.svg
MinusNode.svg BlackNode.svg BlackNode.svg BlackNode.svg BlackNode.svg 1 := MinusNode.svg ? ? ? ? 0
MinusNode.svg BlackNode.svg BlackNode.svg RedNode.svg BlackNode.svg 2 := MinusNode.svg RedNode.svg ? BlackNode.svg ? 3
MinusNode.svg RedNode.svg BlackNode.svg BlackNode.svg BlackNode.svg 3 BlackNode.svg BlackNode.svg BlackNode.svg RedNode.svg BlackNode.svg
MinusNode.svg RedOrBlackNode.svg RedNode.svg BlackNode.svg 4 := MinusNode.svg RedOrBlackNode.svg ? BlackNode.svg RedNode.svg 5
MinusNode.svg RedOrBlackNode.svg BlackNode.svg RedNode.svg 5 BlackNode.svg BlackNode.svg RedOrBlackNode.svg BlackNode.svg
Löschen: Zusammenschau der Fälle

Löschen: Zusammenschau der Fälle[15][16]

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 Reparatur des Baumes führen.

In der nebenstehenden Tabelle wird ein Fall durch eine Zeile repräsentiert, die

  1. die Bedingung, d. i. die Konstellation, die den Fall definiert,
  2. die Fallnummer,
  3. die Konstellation nach Transformation und ggf. Zuweisung in der Spaltengruppe Ergebnis

enthält. Eine Konstellation (5 Spalten) besteht aus den 5 Farben der 5 Knoten . Das Zeichen MinusNode.svg zeigt die schwarze Farbe bei einem Knoten an und gleichzeitig, dass die Zahl der schwarzen Knoten auf den Pfaden durch ihn um 1 vermindert ist. In ein und derselben Zeile bedeuten die 2 Zeichen RedOrBlackNode.svg dieselbe Farbe. Eine Zelle ist leer gelassen, wenn es bei dem beschriebenen Fall auf die entsprechende Angabe nicht ankommt.

Die Konstellationen in der Gruppe Bedingung genügen der Schleifeninvariante, und ihre logische Summe schöpft diese genau aus.

Die Transformation, deren Fallnummer in der Spalte Fall → verlinkt ist, transformiert die Eingabe in eine Konstellation, die im Diagramm des Falles dargestellt ist. Steht ein „–“ 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 für den Problemknoten in der Spalte Zuweisung, auch die Knoten eindeutig bestimmt. Die Gruppe Ergebnis zeigt dann die Konstellation nach der Zuweisung.

Der Eintrag „0“ kommt nur bei der Transformation_L1 vor und bedeutet u. U. einen neuen Iterationsschritt auf der um 1 höheren Ebene im Baum, beginnend mit dem Test auf die Bedingung_L0. Die Anzahl der Ebenen stimmt mit der Höhe überein, so dass höchstens Iterationen vorkommen können. Nun ist der Aufwand für eine Iteration beschränkt (d. h. in ) und damit der für die gesamte Löschoperation in . Gemäß Abschnitt #Durchschnittliche und amortisierte Laufzeit ist der Aufwand im Mittel sogar konstant.

Bei einem Eintrag in der Spalte Rotation ist eine Rotation an der Transformation beteiligt. Und die Tabelle zeigt, dass bei einer Löschung maximal 3 Rotationen erforderlich sind. Denn nach einer Rotation (Transformation_L2, Transformation_L4 und Transformation_L5) kommt kein neuer Iterationsschritt – die Rotationen befinden sich am Ende der letzten Iteration.

Im folgenden C-Beispielcode entscheidet die Kindesrichtung (im Beispielcode die Variable d) von sowohl über die nachfolgenden Rotationsrichtungen wie über die Kindesrichtung der Neffen von . (Der Neffe (wie engl. close) mit derselben Kindesrichtung ist der „nahe“, der andere, (wie engl. distant), der „ferne“ Neffe.)[11] Die Diagramme bei den Fällen zeigen nur eine Kindesrichtung, und zwar ist immer links von .

Jeder Fall wird unter seiner Fallnummer erläutert und einschließlich Test (if-Abfragen) und Transformation durch ein Stück C-Code genau beschrieben.[12][17]

Löschen Fall 1: Der Elter des Problemknotens , sein Geschwister und die Kinder und von sind alle schwarz.

Löschen Fall 2

Die Umfärbung des Knotens von schwarz in rot vermindert in allen Pfaden, die durch führen, die Zahl der schwarzen Knoten um 1 auf . Das betrifft genau die Pfade, die durch , aber nicht durch führen, welch letztere Pfade vorher schon genau schwarze Knoten enthalten haben. Damit sind es schwarze Knoten in den Pfaden, die durch führen, und in solchen, die nicht durch führen – wenn es denn solche noch gibt. Somit wird die Bedingung 4. der Schleifeninvariante nunmehr mit als dem neuen Problemknoten erfüllt.

In der folgenden ersten Iteration haben die Knoten die Schwarzhöhe 0.

     if (S->color == RED)
       goto Fall_L2; // Bedingung_L2: rot: S ===> schwarz: P && C && D
     // S->color == BLACK:
     if (S->child[LEFT+RIGHT-d] != NULL) // (Schwarzhöhe 0)
       goto Fall_L5; // der ferne Neffe (im Diagramm: D) ist rot
     if (S->child[d] != NULL)            // (Schwarzhöhe 0)
       goto Fall_L4; // der nahe  Neffe (im Diagramm: C) ist rot
     // beide Neffen von N sind schwarz:
     if (P->color == RED)
       // Bedingung_L3: rot: P; schwarz: C && S && D
       goto Fall_L3;

     // Bedingung_L1: schwarz: P && C && S && D
     // Transformation_L1:
     S->color = RED;
     N = P; // neuer Problemknoten (kann die Wurzel sein)
     // Iteration eine Ebene höher

Beginn der while-Schleife.
Innerhalb dieser Schleife ist die Schwarzhöhe aller Knoten > 0.

     while (--pParents >= &Parents[0]) // Beginn der while-Schleife.
      {
       P =*pParents; // N ist nicht die Wurzel
       if (N == P->left) { d = LEFT;  S = P->right; }
                    else { d = RIGHT; S = P->left;  }
       if (S->color == RED)
         goto Fall_L2; // Bedingung_L2: rot: S ===> schwarz: P && C && D
       // S->color == BLACK:
       if (S->child[LEFT+RIGHT-d]->color == RED) // (Schwarzhöhe > 0)
         goto Fall_L5; // der ferne Neffe (im Diagramm: D) ist rot
       if (S->child[d]->color == RED)            // (Schwarzhöhe > 0)
         goto Fall_L4; // der nahe  Neffe (im Diagramm: C) ist rot
       // beide Neffen von N sind schwarz:
       if (P->color == RED)
         goto Fall_L3;

       // Bedingung_L1: schwarz: P && C && S && D
       // Transformation_L1:
       S->color = RED;
       N = P; // neuer Problemknoten (kann die Wurzel sein)
      } // Ende der while-Schleife.
     // pParents < &Parents[0] ===> N ist die Wurzel
    }

Löschen Fall 0: Der Problemknoten ist die (ggf. neue) Wurzel.

In diesem Fall ist man fertig, da alle Pfade durch führen (und alle Pfade einen schwarzen Knoten weniger enthalten als vorher).

   // Bedingung_L0: N ist die Wurzel des Baums T
   // N ist die neue Wurzel.
   // (Nullzeiger, wenn der Baum jetzt leer ist.)
   // Da R ein schwarzer Knoten war,
   // verringert sich die Schwarztiefe des Baumes um 1.
   T->root = N;
   return; // Löschung fertiggestellt

Löschen Fall 2: Das Geschwister des Problemknotens ist rot.

Löschen Fall 1

Eine Rotation um macht zum Großelter von , und zwar eine Linksrotation, wenn linkes Kind (und d == LEFT) ist, sonst eine Rechtsrotation. (Im Folgenden wird eine solche Rotation als d-Rotation bezeichnet.) Danach invertiert man die Farben von und . Alle Pfade haben weiterhin dieselbe Anzahl an schwarzen Knoten, aber hat nun ein schwarzes Geschwister () und einen roten Elter (), weswegen man nun zu Fall 3, 4 oder 5 weitergehen kann – mit als altem und neuem Problemknoten.[13]

 Fall_L2:
   // Bedingung_L2: rot: S ===> schwarz: P && C && D
   // Transformation_L2:
   S->color = BLACK;
   P->color = RED;
   C = S->child[d]; // aufbewahren
   // rotate(P,d); // d-Rotation um Knoten P
   P->child[LEFT+RIGHT-d] = S->child[d]; // im Diagramm: C
   S->child[d] = P;

   S = C; // nach der Rotation: neues Geschwister von N
     // (Seine Kinder können Schwarzhöhe 0 haben, deshalb etwas komplizierter:)
   if ((S->child[LEFT+RIGHT-d]        != NULL) // == NULL ===> gilt als nicht-rot
    && (S->child[LEFT+RIGHT-d]->color == RED))
     goto Fall_L5; // ferner Neffe (im Diagramm: Teilbaum 4) ist rot
   if ((S->child[           d]        != NULL)
    && (S->child[           d]->color == RED))
     goto Fall_L4; // naher  Neffe (im Diagramm: Teilbaum 3) ist rot
   // weiter zu Fall_L3:   // beide Neffen von N sind schwarz

Löschen Fall 3: Sowohl das Geschwister des Problemknotens als auch die Kinder und von sind schwarz, aber der Elter von ist rot.

Löschen Fall 3

Eine Vertauschung der Farben von und lässt die Anzahl der schwarzen Knoten auf den Pfaden, die durch laufen, unverändert, fügt aber auf allen Pfaden durch einen schwarzen Knoten hinzu und gleicht damit den fehlenden schwarzen Knoten auf diesen Pfaden aus.

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

Löschen Fall 4: Das Geschwister von ist schwarz, wogegen der nahe Neffe rot ist. Der im Diagramm weiß dargestellte Knoten behält seine Farbe, rot oder schwarz.

Löschen Fall 4

Eine (nicht-d)-Rotation um macht zum Elter von und zugleich zum Geschwister von . Danach vertauscht man die Farben von und . Nun haben alle Pfade immer noch die gleiche Anzahl an schwarzen Knoten, aber hat ein schwarzes Geschwister (), dessen fernes Kind () rot ist, womit man zum Fall 5 weitergehen kann. Weder noch noch die Schwarztiefe werden durch diese Transformation beeinflusst.

 Fall_L4:
   // Bedingung_L4: schwarz: S; rot: naher Neffe C von N
   // Transformation_L4:
   C = S->child[d]; // aufbewahren
   C->color = BLACK;
   // rotate(S,LEFT+RIGHT-d); // (nicht-d)-Rotation um Knoten S
   S->child[d] = C->child[LEFT+RIGHT-d]; // im Diagramm: Teilbaum 4
   C->child[LEFT+RIGHT-d] = S;
     // dadurch wird S zum fernen Neffen von N
   S->color = RED;
   S = C; // naher Neffe wird neues Geschwister von N (schwarz)
   // weiter zu Fall_L5:

Löschen Fall 5: Das Geschwister von ist schwarz, und der ferne Neffe von ist rot. Die im Diagramm weiß dargestellten Knoten (linke Seite) und (rechte Seite) haben dieselbe Farbe, rot oder schwarz.

Löschen Fall 5

Eine d-Rotation um macht zum Großelter von . Nun reicht es, die Farben von und zu vertauschen und schwarz zu färben. hat immer noch dieselbe Farbe, wodurch die Forderung !RR erfüllt bleibt. Aber hat nun einen zusätzlichen schwarzen Vorfahren: Falls vor der Transformation noch nicht schwarz war, so ist er nach der Transformation schwarz, und falls schon schwarz war, so hat nun als schwarzen Großelter, weswegen die Pfade, die durch führen, nun einen zusätzlichen schwarzen Knoten passieren.

Bei den Pfaden, die sich ändern und die nicht durch führen, gibt es zwei Möglichkeiten:

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

 Fall_L5:
   // Bedingung_L5: schwarz: S; rot: ferner Neffe D von N
   // Transformation_L5:
   S->color = P->color;
   P->color = BLACK;
   // rotate(P,d); // d-Rotation um Knoten P
   P->child[LEFT+RIGHT-d] = S->child[d]; // im Diagramm: Teilbaum 3
   S->child[d] = P;
   S->child[LEFT+RIGHT-d]->color = BLACK; // im Diagramm: D
   return; // Löschung fertiggestellt
  } // Ende RBdelete2

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 mit 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 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 Elementen nie eine gewisse Höhe (im Falle des Rot-Schwarz-Baumes ) überschreitet, so hat man bewiesen, dass die oben genannten Operationen im schlechtesten Fall logarithmische Kosten haben, nämlich die genannten Kosten von für einen Baum, in dem Elemente gespeichert sind. Somit muss gezeigt werden, dass folgende Aussage gilt:

Für die Höhe eines Rot-Schwarz-Baumes, der Elemente speichert, gilt: .

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

Zu gibt es einen Rot-Schwarz-Baum der Höhe mit

internen Knoten, und keinen mit weniger ( steht für die Gauß-Klammer).[18]

Beweis

Damit ein Rot-Schwarz-Baum einer bestimmten Höhe 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 Schwarztiefe zu erreichen. Seine Einfärbung hat also unten beim internen 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.[19] 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 mit einem roten internen Blatt, welches gleichzeitig die Wurzel ist. Also ist in Übereinstimmung mit .

Bei einem Minimalbaum (RBh in der Abbildung) der Höhe 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 mit Knoten und der Schwarztiefe ; der niedrigere ist ein vollständiger Binärbaum mit Höhe = Schwarztiefe , hat also interne Knoten. Damit ist rekursiv

(großer Kindbaum) (Wurzel) (kleiner Kindbaum)
woraus man

ausrechnet.  ■

Der Graph der Funktion ist konvex nach unten und stückweise linear mit den Ecken an den Punkten mit . Ferner ist A027383(h–1) für mit der Folge A027383 in OEIS.

Zur Höhe gibt es Formen von Minimalbäumen, da die Position des längsten Pfades der Position eines externen Blattes des vollständigen Binärbaums der Höhe entspricht und dadurch auch die Lage der Knoten außerhalb dieses Pfades bestimmt ist. (Die Abbildung zeigt die äußerste linke Position.)

Umformung

Wegen (eine Folge von ) haben wir für ungerades die Ungleichung

so dass sich für alle (geraden wie ungeraden)

ergibt.

Da die kleinste Knotenzahl für alle Rot-Schwarz-Bäume der Höhe ist, gilt:

Bringt man nun noch den Summanden –2 auf die andere Seite und logarithmiert, so folgt:

Somit folgt die Behauptung, dass ein Rot-Schwarz-Baum eine maximale Höhe von 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 liegen mit als der Zahl der Schlüssel.[20]

Durchschnittliche und amortisierte Laufzeit

Der Rot-Schwarz-Baum bietet amortisiert konstante Modifikationskosten[21] und damit auch im Mittel konstante. Anwendungen von (binären) Suchbäumen, die nur Sequenzen von Einfügungen und Löschungen – ganz ohne jede Suchoperation – enthalten, gehen allerdings am Zweck des Suchbaums vorbei. Sieht man also von dieser Art Anwendungen ab, ist das Gesamtverhalten einer Mischung von Suchen und Modifikation amortisiert, im Mittel und im Worst Case logarithmisch in der Anzahl der Knoten.

Anzahlen von Rot-Schwarz-Bäumen

Die 3 RB-Bäume mit 3 Schlüsseln

Die Folge A001131 in OEIS gibt in Abhängigkeit von der Knotenzahl die Gesamtzahl der Rot-Schwarz-Bäume, Folge A001137 in OEIS derer mit schwarzer Wurzel und Folge A001138 in OEIS derer mit roter Wurzel.

In einem reinen Einfügeszenario wird bspw. von den 3 möglichen Bäumen mit 3 internen Knoten (Schlüsseln) nur der eine Baum mit schwarzer Wurzel und 2 roten Kindern (der linke in der Abbildung) gebildet.
Beim Suchen und Traversieren ist wegen der identischen Form (Gestalt) der 3 Bäume alles Verhalten einschließlich Laufzeit gleich. Unterschiede gibt es aber bei den Einfügungen: Bei den rechten 2 Bäumen sind alle Einfügungen vom Typ Transformation_2 und beim linken Baum alle vom Typ Transformation_3 gefolgt von Transformation_1.

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.[22][23]

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 (split) und Verschmelzen (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, engl. fill factor) der Knoten beobachten und verwalten, weshalb letztere als sehr effiziente Art der Implementierung der 2-3-4-Bäume gelten.[24]

Vergleich mit AVL-Baum

Die Menge der AVL-Bäume ist eine echte Teilmenge in der Menge der Rot-Schwarz-Bäume. Denn jeder Binärbaum, der das AVL-Kriterium erfüllt, lässt sich in einer das Rot-Schwarz-Kriterium erfüllenden Weise einfärben.[25][26]

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 (internen) Knoten und der 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 Größe ist. Konsequenterweise ist auch die Worst-Case-Höhe des AVL-Baums kleiner als die des Rot-Schwarz-Baums, und zwar um den Faktor (2 log2 Φ)−1 ≈ 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 Komplexitätsklasse an. Der Rot-Schwarz-Baum bietet allerdings amortisiert konstante Einfüge- und Löschkosten (jeweils ohne Navigation). Beim AVL-Baum sind nur die Einfügekosten amortisiert, die Löschkosten immerhin im Mittel konstant.

Realistische Anwendungssituationen mit Performancedaten und -vergleichen – auch mit weiteren Suchalgorithmen und Spielarten der Datenstrukturen – finden sich bei Ben Pfaff.[27] 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 AVLRB zwischen 0,677 und 1,077 bei einem Median von ≈0,947 und einem geometrischen Mittelwert von ≈0,910.

Der Speicherplatzbedarf ist praktisch identisch: 1 Bit für die Rot-Schwarz-Farbe gegenüber 2 Bits[28] für den AVL-Balance-Faktor. Während die Balance-Faktoren eines AVL-Baums direkt von dessen Gestalt abhängen, sind bei Rot-Schwarz-Bäumen derselben Gestalt – außer bei den Minimalbäumen gerader Höhe – unterschiedliche Einfärbungen möglich (s. Abschnitt #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 regeltreue 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.[29] Diese „Top-Down-Strategie“[30] ist bspw. für persistente und nebenläufige Programmierung interessant.[31][32]

So bleibt beim Einfügen der frisch eingefügte Knoten rot (das sind die Fälle 1 bis 4). Das bedeutet, dass eine zugehörige Suchfunktion im Abstieg den Baum an der betreffenden Stelle (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 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 TreeSet[33] und TreeMap[34] als Rot-Schwarz-Bäume implementiert. Sie stellen geordnete Mengen bzw. geordnete Dictionarys zur Verfügung.

Weitere Bäume

Literatur

Einzelnachweise und Anmerkungen

  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. Diese Abschätzung ist scharf (siehe #Höhenbeweis) und für wegen
    marginal genauer als
    .
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7, S. 273.
  5. bei Ben Pfaff non-branching node
  6. Mehlhorn 2008 S. 154.
  7. a b Einige Autoren fordern noch, dass die Wurzel des Baums schwarz zu färben sei. Nicht jedoch z. B. Mehlhorn 2008 und Sedgewick. Tatsächlich stört diese Forderung die Rekursivität und erübrigt sich. Denn ist die Wurzel rot, so müssen ihre Kinder nach Forderung !RR schwarz sein, und bei ihrer Umfärbung in schwarz wird keine der anderen Forderungen verletzt. In den Algorithmen kann jedoch die Zahl der Fallunterscheidungen marginal geringer gehalten werden, wenn man bei einem roten Knoten immer einen Elter voraussetzen kann.
  8. Wir folgen diesbezüglich Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees.
  9. Werden die NIL-Knoten als minimale Rot-Schwarz-Knoten implementiert, so kosten sie Speicher für zwei Kindzeiger, einen Elterzeiger, das Feld für die Farbe und ein Erkennungsfeld für die Eigenschaft »NIL-Knoten«. Bei Schlüssel tragenden Knoten braucht man NIL-Knoten, womit sich der Rot-Schwarz-Overhead mehr als verdoppelt. Überdies sind die Verknüpfungen der NIL-Knoten mit den Schlüssel tragenden Knoten (bspw. bei den Rotationen) auch zu pflegen, so dass sich auch die Laufzeit verlängert. Das bedeutet im Ergebnis einen erheblichen Aufwand für einen völlig unspezifischen Gegenwert an Information.
  10. a b UNDEFINED, wenn der Baum leer war. Es ist
    nicht-d   ≡   LEFT+RIGHT-d       sowie
    K->child[LEFT]   ≡   K->left       und       K->child[RIGHT]   ≡   K->right.
  11. a b Eine andere Möglichkeit ist, den Schleifenrumpf der while-Schleife in zwei Versionen aufzuschreiben, in einer für die Kindesrichtung links und in einer für rechts (so Ben Pfaff).
  12. a b 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.
  13. a b Man beachte die in der Programmiersprache C festgelegte Art der Auswertung der Konjunktion (K != NULL) && (K->color == RED), so dass im Fall K == NULL ohne weitere Auswertung der else-Zweig ausgeführt wird.
    Im aktuellen Fall kann K == NULL aber nur in der ersten Iteration der Schleife vorkommen, nur dann ist die Schwarzhöhe 0.
  14. 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)
  15. Die Aufteilung entspricht Roger Whitney.
  16. 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).
  17. Um der Kürze der Aufschreibung willen wird im Beispielcode einige Male goto verwendet. Es ist leicht, dies durch Verdoppelung des Codes zu vermeiden.
  18. Diese Minimalbäume spielen bei den Rot-Schwarz-Bäumen eine ähnliche Rolle wie die Fibonacci-Bäume bei den AVL-Bäumen.
  19. Sedgewick 2011 S. 444 Proof sketch
  20. 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. Gängig sind Hauptspeicher mit 32 Bit und 64 Bit breiten 8-Bit-Byte-Adressen. (Allerdings wird von den Betriebssystemen oft nur der halbe Adressbereich von 0 bis 231–1 bzw. 263–1 dem Benutzer zur Verfügung gestellt.) Der Entwickler wird Anwendern gegenüber typischerweise die Knotenzahl (also die Anzahl von Elementen) beschränken, da die Baumhöhe nur indirekt wahrnehmbar ist. Die folgende Tabelle stellt zu jeder Elementeanzahl eine Höhenangabe zur Verfügung, die von einem Rot-Schwarz-Baum mit Elementen nicht überschritten wird. Da in einem 32-Bit-Adressraum maximal 232 Bytes untergebracht werden können und ein Knoten mindestens 2 Kind-Zeiger à je 4 Bytes benötigt, kann bei 4 Bytes Benutzerdaten ein Baum mit maximal 232/(2×4 + 4) = 357913941 Knoten untergebracht werden. Wie die Tabelle zeigt, kann im erwähnten Adressraum die Höhe 54 durch einen Rot-Schwarz-Baum niemals überschritten werden. Ein Stapelspeicher von 54×4 = 216 Bytes für die Elter-Zeiger kann also nicht überlaufen.
    Umfang von Rot-Schwarz-Bäumen
    Anzahl Knoten Höhe
    100663293 50
    134217725 51
    201326589 52
    268435453 53
    402653181 54
    108086391056891901 110
    144115188075855869 111
    216172782113783805 112
    288230376151711741 113
    432345564227567613 114
    576460752303423485 115
    864691128455135229 116
    1152921504606846973 117

    Mit den Bezeichnungen im Text ist

    eine Maßgabe, die so knapp wie möglich unterhalb der Knotenzahl des nächstgrößeren Minimalbaums bleibt.

  21. 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 die Sprache der Rot-Schwarz-Bäume übersetzt heißt das:
    Für eine beliebige Folge von Einfüge- und Löschoperationen in einen anfänglich leeren Rot-Schwarz-Baum ist die Anzahl der Farbwechsel und Rotationen in .
    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 (Rebalancierungskosten).
    Das Kapitel „III.5.3.2. Amortisierung von Rebalancierungskosten und Sortieren vorsortierter Files“ in Mehlhorn 1998 berücksichtigt dagegen das Aufsuchen mit dem Ergebnis (Satz 10, S. 209):
    Eine Folge von Elementen mit Inversionen kann in Zeitkomplexität sortiert werden.
    Das Maß der Sortiertheit wird durch angegeben, und es ist mit an der Obergrenze für völlig unsortierte Files. Für das Wirksamwerden dieser Formel für kleinere ist allerdings eine spezielle Suchfunktion (bspw. Mehlhorn 1998 S. 208) erforderlich, die Nachbarschaften erkennt und ausnützt.
  22. Mehlhorn 1988 S. 193
  23. 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 engl. 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).
  24. Mehlhorn 1988 S. 187
  25. 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).
  26. 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.
  27. Ben Pfaff: Performance Analysis of BSTs in System Software. Stanford University 2004.
  28. oder auch nur 1 Bit (s. Implementierung)
  29. Red Black Trees. Abgerufen am 14. Oktober 2015.
  30. Mehlhorn 1988 S. 197–198.
  31. 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.
  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. docs.oracle.com
  34. docs.oracle.com

Weblinks

Dieser Artikel wurde am 5. November 2005 in dieser Version in die Liste der lesenswerten Artikel aufgenommen.