Dies ist ein als lesenswert ausgezeichneter Artikel.

Rot-Schwarz-Baum

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
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 Schlüssel garantiert. Rot-Schwarz-Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben,[1] welcher sie symmetric binary B-trees nannte. Der heutige Name geht auf Leonidas J. Guibas und Robert Sedgewick zurück, die 1978 die rot-schwarze Farbkonvention einführten.[2] Die schnellen Zugriffszeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente (meist Paare vom Typ (Schlüssel,Wert)) werden durch zwei Forderungen erreicht, die die Balance des Baums in einer Weise definieren, dass die Höhe eines Baums mit 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.

Definition[Bearbeiten | Quelltext bearbeiten]

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 Baumhöhe 4 und der Schwarzhöhe 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 zum Pfadende ist um genau den Knoten kürzer.

Weitere Definitionen und Folgerungen[Bearbeiten | Quelltext bearbeiten]

Die auf allen Pfaden von Pfadende zu Wurzel gleiche Anzahl schwarzer Knoten wird die Schwarzhöhe[5][6] genannt: des Baums, aber auch seiner Wurzel. Nach dieser Definition ist ein (echter) Knoten der Schwarzhöhe 0 ein rotes Blatt (seine Baumhöhe ist 1) wie bspw. die Knoten im Beispielbaum. Ein (echter) schwarzer Knoten hat eine Schwarzhöhe ≥ 1. Die roten Knoten aber auch die schwarzen Knoten haben Schwarzhöhe 1. Die schwarzen Knoten haben Baumhöhe 2, die Knoten Baumhöhe 1, und 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 Schwarzhöhe 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 ist – 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

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.
Derselbe Rot-Schwarz-Baum – mit NIL-Knoten
(Baum- und Schwarzhöhe sind 4 und 2 – wie oben)
Sehr verbreitet in der Literatur über Rot-Schwarz-Bäume ist die nebenstehende und im Artikel Binärer Suchbaum in dessen Abb. 1B gezeigte Sichtweise, bei der – ebenfalls knotenorientiert – die die Schlüssel tragenden Knoten als intern angesehen werden, dem Baum aber zusätzliche Knoten, so genannte „NIL-Knoten“, als externe Blätter angeheftet sind, die an den Pfadenden für die (randlosen) Intervalle (engl. auch „missing nodes[8]) zwischen den Schlüsseln stehen. Die Darstellung mit NIL-Knoten bringt das eine Pfadende beim Knoten ähnlich deutlich heraus wie die paarigen Pfadenden bei den Knoten Gleichwohl lassen sich die NIL-Knoten sowohl als unterschiedslose Nullzeiger (so im Text) wie als unterschiedslose Wächterknoten implementieren. Werden die NIL-Knoten jedoch als individuelle Knoten aufgefasst, dann kommt für sie 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.
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. 2]

Datenstruktur[Bearbeiten | Quelltext bearbeiten]

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;            // ROT oder SCHWARZ
   ...                    // Benutzer-Daten (z.B. Schlüssel, Wert)
  } ;

 #define LEFT    false
 #define RIGHT   true
 #define left    child[LEFT]  // -> linker  Kindknoten
 #define right   child[RIGHT] // -> rechter Kindknoten
 #define ROT     false
 #define SCHWARZ 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 eines Knotens (einen sog. „Nullknoten“) an dieser Stelle des Baums bedeuten (der Knoten gilt als unecht). M. a. W.: der von einem NULL-Knoten gewurzelte Teilbaum ist leer.

Wegen der 1:1-Beziehung zwischen einem Knoten und dem von ihm gewurzelten Teilbaum wird im Beispielcode eine Variable unterschiedslos als Zeiger auf den Knoten wie auf den Teilbaum verwendet.

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.

Navigationsoperationen[Bearbeiten | Quelltext bearbeiten]

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 unterstützt eine Art „direkten Zugriff“ (im Gegensatz zum sequentiellen Zugriff der Traversierung) und wird in der Regel als vorausgehende Operation bei den Modifikationsoperationen (Einfügen oder Löschen) zum Auffinden des betroffenen Knotens eingesetzt.

Das Suchen setzt eine totale Quasiordnung auf der Menge der Schlüssel voraus, die am flexibelsten durch eine Vergleichsfunktion realisiert wird. Wenn Duplikate im Baum erwünscht sind, dann empfiehlt sich eine leicht abgewandelte Suchfunktion.

Operation Einfügen[Bearbeiten | Quelltext bearbeiten]

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 steht.

Im unten stehenden Beispielcode wird angenommen, dass diese Richtung, die das letzte Ungleich-Ergebnis einer Suche nach dem Schlüssel von reflektiert, im Funktionsparameter d ∈ {LEFT,RIGHT} übergeben wird.[10] Ferner wird angenommen, dass diese Suchfunktion den Stapel struct node* Parents[] der Vorfahren von gebildet hat.[11] 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 Schwarzhöhe des Baumes erhalten bleibt.[12]

Die darauf folgenden Aktionen überprüfen, ob die Rot-Schwarz-Balance im Baum eingehalten ist und stellen sie wenn erforderlich wieder her. Diese Reparatur wird als „Rebalancierung“ (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:[13]

 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 = ROT;
   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: Die Schleife zur Überprüfung und Reparatur des Baums steigt vom roten Blatt zur Wurzel auf. Ihre Invariante ist:

  • Zu Beginn jedes Iterationsschritts ist der Knoten rot.
  • Die Forderung S#= gilt für den ganzen Baum.
  • Die Forderung !RR gilt für alle Paare (Knoten←Elter) im Baum mit höchstens einer Ausnahme – beim Paar (). Dies wird als „Rot-Verletzung“ (engl. red violation) angesehen, welche zum „Problemknoten“ macht.
    Gilt !RR auch dort, entweder weil nicht existiert (Fall E0) oder schwarz ist (Fall E1), dann ist der Baum in Rot-Schwarz-Form.

Einfügen: Erklärung der Symbole:

  1. In den Zusammenschauen und in den Diagrammen stellt BlackNode.svg einen (echten) schwarzen und RedNode.svg einen (echten) roten Knoten dar.
  2. In den Diagrammen stellen die nummerierten Dreiecke TriangleSubtree.svg !RR-konform bei ihrem Elter angebundene Rot-Schwarz-Teilbäume dar. Diese Teilbäume haben alle dieselbe Schwarzhöhe, die
    1. mit der Iterationsstufe wächst und in höheren Iterationsstufen ≥ 1 ist.
    2. in der ersten Iterationsstufe 0 ist.
      Dann besteht der Teilbaum entweder
      • aus einem roten Blatt (der Baumhöhe 1) oder
      • er ist leer, in welch letzterem Fall der „Knoten“ auch als unecht oder als Nullknoten bezeichnet wird. Dann ist sein Zeigerwert X == NULL, und dieser Wert weniger wichtig als der Ort, wo dieser Wert in der Datenstruktur steht. Dieser Ort gibt dann die graphentheoretischen Beziehungen zu den anderen Elementen des Baums an: Ohne selbst einen Knoten zu repräsentieren, kann er in Kindesbeziehung, und damit auch in Geschwister- und Onkelbeziehung zu anderen Knoten stehen.
        Seine Baumhöhe und Schwarzhöhe gelten beide als 0, und Farbe ist ihm auch nicht zugeordnet. In der vorgeschlagenen Implementierung hat er einen Elter (wenn er die Wurzel ist, den Baum als unechten Elter), aber niemals einen Zeiger zum Elter.
  3. Für Teilbäume, die durch das Symbol TriangleTop.svg (Dreieck mit grauer Ellipse an der Spitze) dargestellt sind, gilt dasselbe wie bei den Dreiecken TriangleSubtree.svg.
    Zusätzlich gilt:
    1. Wenn der Teilbaum TriangleTop.svg existiert (d. h. die auf ihn zeigende Zeigervariable X != NULL ist), dann ist sein Wurzelknoten *X[14] schwarz (im Unterschied zu TriangleSubtree.svg, bei dem die Farbe nicht festgelegt ist) und damit seine Schwarzhöhe ≥ 1.
    2. Ist der Zeigerwert X == NULL (so in der ersten Iterationsstufe), dann steht TriangleTop.svg für den leeren Teilbaum.
Bedingung Fall
Rota-
tion
Zuwei-
sung
Ergebnis
Test
x x
RedNode.svg E0 RedNode.svg
RedNode.svg BlackNode.svg E1 RedNode.svg BlackNode.svg
RedNode.svg RedNode.svg E2 RedNode.svg BlackNode.svg
RedNode.svg RedNode.svg BlackNode.svg RedNode.svg E3 := RedNode.svg ? ? ? E0
RedNode.svg RedNode.svg BlackNode.svg TriangleTop.svg i E4 := RedNode.svg RedNode.svg BlackNode.svg TriangleTop.svg o E5
RedNode.svg RedNode.svg BlackNode.svg TriangleTop.svg o E5 RedNode.svg BlackNode.svg RedNode.svg TriangleTop.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 (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_E3 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 E5 nach Fall E4. 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 E4 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.[15]

Im folgenden Beispielcode zur Operation Einfügen hält die Variable d die Kindesrichtung des Knotens Die Diagramme zeigen immer als linkes Kind.

Der alte Problemknoten ( in der linken Spalte eines Diagramms) hat eine blaue Kontur; und wenn die Operation nicht beendet ist, dann auch der neue (in der rechten Spalte).

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.[16]

     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:

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

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

       if (P->color == SCHWARZ) // 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 = SCHWARZ;
         // Da P ROT war,
         // erhöht sich die Schwarzhöhe des Baumes um 1.
         return; // Einfügung fertiggestellt
        }

Im Folgenden ist der rote Elter 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).

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

Einfügen Fall E3

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_E3 wird das potentielle Problem „Rot-Verletzung“ um zwei Baum-Ebenen (eine Schwarz-Ebene) nach oben verschoben mit als dem neuen Problemknoten.[Anm. 3]

       G = *(--pParent);    // Der Großelter G von N existiert.
       d = (P == G->right); // Kindesrichtung von P
       if ((U = G->child[!d]) == NULL || U->color == SCHWARZ)
         goto Test_E4;      // Der Onkel U ist SCHWARZ.
       // Bedingung_E3: N+P+U ROT
       // Transformation_E3:
       P->color = SCHWARZ;
       U->color = SCHWARZ;
       G->color = ROT;
       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

Einfügen Fall E4: 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 E4

Eine entsprechende Rotation um [Anm. 4] 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 E5 mit als dem neuen Problemknoten.

 Test_E4:
   if (N != P->child[d]) // Bedingung_E4: N ist innerer Enkel
                         //               && N+P ROT && U SCHWARZ
    {
     // Transformation_E4:
     // rotate(P,d); // d-Rotation um P:
     P->child[!d] = N->child[d]; // neuer Elter für Teilbaum 2
     N->child[d] = P;
     G->child[d] = N;
 
     U = N; // aufbewahren
     N = P; // neuer Problemknoten (ROT) und äußerer Enkel
     P = U; // neuer Elter von N (ROT)
    }

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

Einfügen Fall E5

Eine (nicht-d)-Rotation um [Anm. 4] 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_E5: N ist äußerer Enkel && N+P ROT && U SCHWARZ
   // Transformation_E5:
   // rotate(G,!d); // (nicht-d)-Rotation um G:
   G->child[d] = P->child[!d]; // neuer Elter für Teilbaum 3
   P->child[!d] = G;
   if (--pParent >= &Parents[0])
    {
     // Ersetze G bei seinem Elter durch P:
     U = *pParent;
     U->child[G == U->right] = P;
    }
   else // G war die Wurzel
     T->root = P; // P ist die neue Wurzel
 
   P->color = SCHWARZ;
   G->color = ROT;
   return; // Einfügung fertiggestellt
  } // Ende RBinsert1

Operation Löschen[Bearbeiten | Quelltext bearbeiten]

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.[17] 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 stehe für einen Nullknoten. 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älle[Bearbeiten | Quelltext bearbeiten]

Ist rot, so hat es kein Kind. Und da alle Pfade, die durch den roten Knoten verliefen, nach seiner Entfernung aus dem Baum durch einen roten Knoten weniger verlaufen, ändert sich an der Anzahl der schwarzen Knoten nichts, womit die Forderung S#= erfüllt bleibt.

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, so dass Forderung S#= erfüllt bleibt.

Das Löschen eines schwarzen Blattes[Bearbeiten | Quelltext bearbeiten]

Ü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 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[11] 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. 5]

 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. 6] 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: Die Schleife zur Überprüfung und Reparatur des Baums steigt vom unechten Blatt zur Wurzel auf. Ihre Invariante ist:

  • Die Anzahl der schwarzen Knoten auf den Pfaden, die nicht durch führen, ist ungeändert, und die Pfade durch enthalten einen schwarzen Knoten weniger (sog. „Schwarz-Verletzung“, engl. black violation), weshalb als der Problemknoten betrachtet wird.
  • In der ersten Iterationsstufe ist leer (sein Zeigerwert N == NULL), in den höheren Iterationsstufen ist schwarz (daher die Kennzeichnung durch das Symbol TriangleTop.svg).
  • Die Forderung !RR ist überall erfüllt.

Löschen: Erklärung der Symbole:
Zu den Symbolen, die bei der Einfügeoperation erklärt wurden, kommt ein weiteres:

  1. Zweimal RedOrBlackNode.svg auf einer Zeile der Zusammenschau oder in einem Diagramm bedeutet beidesmal dieselbe Knotenfarbe, schwarz oder rot.
Bedingung Fall
Rota-
tion
Zuwei-
sung
Ergebnis
Test
TriangleTop.svg L0 TriangleTop.svg
TriangleTop.svg BlackNode.svg TriangleTop.svg BlackNode.svg TriangleTop.svg L1 := TriangleTop.svg ? ? ? ? L0
TriangleTop.svg BlackNode.svg BlackNode.svg RedNode.svg BlackNode.svg L2 := TriangleTop.svg RedNode.svg ? BlackNode.svg ? L3
TriangleTop.svg RedNode.svg TriangleTop.svg BlackNode.svg TriangleTop.svg L3 TriangleTop.svg BlackNode.svg TriangleTop.svg RedNode.svg TriangleTop.svg
TriangleTop.svg RedOrBlackNode.svg RedNode.svg BlackNode.svg TriangleTop.svg L4 := TriangleTop.svg RedOrBlackNode.svg BlackNode.svg RedNode.svg L5
TriangleTop.svg RedOrBlackNode.svg BlackNode.svg RedNode.svg L5 TriangleTop.svg BlackNode.svg RedOrBlackNode.svg BlackNode.svg
Löschen: Zusammenschau der Fälle

Löschen: Zusammenschau der Fälle[18][19]

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 Beispielcode bestimmt die Kindesrichtung (Variable d) von sowohl die nachfolgenden Rotationsrichtungen wie die Kindesrichtung der Neffen und von .[15]

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 Spalte eines Diagramms) hat eine blaue Kontur; und wenn die Operation nicht beendet ist, dann auch der neue (in der rechten Spalte).

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.[16][Anm. 3]

     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 == ROT)
         goto Fall_L2; // Bedingung_L2: S ROT ===> P+C+D SCHWARZ
       // S ist SCHWARZ:
       if (((D = S->child[!d]) != NULL) && (D->color == ROT))
         goto Fall_L5; // der ferne Neffe D ist ROT
       if (((C = S->child[ d]) != NULL) && (C->color == ROT))
         goto Fall_L4; // der nahe  Neffe C ist ROT
       // Beide Neffen sind == NULL (erste Iteration) oder SCHWARZ (später).
       if (P->color == ROT)
         goto Fall_L3; // P ROT && C+S+D SCHWARZ <==> Bedingung_L3

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

Löschen Fall L1

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 = ROT;
       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 Schwarzhöhe des Baumes um 1.
   T->root = N;
   return; // Löschung fertiggestellt

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

Löschen Fall L2

Eine Rotation um [Anm. 7] 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. 3]

 Fall_L2:
   // Bedingung_L2: S ROT && P+C+D SCHWARZ
   // Transformation_L2:
   S->color = SCHWARZ;
   P->color = ROT;
   C = S->child[d]; // aufbewahren
   // rotate(P,d); // d-Rotation um Knoten P:
   P->child[!d] = C; // neuer Elter von 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 (SCHWARZ)
   if (((D = S->child[!d]) != NULL) && (D->color == ROT))
     goto Fall_L5; // der ferne Neffe D ist ROT
   if (((C = S->child[ d]) != NULL) && (C->color == ROT))
     goto Fall_L4; // der nahe  Neffe C ist ROT
   // Beide Neffen sind == NULL (erste Iteration) oder SCHWARZ (später).
   // P ROT && C+S+D SCHWARZ <==> Bedingung_L3
   // 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.

Löschen Fall L3

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 = ROT;
   P->color = SCHWARZ;
   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.

Löschen Fall L4

Eine (nicht-d)-Rotation um [Anm. 4] 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 Schwarzhöhe werden durch diese Transformation beeinflusst.

 Fall_L4:
   // Bedingung_L4: S+D SCHWARZ && C ROT
   // Transformation_L4:
   // 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;
 
   C->color = SCHWARZ;
   S->color = ROT;
   D = S; // nach der Rotation: neuer ferner Neffe
   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.

Löschen Fall L5

Eine d-Rotation um [Anm. 4] 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 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 && D ROT
   // Transformation_L5:
   // rotate(P,d); // d-Rotation um Knoten P:
   P->child[!d] = S->child[d];    // neuer Elter für Teilbaum 3
   S->child[d] = P;
   if (--pParent >= &Parents[0])  // P war nicht die Wurzel
    {
     // Ersetze P bei seinem Elter durch S:
     N = *pParent;
     N->child[P == N->right] = S;
    }
   else
     T->root = S; // S ist die neue Wurzel
 
   S->color = P->color;
   P->color = SCHWARZ;
   S->child[!d]->color = SCHWARZ; // im Diagramm: D
   return; // Löschung fertiggestellt
  } // Ende RBdelete2

Höhenbeweis[Bearbeiten | Quelltext bearbeiten]

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. 8]

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 Schwarzhöhe zu erreichen. Seine Einfärbung hat also unten beim Blatt mit Rot zu beginnen, und sich in der Folge nach oben bis zur Wurzel mit Schwarz und Rot streng abwechselnd fortzusetzen. Außerhalb dieses die Baumhöhe definierenden Pfades hat er nur schwarze Knoten.[20] 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 Schwarzhöhe ; der niedrigere ist ein vollständiger Binärbaum mit Höhe = Schwarzhöhe 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 rechte 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.[21]

Durchschnittliche und amortisierte Laufzeit[Bearbeiten | Quelltext bearbeiten]

Der Rot-Schwarz-Baum bietet amortisiert konstante Rebalancierungskosten[22] 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][23]

Anzahlen von Rot-Schwarz-Bäumen[Bearbeiten | Quelltext bearbeiten]

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.

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

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

Zwar wird in einem reinen Einfügeszenario von den 3 möglichen Bäumen mit 3 Knoten (Schlüsseln) nur der eine Baum mit schwarzer Wurzel und 2 roten Kindern (der linke in der Abbildung) gebildet. Bezieht man jedoch Löschungen mit ein, dann kommen die zwei anderen Rot-Schwarz-Bäume (rechts in der Abbildung) hinzu,

4 Einfügungen und 1 Löschung

und zwar der mit roter Wurzel über

4 Einfügungen und 1 Löschung


6 Einfügungen und 3 Löschungen

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äumen[Bearbeiten | Quelltext bearbeiten]

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.[24][25]

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 (engl. split) und Verschmelzen (engl. 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.[26]

Vergleich mit AVL-Baum[Bearbeiten | Quelltext bearbeiten]

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.[27][28]

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 Knotenzahl ist. Konsequenterweise ist auch die Worst-Case-Höhe des AVL-Baums kleiner als die des Rot-Schwarz-Baums, und zwar asymptotisch um den Faktor (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 das Rot-Schwarz-Attribut gegenüber 2 Bits[Anm. 9] 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 regelkonforme Einfärbungen in einem reinen Einfügeszenario nicht bewirkt werden können.

Eine Folge dieser etwas größeren Freiheitsgrade ist, dass im Rot-Schwarz-Baum die für die Einfügung oder Löschung erforderlichen Farbänderungen und Rotationen schon während des Suchvorgangs – also beim Abstieg – vorgenommen werden können.[29] Diese „Top-Down-Strategie“[30] ist bspw. für nebenläufige und persistente Programmierung interessant.[Anm. 10][31]

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

Verwendung von Rot-Schwarz-Bäumen[Bearbeiten | Quelltext bearbeiten]

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

Weitere Bäume[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Rudolf Bayer: Symmetric Binary B-Trees. Data Structure and Maintenance Algorithms. In: Acta Informatica. 1, 1972, S. 290–306. doi:10.1007/BF00289509.
  2. Leo J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. In: IEEE Computer Society (Hrsg.): Proceedings of the 19th Annual Symposium on Foundations of Computer Science. 1978, S. 8–21.
  3. Der Text folgt Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees. Zu anderen Varianten der Forderungen s. die Anmerkung NIL-Knoten.
  4. bei Ben Pfaff non-branching node
  5. Bei Ben Pfaff ist die Schwarzhöhe (engl. black-height) eines Knotens die einheitliche Anzahl schwarzer Knoten auf allen Pfaden zu den Pfadenden im von ihm gewurzelten Teilbaum.
  6. Mehlhorn 2008 S. 155 färbt die Kanten rot/schwarz und zählt als Schwarztiefe (engl. black depth) eines Knotens die Zahl der schwarzen Kanten von ihm zur Wurzel.
  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. Dabei ist d == LEFT             Schlüssel von < Schlüssel von .
    S. a. Binärer Suchbaum#Suchen, wenn Duplikate zulässig.
  11. 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.
  12. Ben Pfaff bringt außer der Variante des Textes auch eine Variante mit einem ersten eingefügten Knoten schwarzer Farbe.
  13. Die Kurzschreibweise mit dem Pfeil -> ist erklärt im Artikel Verbund (Datentyp).
  14. Der Stern * dereferenziert (in der Programmiersprache C) den Zeiger X. Also ist *X das Objekt (hier: der Knoten), auf den der Zeiger X zeigt, jedenfalls wenn X != NULL.
  15. 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).
  16. 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.
  17. 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)
  18. Die Aufteilung entspricht Roger Whitney.
  19. 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).
  20. Sedgewick 2011 S. 444 Proof sketch
  21. Als eine Datenstruktur, die im homogenen Arbeitsspeicher (Hauptspeicher) untergebracht ist, ist der Rot-Schwarz-Baum durch dessen Größe beschränkt, also auch die Höhe des Baums und die Längen der Pfade von Blatt zu Wurzel. Der Programmierer wird seinen Anwendern gegenüber eher die Knotenzahl einschränken als die Baumhöhe, die für den Anwender eher zufälliger Natur ist und ihn normalerweise nicht interessiert.
    Die folgende Tabelle gibt zu jeder Knotenzahl 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 (Schlüssel + Wert) von Bytes pro Knoten ein Baum mit maximal Knoten untergebracht werden; bei sind das Wie die Tabelle zeigt, kann im 32-Bit-Adressraum die Höhe durch einen Rot-Schwarz-Baum unmöglich überschritten werden.
    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 dieser nicht überlaufen kann.
    Umfang von Rot-Schwarz-Bäumen
    Anzahl Knoten Baumhöhe Nutzlänge
    32-Bit-Adressen
    33554429 47 120
    50331645 48 77
    67108861 49 56
    100663293 50 34
    134217725 51 24
    201326589 52 13
    268435453 53 8
    402653181 54 2
    536870909 55 0
    64-Bit-Adressen
    72057594037927933 109 240
    108086391056891901 110 154
    144115188075855869 111 112
    216172782113783805 112 69
    288230376151711741 113 48
    432345564227567613 114 26
    576460752303423485 115 16
    864691128455135229 116 5
    1152921504606846973 117 0

    Mit den Bezeichnungen im Text ist eine Maßgabe, die so knapp wie möglich unterhalb der Knotenzahl des nächstgrößeren Minimalbaums bleibt. Ist der Speicherbedarf für alle Knoten gleich, können die Benutzerdaten pro Knoten maximal

    im 32-Bit-Adressraum (4 Bytes/Adresse)
    im 64-Bit-Adressraum (8 Bytes/Adresse)

    Bytes umfassen.

    Fazit

    Ist der Stapelspeicher struct node* Parents[] für die Elter-Zeiger bei einem 32-Bit-Adressraum auf wenigstens Einträge mit insgesamt Bytes ausgelegt, so kann er unmöglich überlaufen.
    Dasselbe gilt bei einem 64-Bit-Adressraum für und einem Elter-Stapel der Größe Bytes.
    Bevor nämlich in beiden Fällen der Elter-Stapel überläuft, ist der Adressraum schon geplatzt.
    Ben Pfaff hat #define RB_MAX_HEIGHT 128.

  22. 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.
  23. Lightweight Java implementation of Persistent Red-Black Trees
  24. Mehlhorn 1988 S. 193
  25. 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).
  26. Mehlhorn 1988 S. 187
  27. 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).
  28. 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.
  29. Red Black Trees. Abgerufen am 14. Oktober 2015. (Eternally Confuzzled)
  30. Mehlhorn 1988 S. 197–198.
  31. 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
  32. Java Class TreeSet auf docs.oracle.com
  33. Java Class TreeMap auf docs.oracle.com

Anmerkungen[Bearbeiten | Quelltext bearbeiten]

  1. Diese Abschätzung ist scharf (s. § #Höhenbeweis) und für wegen
    marginal genauer als
    .
  2. Werden nämlich die NIL-Knoten als minimale Rot-Schwarz-Knoten implementiert, so brauchen sie Speicher für zwei Kindzeiger, ggf. einen Elterzeiger, das Feld für die Farbe und ein Erkennungsfeld für die Eigenschaft »NIL-Knoten«. Bei 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 das Aufzeichnen und Pflegen von Informationen, die für die nachfolgenden Algorithmen nicht gebraucht werden oder sich auf sehr einfache Weise aus den anderen Informationen ableiten lassen.
  3. a b c Man beachte die in der Programmiersprache C festgelegte Art der Auswertung der
      Disjunktion:       (X == NULL)
    || (X->color == SCHWARZ)
    bzw. der
      Konjunktion:       (X != NULL)
    && (X->color == ROT)

    die im Fall X == NULL die zweite Bedingung X->color == SCHWARZ resp. R->color == ROT nicht auswertet, sondern sofort zum else-Zweig verzweigt. Im Beispielcode sind die entsprechenden Zeilen gelb hinterlegt.
    Zusätzliche Bemerkung:
    Die Schwarzhöhe 0 kommt nur in der ersten Iterationsstufe der Reparaturschleife vor; bei den höheren Iterationsstufen ist die Schwarzhöhe aller besuchten Knoten positiv. Deshalb ist die Abfrage auf (X != NULL) nur bei Schwarzhöhe 0, also in der ersten Iterationsstufe relevant, und bei den höheren Iterationsstufen nur die Abfrage auf color. Wenn jetzt die erste Iteration aus der Schleife herausgezogen wird, dann kann sich die Abfrage dort auf die Existenz des Knotens beschränken und in den höheren Iterationen auf seine Farbe.

  4. a b c d In der ersten Iterationsstufe ist der Teilbaum leer. Wenn die Knoten mit Elterzeiger implementiert werden, dann ist nach der Rotation der Elterzeiger dieses Teilbaums bei allen Iterationsstufen außer der ersten anzupassen.
  5. Um der Kürze der Aufschreibung willen wird im Beispielcode einige Male goto verwendet. Es ist leicht, dies durch Verdoppelung des Codes zu vermeiden.
  6. Wegen der Gleichsetzungen LEFT ≡ false ≡ 0 und RIGHT ≡ true ≡ 1 spiegelt die logische Negation
    nicht-d   ≡   !d
    die Richtung LEFT RIGHT.
    Im Kontext der Farben spricht man bei ROT :≡ !SCHWARZ und SCHWARZ :≡ !ROT von „Invertierung“.
  7. Wenn die Knoten mit Elterzeiger implementiert werden, dann ist der Elterzeiger des Knotens in allen Iterationen anzupassen, da die Schwarzhöhe von auch in der ersten Iteration ≥ 1 ist.
  8. Diese Minimalbäume spielen bei den Rot-Schwarz-Bäumen eine ähnliche Rolle wie die Fibonacci-Bäume bei den AVL-Bäumen.
  9. oder auch nur 1 Bit (s. AVL-Implementierung)
  10. 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.