Hauptmenü öffnen
Rot-Schwarz-Baum
Komplexität
bei Elementen
Platz
Operation im Mittel,
amortisiert
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 zwei Forderungen erreicht, die die Balance des Baums in einer Weise definieren, dass die Höhe eines Baums mit Schlüsseln (Elementen) nie größer als sein kann.[Anm. 1] Somit können die wichtigsten Operationen in Suchbäumen – Suchen, Einfügen und Löschen – garantiert in (s. Landau-Symbole) ausgeführt werden.

DefinitionBearbeiten

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 folgenden zwei Forderungen zu erfüllen:[3]

  • Forderung !RR   (Nicht Rot Rot):
Kindknoten eines roten Knotens sind 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 „Pfadendengenannt,[4] enthält die gleiche Anzahl schwarzer Knoten.
 
Rot-Schwarz-Baum der Höhe 4 und der Schwarztiefe 2

Eine unmittelbare Folge aus den Forderungen ist, dass ein Halbblatt   (bspw. der Knoten   im Beispielbaum) schwarz und sein (einzelnes) Kind   (der Knoten  ) rot sein muss, denn beide sind Pfadenden, und der Pfad zu   ist um genau den Knoten   kürzer.

Weitere Definitionen und FolgerungenBearbeiten

Die auf allen Pfaden von Wurzel zu Pfadende gleiche Anzahl   schwarzer Knoten wird die Schwarztiefe[5] des Baums genannt. Als Schwarzhöhe eines Knotens (engl. black-height[6]) wird die einheitliche Anzahl schwarzer Knoten auf allen Pfaden zu den Pfadenden im von ihm gewurzelten Teilbaum bezeichnet. Nach dieser Definition ist ein Knoten der Schwarzhöhe 0 ein rotes Blatt,[Anm. 2] wie bspw. die Knoten   im Beispielbaum, wogegen die schwarzen Knoten  , aber auch die roten Knoten   die Schwarzhöhe 1 haben.   ist der einzige Knoten mit Ausgangsgrad 1, das einzige Halbblatt.

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

Ist   die Schwarztiefe des Baums, dann gibt es wegen der Forderung S#= auf einem Pfad von der Wurzel zu einem Pfadende genau   schwarze Knoten, aber wegen der Forderung !RR höchstens einen roten Knoten mehr als schwarze, also insgesamt maximal   Knoten. Damit gilt für die Zahl   aller Knoten im Baum  , so dass der Rot-Schwarz-Baum immer gut genug balanciert – auf jeden Fall so gut, dass das Verhältnis zwischen der Höhe   des Baums, für die   gilt, und dem Logarithmus der Knotenzahl   beschränkt bleibt. Diese logarithmische Beschränkung, die im § #Höhenbeweis formal bewiesen wird, ist aber gleichzeitig das informationstheoretische Optimum, d. h. es gibt keinen Binärbaum mit 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.

NIL-Knoten
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.
Sehr verbreitet in der Literatur über Rot-Schwarz-Bäume ist die 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 als externe Blätter angeheftet sind, die an den Pfadenden für die (randlosen) Intervalle zwischen den Schlüsseln stehen (engl. auch „missing nodes[8]) – und damit nicht als (einheitliche) Nullzeiger resp. Wächterknoten (Sentinel), sondern als Individuen aufgefasst werden.
In dieser zweiten Sichtweise kommen für die externen Blätter, genannt „NIL-Knoten“, eine Forderung hinzu, so dass sich folgende drei Forderungen ergeben:[9]
  • NIL-Knoten sind schwarz.
  • Kinder eines roten Knotens sind schwarz.
  • Jeder Pfad von einem gegebenen Knoten zu einem seiner NIL-Knoten enthält die gleiche Anzahl schwarzer Knoten.
Hier haben die (internen) die Schlüssel tragenden Knoten immer genau zwei Kinder.
Diese zweite (in mathematischer Hinsicht äquivalente) Sichtweise hat für das Verständnis der Sachverhalte einen vernachlässigbaren Nutzen, bei „naiver“ Implementierung ist ihr Einfluss jedoch eher ungünstig.[Anm. 3]

DatenstrukturBearbeiten

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

 struct node                // Knotenfeld
  {
   struct node* child[2];   // zwei Zeiger zu Kindknoten
                            // NULL-Zeiger, wenn
                            //   kein Knoten an dieser Stelle
   bool color;              // RED oder BLACK
   ...                      // Benutzer-Daten (wie Schlüssel, Wert etc.)
  } ;

 #define LEFT  false
 #define RIGHT true
 #define left  child[LEFT]  // -> linker  Kindknoten
 #define right child[RIGHT] // -> rechter Kindknoten
 #define RED   false
 #define BLACK true

Befindet sich an einer Stelle im Baum, an der syntaktisch ein Zeiger zu einem Knoten erwartet wird, ein Nullzeiger, so soll dies verabredungsgemäß das Fehlen (die „Nicht-Existenz“) eines Knotens an dieser Stelle des Baums bedeuten. M. a. W.: der von einem NULL-Knoten gewurzelte Teilbaum ist leer.

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

NavigationsoperationenBearbeiten

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 (oder einer Lücke) 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ügenBearbeiten

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 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   – für das Fehlen des linken oder des rechten Kindes dient.

Im unten stehenden Beispielcode wird angenommen, dass diese Richtung, die das letzte Ungleich-Ergebnis einer Suche nach dem Schlüssel von   reflektiert, im Funktionsargument d ∈ {LEFT,RIGHT}[Anm. 4] übergeben wird. Ferner wird angenommen, dass diese Suchfunktion den Stapel struct node* Parents[] der Vorfahren von   gebildet hat.[10] Der ebenfalls übergebene Zeiger struct node** 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 d irrelevant). Andernfalls ist pParent&Parents[0] (und Parents[0] gleich dem Zeiger auf den Wurzelknoten).

Der Knoten   wird zunächst rot gefärbt, damit die Schwarztiefe 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. Letztere Reparatur wird als „Rebalancierung“ (engl. rebalancing) bezeichnet.

Der neue Knoten   (wie engl. node) ist der gerade betrachtete „Problemknoten“. Sein Elter ist   (wie engl. parent). Der Großelter sei   (wie engl. grandparent) und der Onkel (das Geschwister des Elters)   (wie engl. uncle) genannt.

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

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

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

Einfügen: Invariante der Schleife zur Überprüfung und Reparatur:

  • Zu Beginn jedes Iterationsschritts ist der Problemknoten   rot.
  • Die Forderung !RR gilt im ganzen Baum – mit der einzigen möglichen Ausnahme beim Paar    (engl. red violation).
    Gilt sie auch dort (entweder weil   nicht existiert oder weil   existiert und schwarz ist), dann ist der Baum in Rot-Schwarz-Form.
  • Die Forderung S#= gilt für den ganzen Baum.

Einfügen: Erklärung der Symbole:

  1.   stellt einen schwarzen und   einen roten Knoten dar.
  2. In den Diagrammen stellen die nummerierten Dreiecke regelkonform angebundene Rot-Schwarz-Teilbäume dar. Diese Teilbäume haben alle dieselbe Schwarztiefe, die
    • 0 ist in der ersten Iterationsstufe[Anm. 2] und
    • mit der Iterationsstufe wächst.
Bedingung Fall
Rota-
tion
Zuwei-
sung
Ergebnis
Test
        x         x
  E0  
    E1    
    E2    
        i E3     :=          o E4
        o E4           
        E5  :=    ? ? ? E0
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 (Rebalancierung) des Baumes führen.

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

  • die Bedingung, d. i. die Konstellation, die den Fall definiert,
  • die Fallnummer,
  • 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 zu 100 % 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 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 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 „E0“ nur bei der Transformation_E5 vor. Er bedeutet ggf. einen neuen Iterationsschritt, der mit dem Test auf die while-Bedingung_E0 in der do while-Schleife beginnt, und zwar zwei Baumebenen (eine Schwarzebene) näher an der Wurzel. Da die Anzahl der Baumebenen 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   (mit oder ohne Suchen). Die reine Rebalancierung ist gemäß § #Durchschnittliche und amortisierte Laufzeit im Mittel und amortisiert in  .

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 zwei Rotationen vorkommen, und zwar bei Fall E4 nach Fall E3. Denn nach einer Rotation kommt kein neuer Iterationsschritt – die Rotationen befinden sich endrekursiv am Ende der letzten ausgeführten Iteration.

Im folgenden Beispielcode entscheidet die Kindesrichtung von   insbesondere über die nachfolgenden Rotationsrichtungen. Sie bestimmt aber bei Fall E3 auch die Auswahl des Falles: Hat   dieselbe Kindesrichtung wie  , dann ist die Angabe x (s. Zusammenschau) auf „o“ für „außen“, sonst auf „i“ für „innen“ zu setzen.[13]

Die Diagramme zu den Fällen zeigen nur eine Kindesrichtung, und zwar ist bei der Operation Einfügen der Elterknoten   immer linkes Kind von  .

Die kleinen nummerierten Dreiecke stellen (Rot-Schwarz-)Teilbäume dar. Diese Teilbäume haben alle dieselbe Schwarztiefe, die in der ersten Iteration 0 ist.

Der alte Problemknoten (in der linken Hälfte des Diagramms) hat eine blaue Kontur; und wenn die Operation nicht beendet ist, dann auch der neue (rechts).

Jeder Fall wird unter seiner Fallnummer erläutert und einschließlich Test (auf die ihn charakterisierende Bedingung) und Transformation durch ein Stück C-Code genau beschrieben.[14]

Einfügen Fall E1: Der Elter   des (roten) Problemknotens   ist schwarz.

Nach Eintritt dieser Bedingung gibt es kein Paar Elter→Knoten (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.

     do // Beginn der (do while)-Schleife
      {
       // Bedingung_E0 trifft NICHT zu: pParent >= &Parents[0]:
       // ===> Es gibt den Elter P von N.
       P = *pParent;  // -> Elterknoten von N
 Start_E:
       if (P->color == BLACK) // Bedingung_E1
         // Transformation_E1:
         return; // Einfügung fertiggestellt

Einfügen Fall E2: 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 (--pParent < &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 E3: Der rote Elter   ist nicht die Wurzel, so dass der Großelter   existiert. Da   rot ist, muss   schwarz sein, und das bei allen restlichen Fällen E3, E4 und E5.

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

Eine entsprechende Rotation um  [Anm. 5] vertauscht die Rollen von   und  , und zwar eine Linksrotation, wenn   linkes Kind (d. h. 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 Knoten mehr und die des Teilbaums   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#= erfüllt bleibt.

Die Ergebniskonstellation entspricht der Eingangskonstellation des Falles E4 mit   als dem neuen Problemknoten.[Anm. 6]

       G = *pParent; // Der Großelter G von N existiert.
       d = (P == G->right); // Kindesrichtung von P
       U = G->child[!d]; // Onkel von N (im Diagramm: Teilbaum 5)
       if (U == NULL || U->color == BLACK)
        {
         if (N != P->child[d]) // Bedingung_E3: N ist innerer Enkel
                               //               && N+P rot && U schwarz
          {
           // Transformation_E3:
           // rotate(P,d); // d-Rotation um P:
           P->child[!d] = N->child[d]; // neuer Elter für Teilbaum 3
           N->child[d] = P;
           G->child[d] = N;
           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 E4: Der Problemknoten   hat keinen oder einen schwarzen Onkel. Seine Kindesrichtung ist dieselbe wie die von  , also ist   äußerer Enkel.

Eine (nicht-d)-Rotation um  [Anm. 5] macht   zum Elter sowohl von   als auch von  . Da   rot war, muss wegen Forderung !RR   schwarz sein. Invertiert 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_E4: N ist äußerer Enkel && N+P rot && U schwarz
         // Transformation_E4:
         // rotate(G,!d); // (nicht-d)-Rotation um G:
         G->child[d] = P->child[!d]; // neuer Elter für Teilbaum 3
         P->child[!d] = G;
         P->color = BLACK;
         G->color = RED;
         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
         return; // Einfügung fertiggestellt
        }

Einfügen Fall E5: Sowohl der Onkel   als auch der Elter   des Problemknotens   ist rot.

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

       // Bedingung_E5: N+P+U rot
       // Transformation_E5:
       P->color = BLACK;
       U->color = BLACK;
       G->color = RED;
       N = G; // neuer Problemknoten (kann die Wurzel sein)
       // Iteration zwei Ebenen höher (es ist N == *pParent)
      }
     while (--pParent >= &Parents[0]) // Ende der (do while)-Schleife.
    } // end_if (pParent >= &Parents[0])

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

   // pParent < &Parents[0]
   // Bedingung_E0: N ist die Wurzel des Baums T.
   // Transformation_E0:
   T->root = N; // neue Wurzel
   return; // Einfügung fertiggestellt
  } // Ende RBinsert1

Operation LöschenBearbeiten

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 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   benannt sei.

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 wenn nötig wieder her.

Einfache FälleBearbeiten

Ist   rot, so hat es kein Kind. Und da alle Pfade, die durch den roten Knoten verliefen, nach seiner Löschung 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 ein Kind hat. Dieses ist dann zwangsläufig rot. Man färbt es schwarz und macht es 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 BlattesBearbeiten

Übrig bleibt der Fall, dass der Knoten   schwarz ist und kein Kind hat, also ein schwarzes Blatt ist.

Nach der Ersetzung von   bei   durch einen leeren Baum, 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 Knoten   lokalisiert hat, den Stapel struct node* Parents[] von dessen Vorfahren gebildet[10] und dessen Zeiger an die Löschfunktion übergeben hat. Ist   die Wurzel, dann zeigt der ebenfalls übergebene Zeiger struct node** 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   ohne Kind könnte dann wie folgt aussehen:[Anm. 7]

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

   if (pParent >= &Parents[0]) // R war nicht die Wurzel
    {
     P = *pParent; // Elter von R
     d = (R == P->right); // Kindesrichtung von R
     // Ersetze R bei seinem Elter P durch NULL:
     P->child[d] = N;
     goto Start_L;

Der Knoten   war nicht die Wurzel und, da er schwarz war, hatte er ein Geschwister, das (nicht-d)-Kind[Anm. 4] von  . Es ist nunmehr das Geschwister von   und sei mit   (wie engl. sibling) bezeichnet. Das d-Kind   (wie engl. close) von   ist der „nahe“ Neffe von   mit derselben Kindesrichtung; das andere Kind   (wie engl. distant) der „ferne“ Neffe.

Löschen: Erklärung der Symbole:
Zu den Symbolen, die bei der Einfügeoperation erklärt wurden, kommen zwei weitere:

  1. Zweimal   auf einer Zeile der Zusammenschau oder in einem Diagramm bedeutet beidesmal dieselbe Knotenfarbe, schwarz oder rot.
  2. Das Symbol   (Dreieck mit hellgrauer Ellipse an der Spitze) steht für den Wurzelknoten eines Rot-Schwarz-Teilbaums derselben Schwarztiefe wie die anderen durch Dreiecke dargestellten Teilbäume.
    • In der ersten Iterationsstufe hat eine Zeigervariable X auf einen solchen „Knoten“ den Wert NULL. (Der Nullzeiger ist Indikator für das Fehlen eines Knotens an dieser Stelle.)
    • Bei höheren Iterationsstufen ist X != NULL, und *X steht für einen schwarzen Knoten  , der die Wurzel eines Teilbaums mit Schwarztiefe ≥ 1 ist.

Löschen: Invariante der Schleife zur Überprüfung und Reparatur:

  • Die Anzahl der schwarzen Knoten auf den Pfaden, die nicht durch den   führen, ist ungeändert, und die Pfade durch   enthalten einen schwarzen Knoten weniger (engl. black violation).
    Deshalb wird   als der gerade betrachtete Problemknoten angesehen.
  • In der ersten Iterationsstufe fehlt   (ist N == NULL). In den höheren Iterationsstufen ist   schwarz.
  • Die Forderung !RR ist überall erfüllt.
Bedingung Fall
Rota-
tion
Zuwei-
sung
Ergebnis
Test
                   
  L0  
          L1  :=    ? ? ? ? L0
          L2     :=      ?   ? L3
          L3          
          L4     :=          L5
        L5           
Löschen: Zusammenschau der Fälle

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

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

  • die Bedingung, d. i. die Konstellation, die den Fall definiert,
  • die Fallnummer,
  • 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  . 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 zu 100 % 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 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 für den Problemknoten   in der Spalte Zuweisung, auch die Knoten   eindeutig bestimmt. Die Gruppe Ergebnis zeigt die Konstellation nach der Zuweisung, wobei Fragezeichen bei denjenigen Knoten stehen, auf deren Farbe es in den nächsten Abfragen ankommt.

Der Eintrag „L0“ kommt nur bei der Transformation_L1 vor und bedeutet ggf. 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äß § #Durchschnittliche und amortisierte Laufzeit ist der Rebalancierungsaufwand 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 drei Rotationen (von Fall L2 über L4 zu L5) erforderlich sind. Denn nach einer Rotation kommt kein neuer Iterationsschritt – die Rotationen befinden sich endrekursiv am Ende der letzten Iteration.

Im folgenden C-Beispielcode bestimmt die Kindesrichtung (im Beispielcode die Variable d) von   sowohl die nachfolgenden Rotationsrichtungen wie die Kindesrichtung der Neffen   und   von  .[13]

Die Diagramme bei den Fällen zeigen nur eine Kindesrichtung, und zwar ist bei der Operation Löschen der Problemknoten   immer links von  .

Der alte Problemknoten (in der linken Hälfte des Diagramms) hat eine blaue Kontur; und wenn die Operation nicht beendet ist, dann auch der neue (rechts).

Jeder Fall wird unter seiner Fallnummer erläutert und einschließlich Test (auf die ihn charakterisierende Bedingung) und Transformation durch ein Stück C-Code genau beschrieben.[14][Anm. 6]

     do // Beginn der (do while)-Schleife
      {
       // Bedingung_L0 trifft NICHT zu: pParent >= &Parents[0]:
       // ===> Es gibt den Elter P von N.
       P = *pParent;
       d = (N == P->right); // Kindesrichtung von N
 Start_L:
       S = P->child[!d]; // Geschwister von N
       if (S->color == RED)
         goto Fall_L2; // Bedingung_L2: S rot ===> P+C+D schwarz
       // S->color == BLACK:
       if (((R = S->child[!d]) != NULL) && (R->color == RED))
         goto Fall_L5; // der ferne Neffe (im Diagramm: D) ist rot
       if (((R = S->child[           d]) != NULL) && (R->color == RED))
         goto Fall_L4; // der nahe  Neffe (im Diagramm: C) ist rot
       // Beide Neffen sind == NULL (erste Iteration) oder schwarz (später).
       if (P->color == RED) // Bedingung_L3: P rot && C+S+D schwarz
         goto Fall_L3;

Löschen Fall L1: Der Elter   des Problemknotens   und das Geschwister   sind schwarz, ebenso die Kinder   und   von  , falls sie existieren.

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 zweite Bedingung der Schleifeninvariante mit nunmehr   als Problemknoten erfüllt.

       // Bedingung_L1: P+C+S+D schwarz
       // Transformation_L1:
       S->color = RED;
       N = P; // neuer Problemknoten (kann die Wurzel sein)
       // 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.
    } // end_if (pParent >= &Parents[0])

Löschen Fall L0: Der Problemknoten   ist die 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: pParent < &Parents[0] ===> N ist die neue Wurzel des Baums T.
   // (Nullzeiger, wenn der Baum jetzt leer ist.)
   // Da der zu löschende Knoten R ein schwarzer Knoten war,
   // verringert sich die Schwarztiefe des Baumes um 1.
   T->root = N;
   return; // Löschung fertiggestellt

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

Eine Rotation um  [Anm. 8] macht   zum Großelter von  , und zwar eine Linksrotation, wenn   linkes Kind (d. h. 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 L3, L4 oder L5 weitergehen kann – mit   als altem und neuem Problemknoten.[Anm. 6]

 Fall_L2:
   // Bedingung_L2: S rot && P+C+D schwarz
   // Transformation_L2:
   S->color = BLACK;
   P->color = RED;
   C = S->child[d]; // aufbewahren
   // rotate(P,d); // d-Rotation um Knoten P:
   P->child[!d] = C; // neuer Elter für C
   S->child[d] = 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
   S = C; // nach der Rotation: neues Geschwister von N

   if (((R = S->child[!d]) != NULL) && (R->color == RED))
     goto Fall_L5; // der ferne Neffe (im Diagramm: Teilbaum 4) ist rot
   if (((R = S->child[           d]) != NULL) && (R->color == RED))
     goto Fall_L4; // der nahe  Neffe (im Diagramm: Teilbaum 3) ist rot
   // Beide Neffen sind == NULL (erste Iteration) oder schwarz (später).
   // Weiter zu Fall_L3:

Löschen Fall L3: Der Elter   von   ist rot, aber sowohl das Geschwister   des Problemknotens   als auch dessen Kinder   und   sind schwarz, falls sie existieren.

Eine Invertierung 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: P rot && C+S+D schwarz
   // Transformation_L3:
   S->color = RED;
   P->color = BLACK;
   return; // Löschung fertiggestellt

Löschen Fall L4: Das Geschwister   von   ist schwarz, der nahe Neffe   rot, während der ferne Neffe  , falls er existiert, schwarz ist. Der im Diagramm rot-schwarz dargestellte Knoten   behält seine Farbe, rot oder schwarz.

Eine (nicht-d)-Rotation um  [Anm. 5] macht   zum Elter von   und zugleich zum Geschwister von  . Danach invertiert man die Farben von   und  . Dadurch werden die Pfade des Teilbaums   (s. Diagramm) so verändert, dass sie durch einen roten Knoten weniger und die Pfade durch den Knoten   durch einen mehr führen. Die Zahl der schwarzen Knoten auf diesen Pfaden bleibt jedoch gleich. Ferner hat nun   ein schwarzes Geschwister,  , dessen fernes Kind,  , rot ist, womit man zum Fall L5 weitergehen kann. Weder   noch   noch die Schwarztiefe werden durch diese Transformation beeinflusst.

 Fall_L4:
   // Bedingung_L4: S+D schwarz && C rot
   // Transformation_L4:
   C = S->child[d]; // aufbewahren
   C->color = BLACK;
   // rotate(S,!d); // (nicht-d)-Rotation um Knoten S:
   S->child[d] = C->child[!d]; // neuer Elter für Teilbaum 3
   C->child[!d] = S;
     // dadurch wird S zum fernen Neffen von N
   P->child[!d] = C;
   S->color = RED;
   S = C; // naher Neffe wird neues Geschwister von N (schwarz)
   // weiter zu Fall_L5:

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

Eine d-Rotation um  [Anm. 5] 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: S schwarz && ferner Neffe D von N rot
   // Transformation_L5:
   S->color = P->color;
   P->color = BLACK;
   // rotate(P,d); // d-Rotation um Knoten P:
   P->child[!d] = S->child[d]; // neuer Elter für Teilbaum 3
   S->child[d] = P;
   S->child[!d]->color = BLACK; // im Diagramm: D
   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
   return; // Löschung fertiggestellt
  } // Ende RBdelete2

HöhenbeweisBearbeiten

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.

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

 

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

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 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.[18] 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 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   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.[19]

Durchschnittliche und amortisierte LaufzeitBearbeiten

Der Rot-Schwarz-Baum bietet amortisiert konstante Rebalancierungskosten[20] und damit auch im Mittel konstante.

Anwendungen von (binären) Suchbäumen, die neben Sequenzen von Einfügungen und Löschungen auch Suchoperationen enthalten, sind asymptotisch durch die logarithmische Laufzeit der letzteren dominiert. Interessant ist der amortisiert konstante Modifikations-Aufwand jedoch, wenn der Suchbaum persistent gehalten werden soll, d. h. alle Versionen zugänglich bleiben sollen (s. a. en:Persistent data structure).[8][21]

Anzahlen von Rot-Schwarz-BäumenBearbeiten

 
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.

Beim Suchen und Traversieren ist wegen der identischen Verzweigungen 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_E2 und beim linken Baum alle vom Typ Transformation_E3 gefolgt von 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,

und zwar der mit roter Wurzel über

4 Einfügungen und 1 Löschung


und der mit schwarzer Wurzel über

6 Einfügungen und 3 Löschungen

und dies mit den oben beschriebenen Algorithmen für Einfügung und Löschung – jeweils bei geeignet gewählter Schlüsselfolge, die durch den Knoten mit blauer Kontur angegeben ist.

Verwandtschaft mit 2-3-4-BäumenBearbeiten

 
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-BaumBearbeiten

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 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 nur Rebalancierung – 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. 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[Anm. 10] für den AVL-Balance-Faktor. Während die Balance-Faktoren eines AVL-Baums direkt von seiner (graphentheoretischen) 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. § #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.[27] Diese „Top-Down-Strategie“[28] ist bspw. für nebenläufige und persistente Programmierung interessant.[Anm. 11][29]

So bleibt beim Einfügen der frisch eingefügte Knoten rot. Das bedeutet, dass eine zugehörige Suchfunktion im Abstieg den Baum entlang dem betroffenen Pfad (in logarithmischer Zeit) so vorbereiten kann, dass das endgültige Einfügen unmittelbar bei einem schwarzen Elter in Form eines roten Knotens geschehen oder eben 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äumenBearbeiten

Im Java Development Kit sind die Klassen TreeSet[30] und TreeMap[31] als Rot-Schwarz-Bäume implementiert. Sie stellen geordnete Mengen bzw. geordnete Dictionarys zur Verfügung.

Weitere BäumeBearbeiten

LiteraturBearbeiten

WeblinksBearbeiten

EinzelnachweiseBearbeiten

  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. Mehlhorn 2008 S. 154.
  6. so Ben Pfaff
  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 ist diese Forderung ohne mathematische Bedeutung und stört die Rekursivität. 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 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. a b 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 (Massachusetts) 2001, ISBN 0-262-03293-7, S. 273.
  10. a b 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.
  11. Ben Pfaff bringt außer der Variante des Textes auch eine Variante mit einem ersten eingefügten Knoten schwarzer Farbe.
  12. Die Kurzschreibweise mit dem Pfeil -> ist erklärt im Artikel Verbund (Datentyp).
  13. a b 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. 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.
  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. Sedgewick 2011 S. 444 Proof sketch
  19. 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 Anwendern gegenüber eher die Knotenzahl einschränken als die Baumhöhe, die nicht direkt wahrzunehmen ist.
    Die folgende Tabelle gibt zu jeder Knotenzahl   eine Höhenangabe   zurück, die von einem Rot-Schwarz-Baum mit   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   Bytes untergebracht werden können und ein Knoten mindestens 2 Kind-Zeiger à je 4 Bytes benötigt, kann bei Benutzerdaten von   Bytes pro Knoten ein Baum mit maximal   Knoten untergebracht werden; bei   sind das  . Wie die Tabelle zeigt, kann im erwähnten Adressraum die Höhe   durch einen Rot-Schwarz-Baum nicht überschritten werden.
    (Ist also der Stapelspeicher struct node* Parents[] für die Elter-Zeiger auf wenigstens   Einträge mit insgesamt   Bytes ausgelegt, so kann er unmöglich überlaufen.)
    Für einen Adressraum mit 8 Byte breiten Adressen und   Byte Benutzerdaten hat man   , so dass   bleibt und beim Einsatz von   Bytes für den Elter-Stapel NICHTS passieren kann. (Ben Pfaff hat #define RB_MAX_HEIGHT 128.)
    Umfang von Rot-Schwarz-Bäumen
    Anzahl Knoten   Höhe  
    100663293 50
    134217725 51
    201326589 52
    268435453 53
    402653181 54
    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.

  20. 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  .
    Damit ist der Aufwand pro Operation in einer solchen Sequenz in  , 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.
  21. Lightweight Java implementation of Persistent Red-Black Trees
  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. Red Black Trees. Archiviert vom Original am 27. September 2007.   Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/eternallyconfuzzled.com Abgerufen am 14. Oktober 2015. (Eternally Confuzzled)
  28. Mehlhorn 1988 S. 197–198.
  29. 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
  30. Java Class TreeSet auf docs.oracle.com
  31. Java Class TreeMap auf docs.oracle.com

AnmerkungenBearbeiten

  1. Diese Abschätzung ist scharf (s. § #Höhenbeweis) und für   wegen
     
    marginal genauer als
     .
  2. a b Definitionsgemäß hat ein schwarzer Knoten eine Schwarzhöhe ≥ 1. Folglich ist verabredungsgemäß X == NULL für einen schwarzen „Knoten“   der Schwarzhöhe 0. Daher gilt für eine Knotenvariable struct node *X der Schwarzhöhe 0 die Äquivalenz
    X != NULL               *X ist ein roter Knoten.
  3. 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   Schlüssel tragenden Knoten braucht man   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 einen völlig unspezifischen Gegenwert an Information.
  4. a b Für d ∈ {LEFT,RIGHT} spiegelt die logische Negation
    nicht-d   ≡   !d
    die Richtung LEFT   RIGHT.
    Bei den Farben findet sich für RED ≡ !BLACK und BLACK ≡ !RED der Ausdruck „Invertierung“.
  5. a b c d In der ersten Iterationsstufe ist der Teilbaum   leer. Wenn die Knoten mit Elterzeiger implementiert sind, dann ist der Elterzeiger dieses Teilbaums bei allen Iterationsstufen außer der ersten anzupassen.
  6. a b c Man beachte die in der Programmiersprache C festgelegte Art der Auswertung
    der Disjunktion (U == NULL) || (U->color == BLACK)
    resp.
    der Konjunktion (R != NULL) && (R->color == RED),

    die im Fall U == NULL resp. R == NULL die zweite Bedingung U->color == BLACK resp. R->color == RED nicht berechnet, sondern sofort zum else-Zweig verzweigt.
    Für eine einen Knoten darstellende Programmvariable U resp. R bedeutet der Wert NULL verabredungsgemäß das „Fehlen“ des dargestellten „Knotens“. Das Fehlen entspricht einer Baumhöhe 0, woraus Schwarzhöhe 0 folgt.
    Schwarzhöhe 0 kommt aber nur in der ersten Runde der Reparaturschleife vor; bei den höheren Iterationstufen sind die Schwarzhöhen aller beteiligten Knoten positiv. Die Disjunktion resp. Konjunktion lässt sich somit durch Entrollen der ersten Iteration (Herausziehen aus der Schleife) sowohl dort wie in den höheren Iterationen vermeiden.

  7. Um der Kürze der Aufschreibung willen wird im Beispielcode einige Male goto verwendet. Es ist leicht, dies durch Verdoppelung des Codes zu vermeiden.
  8. Wenn die Knoten mit Elterzeiger implementiert sind, dann ist der Elterzeiger des Knotens   in allen Iterationen anzupassen.
  9. Diese Minimalbäume spielen bei den Rot-Schwarz-Bäumen eine ähnliche Rolle wie die Fibonacci-Bäume bei den AVL-Bäumen.
  10. oder auch nur 1 Bit (s. Implementierung)
  11. 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.
  Dieser Artikel wurde am 5. November 2005 in dieser Version in die Liste der lesenswerten Artikel aufgenommen.