Rot-Schwarz-Baum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Rot-Schwarz-Baum (engl. red–black tree oder RB tree) ist in der Informatik eine vom binären Suchbaum abgeleitete Datenstruktur, 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 Leo J. Guibas und Robert Sedgewick zurück, die 1978 die rot-schwarze Farbkonvention einführten.[2] Die schnellen Zugriffszeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente werden durch drei Forderungen erreicht, die zusammen garantieren, dass ein Rot-Schwarz-Baum immer balanciert ist, wodurch die Höhe eines Rot-Schwarz-Baumes mit n Werten nie größer als 2 \log_2(n+2)-2 wird. Somit können die wichtigsten Operationen in Suchbäumen – suchen, einfügen und löschen – garantiert in O(log n) ausgeführt werden.

Definition[Bearbeiten]

Zusätzlich zu den Eigenschaften des binären Suchbaums hat jeder Knoten des Rot-Schwarz-Baums ein weiteres Attribut, genannt Farbe, mit zwei Werten, genannt rot und schwarz. Diese Einfärbung hat die drei folgenden Forderungen zu erfüllen:[3]

  1. Alle Blatt-Knoten (NIL) sind schwarz.
  2. Ist ein Knoten rot, so sind beide Kinder schwarz.
  3. Jeder Pfad von einem gegebenen Knoten zu seinen Blattknoten enthält die gleiche Anzahl schwarzer Knoten.
Rot-Schwarz-Baum der Höhe 4 und der Schwarztiefe 2

Letztere einheitliche Anzahl schwarzer Knoten auf den Pfaden wird die Schwarztiefe des Baums genannt. Dabei sei in diesem Artikel der auf jedem Pfad vorhandene eine und immer schwarze NIL-Knoten nicht mitgezählt, ebenso wenig wie bei der Baumhöhe.

Durch diese drei Forderungen[4] wird die wichtigste Eigenschaft von Rot-Schwarz-Bäumen sichergestellt: Die Anzahl der Knoten auf einem längsten Pfad von der Wurzel zu einem Blatt ist nie mehr als doppelt so hoch wie die Anzahl der Knoten eines kürzesten Pfades von der Wurzel zu einem Blatt. Hierdurch ist ein Rot-Schwarz-Baum immer annähernd balanciert. Das ist für die Operationen suchen, einfügen und löschen wichtig, da deren Laufzeitkosten proportional zur Höhe des Baumes sind. Da die Höhe eines Rot-Schwarz-Baumes dadurch, dass er annähernd balanciert ist, minimiert wird, wird somit ebenfalls die Laufzeit der oben genannten Operationen minimiert. Somit kann man für Rot-Schwarz-Bäume eine obere Schranke für die Laufzeit der Operationen suchen, einfügen und löschen garantieren.

Um zu verstehen, wie diese drei Forderungen die Höhe nach oben begrenzen, reicht es, sich zu verdeutlichen, dass aufgrund der zweiten Forderung auf keinem Pfad zwei rote Knoten aufeinander folgen dürfen, weswegen es auf keinem Pfad mehr rote als schwarze Knoten geben kann, während auf dem kürzesten Pfad im Extremfall nur schwarze Knoten vorhanden sind. Da die dritte Forderung jedoch festlegt, dass die Anzahl der schwarzen Knoten auf allen Pfaden gleich sein muss, kann der Pfad, auf dem sich jeweils ein roter mit einem schwarzen Knoten abwechselt, maximal doppelt so lang sein wie der Pfad, auf dem nur schwarze Knoten sind. Einen formalen Beweis für diese Eigenschaft des Rot-Schwarz-Baumes findet man unter Höhenbeweis weiter unten im Artikel.

Anmerkung: Dieser Artikel nimmt die im Artikel Binärer Suchbaum in dessen Abb. 2 aufgezeigte und bei Rot-Schwarz-Bäumen außerordentlich verbreitete Sichtweise ein, bei der die inneren Knoten die Schlüssel tragen („knotenorientierte Speicherung“) und die (externen) Blätter als Platzhalter für die Intervalle zwischen den Schlüsseln fungieren (siehe hierzu auch die Abb. mit dem Beispielbaum). Hierbei haben die Schlüssel tragenden Knoten immer genau zwei Kinder, und die Blätter ohne Suchschlüssel (sog. NIL-Blätter) tragen die Farbe schwarz. Diese Sichtweise erlaubt, mit weniger Fallunterscheidungen auszukommen, und vereinfacht die Beschreibung des Algorithmus. Sie präjudiziert aber die Implementierung nicht wirklich.

Operationen[Bearbeiten]

Suchen[Bearbeiten]

Die Suchoperation erben Rot-Schwarz-Bäume von den allgemeinen binären Suchbäumen. Eine genaue Beschreibung des Algorithmus ist dort zu finden.

Einfügen[Bearbeiten]

Das Einfügen in den Rot-Schwarz-Baum funktioniert wie das Einfügen in einen binären Suchbaum. Der neue Knoten wird rot gefärbt, damit die Schwarztiefe des Baumes erhalten bleibt. Nach dem Einfügen kann die zweite Forderung des Rot-Schwarz-Baumes verletzt sein. Deshalb kann es nötig werden, den Baum zu reparieren. Hierbei unterscheidet man insgesamt fünf Fälle, welche im Folgenden genauer betrachtet werden.

Anmerkung: Wenn im folgenden von Vater (P für parent), Großvater (G für grandparent) und Onkel (U für uncle) die Rede ist, so sind diese jeweils relativ zum neu einzufügenden Knoten (N) zu sehen.

Zur Verdeutlichung wird bei jedem der fünf Fälle ein Stück C-Code angegeben, welches zeigt, wie der entstandene Baum repariert wird.

Den Großvater bzw. den Onkel eines Knotens kann man wie folgt bestimmen:

 node grandparent(node n) {
     return n->parent->parent;
 }
 
 node uncle(node n) {
     if (n->parent == grandparent(n)->left)
         return grandparent(n)->right;
     else
         return grandparent(n)->left;
 }

Fall 1: Der neu eingefügte Knoten ist der erste im Baum.

 void insert_case1(node n) {
     if (n->parent == NULL)
         n->color = BLACK;
     else
         insert_case2(n);
 }

Wie oben bemerkt, wird eine rote Wurzel ohne Schaden sofort von rot auf schwarz umgefärbt.[4]

Fall 2: Der Vater des neuen Knotens ist schwarz.

Hierdurch könnte die dritte Forderung verletzt sein, da der neue Knoten selbst wieder zwei schwarze NIL-Knoten mitbringt und somit die Schwarztiefe auf einem der Pfade um eins erhöht wird.

Da der eingefügte Knoten selbst aber rot ist, und beim Einfügen einen schwarzen NIL-Knoten verdrängt hat, bleibt die Schwarztiefe auf allen Pfaden erhalten und es ist nichts zu tun.

 void insert_case2(node n) {
     if (n->parent->color == BLACK)
         return; /* Alle Forderungen des Baumes sind immer noch erfüllt */
     else
         insert_case3(n);
 }

Anmerkung: In den nun folgenden Fällen kann angenommen werden, dass der einzufügende Knoten einen Großvater hat, da sein Vater rot ist, und somit nicht selbst die Wurzel sein kann[4]. Da es sich aber bei einem Rot-Schwarz-Baum um einen Binärbaum handelt, hat der Großvater auf jeden Fall noch ein Kind (auch wenn es sich bei diesem um einen NIL-Knoten handeln kann).

Fall 3: Sowohl Onkel als auch Vater des neuen Knotens sind rot

Fall 3: Sowohl der Onkel als auch der Vater des neuen Knotens sind rot.

In diesem Fall kann man beide Knoten einfach schwarz färben, und im Gegenzug den Großvater rot färben, wodurch die dritte Forderung wiederhergestellt wird. Durch diese Aktion wird das Problem um zwei Ebenen nach oben verschoben, da durch den nun rot gefärbten Großvater die zweite Forderung verletzt sein könnte, weswegen nun der Großvater betrachtet werden muss. Dieses Vorgehen wird solange rekursiv fortgesetzt, bis alle Forderungen erfüllt sind.

 void insert_case3(node n) {
     if (uncle(n) != NULL && uncle(n)->color == RED) {
         n->parent->color = BLACK;
         uncle(n)->color = BLACK;
         grandparent(n)->color = RED;
         insert_case1(grandparent(n));
     }
     else
         insert_case4(n);
 }

Anmerkung: In den beiden noch verbleibenden Fällen wird der Einfachheit halber angenommen, dass der Vaterknoten das linke Kind seines Vaters (also des Großvaters des einzufügenden Knotens) ist. Sollte er das rechte Kind seines Vaters sein, so müssen in den beiden folgenden Fällen jeweils links und rechts vertauscht werden. Der Beispielcode berücksichtigt diesen Fall bereits.

Fall 4: Der neue Knoten hat einen schwarzen Onkel und ist das rechte Kind seines roten Vaters. Der Vater hängt links am Großvater.

Fall 4: Der neue Knoten hat einen schwarzen oder keinen Onkel und ist das rechte Kind seines roten Vaters während der Vater jedoch links am Großvater sitzt.

In diesem Fall kann man eine Linksrotation um den Vater ausführen, welche die Rolle des einzufügenden Knotens und seines Vaters vertauscht. Danach kann man den ehemaligen Vaterknoten mit Hilfe des fünften Falles bearbeiten. Durch die oben ausgeführte Rotation wurde ein Pfad (im Bild mit 1 markiert) so verändert, dass er nun durch einen zusätzlichen Knoten führt, während ein anderer Pfad (im Bild mit 3 markiert) so verändert wurde, dass er nun einen Knoten weniger hat. Da es sich jedoch in beiden Fällen um rote Knoten handelt, ändert sich hierdurch an der Schwarztiefe nichts, womit die dritte Forderung erfüllt bleibt.

 void insert_case4(node n) {
     //knoten ist rechts am vater und vater links am großvater
     if (n == n->parent->right && n->parent == grandparent(n)->left) {
         rotate_left(n->parent);
         n = n->left;
     //knoten ist links am vater und vater rechts am großvater
     } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
         rotate_right(n->parent);
         n = n->right;
     }
     insert_case5(n);
 }
Fall 5: Der neue Knoten hat einen schwarzen Onkel und ist das linke Kind seines roten Vaters. Der Vater hängt links am Großvater.

Fall 5: Der neue Knoten hat einen schwarzen oder keinen Onkel und ist das linke Kind seines roten Vaters; der Vater hängt auch links am Großvater.

In diesem Fall kann man eine Rechtsrotation um den Großvater ausführen, wodurch der ursprüngliche Vater nun der Vater von sowohl dem neu einzufügenden Knoten als auch dem ehemaligen Großvater ist. Da der Vater rot war, muss nach der zweiten Forderung (Kein roter Knoten hat ein rotes Kind) der Großvater schwarz sein. Vertauscht man nun die Farben des ehemaligen Großvaters bzw. Vaters, so ist in dem dadurch entstehenden Baum die zweite Forderung wieder erfüllt. Die dritte Forderung bleibt ebenfalls erfüllt, da alle Pfade, die durch einen dieser drei Knoten laufen, vorher durch den Großvater liefen und nun alle durch den ehemaligen Vater laufen, der inzwischen – wie der Großvater vor der Transformation – der einzige schwarze der drei Knoten ist.

 void insert_case5(node n) {
     n->parent->color = BLACK;
     grandparent(n)->color = RED;
     //knoten ist links am vater und vater links am großvater
     if (n == n->parent->left && n->parent == grandparent(n)->left) {
         rotate_right(grandparent(n));
     //knoten ist rechts am vater und vater rechts am großvater
     } else {
         /* Ab hier gilt, n == n->parent->right und n->parent == grandparent(n)->right */
         rotate_left(grandparent(n));
     }
 }

Löschen[Bearbeiten]

Illustration der beiden Möglichkeiten den Knoten mit dem Wert 7 aus dem Binärbaum zu löschen

Das Löschen eines Knotens aus einem Rot-Schwarz-Baum erfolgt analog zum Löschen eines Knotens aus binären Bäumen. Falls der zu löschende Knoten zwei Kinder hat (keine NIL-Knoten), so sucht man entweder den größten Wert im linken Teilbaum oder den kleinsten Wert im rechten Teilbaum des zu löschenden Knotens, kopiert diesen Wert in den eigentlich zu löschenden Knoten, und entfernt den gefundenen Knoten aus dem Rot-Schwarz-Baum. Da der gefundene Knoten höchstens ein Kind besitzen kann, da sein Wert sonst nicht maximal oder minimal gewesen wäre, lässt sich das Problem so auf das Löschen eines Knotens mit höchstens einem Kind vereinfachen.

Anmerkung: Im Folgenden werden wir also nur noch Knoten mit höchstens einem echten Kind betrachten, und dieses Kind als 'sein Kind' bezeichnen. Falls der Knoten gar keine echten Kinder hat, soll einer der beiden NIL-Knoten die Rolle des Kindes spielen.

Will man einen roten Knoten löschen, so kann man diesen durch sein Kind ersetzen, welches nach der zweiten Forderung (Kein roter Knoten hat ein rotes Kind) schwarz sein muss. Da der Vater des gelöschten Knotens ebenfalls aufgrund derselben Forderung schwarz gewesen sein muss, wird die zweite Forderung somit nicht mehr verletzt. Da alle Pfade, die ursprünglich durch den gelöschten roten Knoten verliefen, nun durch einen roten Knoten weniger verlaufen, ändert sich an der Schwarztiefe ebenfalls nichts, womit die dritte Forderung erfüllt bleibt.

Ebenfalls noch einfach zu lösen ist der Fall, wenn der zu löschende Knoten schwarz ist, aber ein rotes Kind hat. Würde in diesem Fall einfach der schwarze Knoten gelöscht werden, könnte dadurch sowohl die zweite als auch die dritte Forderung verletzt werden. Das kann jedoch umgangen werden, indem das Kind schwarz gefärbt wird. Somit treffen garantiert keine zwei roten Knoten aufeinander (der eventuell rote Vater des gelöschten Knotens und sein rotes Kind) und alle Pfade, die durch den gelöschten schwarzen Knoten verliefen, verlaufen nun durch sein schwarzes Kind, wodurch beide Forderungen erfüllt bleiben.

Die oben angegebene Löschung eines Knotens mit einem Kind kann durch das folgende Programm realisiert werden, das den Knoten n mittels replace_node durch den Knoten child ersetzt.

 void delete_one_child(node n) {
     /* Vorbedingung: n hat höchstens ein echtes Kind (kein NIL-Knoten) */
     node child = is_leaf(n->right) ? n->left : n->right;
     replace_node(n, child);
     if (n->color == BLACK) {
         if (child->color == RED)
             child->color = BLACK;
         else
             delete_case1(child);
     }
     free(n);
 }

Anmerkung: Der Code setzt voraus, dass eventuelle NIL-Knoten durch tatsächliche Knoten repräsentiert werden und nicht einfache Nullzeiger sind.

Schwieriger zu lösen ist der Fall, wenn sowohl der zu löschende Knoten als auch sein Kind schwarz sind. Zuerst ersetzt man den zu löschenden Knoten mit seinem Kind, und löscht danach den Knoten. Nun verletzt jedoch dieser nachgerückte Kind-Knoten, im folgenden Konfliktknoten genannt, die Forderungen eines Rot-Schwarz-Baumes, da es nun einen Pfad gibt, welcher vorher durch zwei schwarze Knoten führte, jetzt aber nur noch durch einen führt. Somit ist die dritte Forderung (Die Anzahl der schwarzen Knoten von jedem beliebigen Knoten zu einem Blatt ist auf allen Pfaden gleich) verletzt. Je nach Ausgangslage werden nun sechs verschiedene Fälle unterschieden, wie der Baum wieder zu reparieren ist, die im Folgenden genauer betrachtet werden.

Anmerkung: Wenn im folgenden von Vater (P für parent), Bruder (S für sibling), Großvater (G für grandparent) und Onkel (U für uncle) die Rede ist, so sind diese jeweils relativ zum Konfliktknoten zu sehen. Diesen Konfliktknoten selbst bezeichnen wir in den Diagrammen mit N. Zur Verdeutlichung wird bei jedem der Fälle ein Stück C-Code angegeben, das zeigt, wie der entstandene Baum repariert wird.

Den Bruder (sibling) eines Knotens kann man wie folgt bestimmen:

 node sibling(node n) {
      if (n == n->parent->left)
          return n->parent->right;
      else
          return n->parent->left;
 }

Fall 1: Der Konfliktknoten (N) ist die neue Wurzel. In diesem Fall ist man fertig, da ein schwarzer Knoten von jedem Pfad entfernt wurde und die neue Wurzel schwarz ist, womit alle Forderungen erfüllt bleiben.

 void delete_case1(node n) {
     if (n->parent == NULL)
         return;
     else
         delete_case2(n);
 }

Anmerkung: Für die Fälle 2, 5 und 6 sei der Konfliktknoten (N) das linke Kind seines Vaters. Sollte er das rechte Kind sein, so müssen in den drei Fällen jeweils links und rechts vertauscht werden. Der Beispielcode berücksichtigt diesen Fall bereits.

Fall 2: Der Bruder (S) des Konfliktknotens (N) ist rot.

Fall 2: Der Bruder (S) des Konfliktknotens ist rot. In diesem Fall kann man die Farben des Vaters und des Bruders des Konfliktknotens invertieren und anschließend eine Linksrotation um seinen Vater ausführen, wodurch der Bruder des Konfliktknotens zu dessen Großvater wird. Alle Pfade haben weiterhin dieselbe Anzahl an schwarzen Knoten, aber der Konfliktknoten hat nun einen schwarzen Bruder und einen roten Vater, weswegen man nun zu Fall 4, 5, oder 6 weitergehen kann.

 void delete_case2(node n) {
     if (sibling(n)->color == RED) {
         n->parent->color = RED;
         sibling(n)->color = BLACK;
         if (n == n->parent->left)
             rotate_left(n->parent);
         else
             rotate_right(n->parent);
     }
     delete_case3(n);
 }
Fall 3: Der Vater (P) des Konfliktknotens (N), sein Bruder (S) und die Kinder seines Bruders (SL oder SR) sind schwarz

Fall 3: Der Vater (P) des Konfliktknotens, sein Bruder (S) und die Kinder seines Bruders (SL oder SR) sind alle schwarz. In diesem Fall kann man einfach den Bruder rot färben, wodurch alle Pfade die durch diesen Bruder führen – welches genau die Pfade sind, die nicht durch den Konfliktknoten selbst führen – einen schwarzen Knoten weniger haben, wodurch die ursprüngliche Ungleichheit wieder ausgeglichen wird. Jedoch haben alle Pfade, die durch den Vater laufen, nun einen schwarzen Knoten weniger als jene Pfade die nicht durch den Vater laufen, wodurch die dritte Forderung immer noch verletzt wird. Um dies zu reparieren, versucht man nun den Vaterknoten zu reparieren, indem man versucht, einen der sechs Fälle – angefangen bei Fall 1 – anzuwenden.

 void delete_case3(node n) {
     if (n->parent->color == BLACK &&
         sibling(n)->color == BLACK &&
         sibling(n)->left->color == BLACK &&
         sibling(n)->right->color == BLACK)
     {
         sibling(n)->color = RED;
         delete_case1(n->parent);
     }
     else
         delete_case4(n);
 }
Fall 4: Sowohl der Bruder (S) des Konfliktknotens (N) als auch die Kinder des Bruders (SL oder SR) sind schwarz, aber der Vater (P) des Konfliktknotens ist rot

Fall 4: Sowohl der Bruder des Konfliktknotens als auch die Kinder des Bruders (SL bzw. SR) sind schwarz, aber der Vater (P) des Konfliktknotens rot. In diesem Fall reicht es aus, die Farben des Vaters und des Bruders zu tauschen. Hierdurch bleibt die Anzahl der schwarzen Knoten auf den Pfaden, die nicht durch den Konfliktknoten laufen, unverändert, fügt aber einen schwarzen Knoten auf allen Pfaden, die durch den Konfliktknoten führen, hinzu, und gleicht somit den gelöschten schwarzen Knoten auf diesen Pfaden aus.

 void delete_case4(node n) {
     if (n->parent->color == RED &&
         sibling(n)->color == BLACK &&
         sibling(n)->left->color == BLACK &&
         sibling(n)->right->color == BLACK)
     {
         sibling(n)->color = RED;
         n->parent->color = BLACK;
     }
     else
         delete_case5(n);
 }
Fall 5: Das linke Kind (SL) des Bruders (S) ist rot, das rechte Kind (SR) wie auch der Bruder (S) des Konfliktknotens (N) sind jedoch schwarz und der Konfliktknoten selbst ist das linke Kind seines Vaters (P)

Fall 5: Das linke Kind (SL) des Bruders (S) ist rot, das rechte Kind (SR) wie auch der Bruder des Konfliktknotens (N) sind jedoch schwarz und der Konfliktknoten selbst ist das linke Kind seines Vaters. In diesem Fall kann man eine Rechtsrotation um den Bruder ausführen, sodass das linke Kind (SL) des Bruders dessen neuer Vater wird, und damit der Bruder des Konfliktknotens wird. Danach vertauscht man die Farben des Bruders und seines neuen Vaters. Nun haben alle Pfade immer noch die gleiche Anzahl an schwarzen Knoten, aber der Konfliktknoten hat einen schwarzen Bruder dessen rechtes Kind rot ist, womit man nun zum sechsten Fall weitergehen kann. Weder der Konfliktknoten selbst noch sein Vater werden durch diese Transformation beeinflusst.

 void delete_case5(node n) {
     if (n == n->parent->left &&
         sibling(n)->color == BLACK &&
         sibling(n)->left->color == RED &&
         sibling(n)->right->color == BLACK)
     {
         sibling(n)->color = RED;
         sibling(n)->left->color = BLACK;
         rotate_right(sibling(n));
     }
     else if (n == n->parent->right &&
              sibling(n)->color == BLACK &&
              sibling(n)->right->color == RED &&
              sibling(n)->left->color == BLACK)
     {
         sibling(n)->color = RED;
         sibling(n)->right->color = BLACK;
         rotate_left(sibling(n));
     }
     delete_case6(n);
 }
Fall 6: Der Bruder (S) des Konfliktknotens (N) hat schwarze, das rechte Kind des Bruders (SR) rote Farbe, und der Konfliktknoten selbst ist linkes Kind.
Die 2 weiß dargestellten Knoten P und S haben dieselbe Farbe, rot oder schwarz.

Fall 6: Der Bruder (S) des Konfliktknotens (N) ist schwarz, das rechte Kind des Bruders (SR) rot und der Konfliktknoten selbst ist das linke Kind seines Vaters. In diesem Fall kann man eine Linksrotation um den Vater des Konfliktknotens ausführen, so dass S Großvater von N wird. Nun reicht es, die Farben von S und P zu tauschen und SR schwarz zu färben. N hat immer noch dieselbe Farbe, wodurch die zweite Forderung erfüllt bleibt. Aber N hat nun einen weiteren schwarzen Vorfahren: Falls P vor der Transformation noch nicht schwarz war, so ist er nach der Transformation schwarz, und falls P schon schwarz war, so hat der Konfliktknoten nun S als schwarzen Großvater, weswegen die Pfade, welche durch den Konfliktknoten laufen, nun einen zusätzlichen schwarzen Knoten passieren.

Bei den Pfaden, die sich ändern und die nicht durch den Konfliktknoten (N) verlaufen, gibt es zwei Möglichkeiten:

  • Der Pfad verläuft durch seinen neuen Bruder (3). Dann muss der Pfad sowohl vor als auch nach der Transformation durch S und P laufen. Da die beiden Knoten aber nur ihre Farben vertauscht haben, ändert sich an der Schwarztiefe auf dem Pfad nichts.
  • Der Pfad verläuft durch den neuen Onkel (SR) von N, welcher das rechte Kind des Bruders (S) ist. In diesem Fall ging der Pfad vorher sowohl durch S, P und SR. Nach der Transformation geht er aber nur noch durch (S) selbst, welcher die Farbe von P angenommen hat, und SR, der von Rot auf Schwarz umgefärbt wurde. An der Schwarztiefe eines solchen Pfades hat sich also nichts geändert.

In beiden Fällen ändert sich die Anzahl der schwarzen Knoten auf den Pfaden nicht: die zweite Forderung ist wiederhergestellt.

 void delete_case6(node n) {
     sibling(n)->color = n->parent->color;
     n->parent->color = BLACK;
     if (n == n->parent->left) {
         /* Here, sibling(n)->color == BLACK &&
                  sibling(n)->right->color == RED */
         sibling(n)->right->color = BLACK;
         rotate_left(n->parent);
     }
     else
     {
         /* Here, sibling(n)->color == BLACK &&
                  sibling(n)->left->color == RED */
         sibling(n)->left->color = BLACK;
         rotate_right(n->parent);
     }
 }

Höhenbeweis[Bearbeiten]

Wie schon in der Einleitung motiviert, ist die besondere Eigenschaft von Rot-Schwarz-Bäumen, dass sie in logarithmischer Zeit – genauer in \mathcal O(\log_2 n) mit n als der Anzahl der Schlüssel – ein Element im Baum suchen, löschen oder einfügen können. Diese Operationen sind auf allen binären Suchbäumen von der Höhe h des Baumes abhängig. Je niedriger die Höhe des Baumes ist, desto schneller laufen die Operationen. Kann man nun beweisen, dass ein binärer Suchbaum mit n Elementen nie eine gewisse Höhe (im Falle des Rot-Schwarz-Baumes 2 \log_2(n+2)-2) überschreitet, so hat man bewiesen, dass die oben genannten Operationen im schlimmsten Fall logarithmische Kosten haben, nämlich die genannten Kosten von 2 \log_2(n+2)-2 für einen Baum, in dem n Elemente gespeichert sind. Somit muss gezeigt werden, dass folgende Aussage gilt:

Für die Höhe h eines Rot-Schwarz-Baumes, der n Schlüssel speichert, gilt: h \leq 2 \log_2(n+2)-2.

Vorbemerkung[Bearbeiten]

Damit ein Rot-Schwarz-Baum einer bestimmten Höhe h eine minimale Knotenzahl besitzt, muss er genau einen längsten Pfad der Länge h haben, auf dem rote und schwarze Knoten sich abwechseln. Alle anderen Pfade haben rote Knoten nur dann, wenn sie ein Stück mit dem längsten Pfad gemeinsam haben. Alle Knoten außerhalb des längsten Pfades sind schwarz.[5]

In den folgenden Beweisen sei unter einem »Ast der Größe \scriptstyle 2^t« ein vollständiger Binärbaum aus \scriptstyle 2^t-1 schwarzen (inneren) Knoten verstanden inklusive eines weiteren Knotens, dessen rechter Kindbaum er ist. Diese Wurzel des Astes kann dabei rot oder schwarz sein. Bei roter Wurzel hat der Ast die Schwarztiefe t, bei schwarzer kommen auf den rechtsseitigen Pfaden t+1 schwarze Knoten zusammen.

Rot-Schwarz-Bäume der Höhen 0,2,4,6
jeweils mit minimaler Knotenzahl 0,2,6 resp. 14

Minimalzahl der Knoten bei gerader Höhe[Bearbeiten]

Ist h gerade, so gibt es einen Rot-Schwarz-Baum der Höhe h mit m_h = 2 \cdot 2^{\tfrac{h}2}-2 Knoten und keinen mit weniger. Seine Schwarztiefe ist \tfrac{h}2.

Beweis für gerade Höhe[Bearbeiten]

Ist h = 0, dann ist der leere Baum mit einem NIL-Knoten der einzige Rot-Schwarz-Baum der Höhe h. Er trägt 0 Schlüssel.
Ist h > 0 und gerade, dann bauen wir einen Minimalbaum der Höhe h aus dem uns schon bekannten Minimalbaum der Höhe h-2 (mit der Schwarztiefe \tfrac{h-2}2=:s) und zwei „Ästen“ zusammen, und zwar hängen wir den \scriptstyle (h\!-\!2)-Baum links an die rote Wurzel eines Astes der Größe \scriptstyle 2^s. Der so entstandene Baum (der übrigens ein Minimalbaum der Höhe h-1 ist) hat dieselbe Schwarztiefe s. Ihn hängen wir wiederum links an die schwarze Wurzel eines Astes der Größe \scriptstyle 2^s. Der so entstandene Baum hat nun wegen der schwarzen Wurzel die (einheitliche) Schwarztiefe s+1. Seine Knotenzahl ist
m_h = m_{h-2}+2^s+2^s = 2 \cdot 2^{\tfrac{h-2}2}-2+2^{\tfrac{h-2}2}+2^{\tfrac{h-2}2} = 2 \cdot 2^{\tfrac{h}2}-2,
wie behauptet ■
Rot-Schwarz-Bäume der Höhen 1,3,5 mit den minimalen Knotenzahlen 1,4,10

Minimalzahl der Knoten bei ungerader Höhe[Bearbeiten]

Ist h ungerade, so gibt es einen Rot-Schwarz-Baum der Höhe h mit m_h = 3 \cdot 2^{\tfrac{h-1}2}-2 Knoten und keinen mit weniger. Seine Schwarztiefe ist \tfrac{h-1}2.

Beweis für ungerade Höhe[Bearbeiten]

Ist h = 1, dann ist der Baum mit einem Knoten und 2 NIL-Knoten der einzige Rot-Schwarz-Baum der Höhe h.
Ist h > 1 und ungerade, dann bauen wir einen Minimalbaum der Höhe h aus dem der Höhe h-2 (mit der Schwarztiefe \tfrac{h-3}2=:s) und zwei „Ästen“ zusammen, und zwar hängen wir den \scriptstyle (h\!-\!2)-Baum links an die schwarze Wurzel eines Astes der Größe \scriptstyle 2^s. Wegen dieser schwarzen Wurzel kommen nun auch auf den linksseitigen Pfaden s+1 schwarze Knoten zusammen, so dass der so entstandene Baum (der übrigens ein Minimalbaum der Höhe h-1 ist) die Schwarztiefe s+1 hat. Ihn hängen wir wiederum links an die rote Wurzel eines Astes der Größe \scriptstyle 2^{s+1}. Der so entstandene Baum hat nun wegen der roten Wurzel dieselbe (einheitliche) Schwarztiefe s+1. Seine Knotenzahl ist
m_h = m_{h-2}+2^s+2^{s+1} = 3 \cdot 2^{\tfrac{h-3}2}-2+2^{\tfrac{h-3}2}+2^{\tfrac{h-1}2} = 3 \cdot 2^{\tfrac{h-1}2}-2,
wie behauptet ■

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

m_h = 3 \cdot 2^{\tfrac{h-1}2}-2 = 3\cdot 2^{-\tfrac32}\cdot 2^{\tfrac{h+2}2}-2 > 2 \cdot 2^{\tfrac{h}2}-2,

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

m_h \geq 2 \cdot 2^{\tfrac{h}2}-2

ergibt.

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

2 \cdot 2^{\tfrac{h}2}-2 \leq m_h \leq n.

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


\begin{matrix}
                & 2 \cdot 2^{\tfrac{h}2}-2 & \leq & n \\
\Leftrightarrow & 2 \cdot 2^{\tfrac{h}2} & \leq & n+2 \\
\Leftrightarrow & 1+\tfrac{h}2 & \leq & \log_2(n+2) \\
\Leftrightarrow & \tfrac{h}2 & \leq & \log_2(n+2)-1 \\
\Leftrightarrow & h & \leq & 2 \log_2(n+2)-2 \\
\end{matrix}

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

Verwendung von Rot-Schwarz-Bäumen[Bearbeiten]

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

Weitere Bäume[Bearbeiten]

Literatur[Bearbeiten]

Einzelnachweise[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: A Dichromatic Framework for Balanced Trees. In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science. 1978, S. 8-21.
  3.  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.
  4. a b c Einige Autoren fordern noch, dass die Wurzel des Baums schwarz zu färben sei. Nicht jedoch z. B. Mehlhorn und Sedgewick. Tatsächlich stört diese Forderung bei rekursiven Beweisen und erübrigt sich. Denn ist die Wurzel rot, so müssen ihre Kinder nach Forderung zwei schwarz sein. Um jedoch im Algorithmus die Zahl von Fallunterscheidungen gering zu halten, ist es günstig, wenn man bei einem roten Knoten immer einen Vater voraussetzen kann. Wir denken uns also bei der Darlegung des Algorithmus eine rote Wurzel stets auf schwarz umgefärbt.
  5. Sedgewick 2011 S. 444 Proof sketch.
  6. http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html
  7. http://docs.oracle.com/javase/7/docs/api/java/util/TreeMap.html

Weblinks[Bearbeiten]

Dies ist ein als lesenswert ausgezeichneter Artikel.
Dieser Artikel wurde in die Liste der lesenswerten Artikel aufgenommen. Vorlage:Lesenswert/Wartung/ohne DatumVorlage:Lesenswert/Wartung/ohne Version