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.[3] Somit können die wichtigsten Operationen in Suchbäumen – suchen, einfügen und löschen – garantiert in \mathcal O(\log n) (Landau-Symbol) 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:[4]

  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[5] 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 logarithmische 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 Forderung Nummer 2 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 Forderung Nummer 3 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]

Navigieren[Bearbeiten]

Die Navigationsoperationen, das sind die verschiedenen Suchoperationen, das Traversieren, Aufsuchen erstes oder letztes Element und ähnliche, lassen den Baum unverändert 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 (englisch: find, search oder locate) eines Elements anhand seines Schlüssels ist die wichtigste unter den Navigationsoperationen. Die Höhen-Balancierung des Rot-Schwarz-Baums versucht, auf diese Operation hin zu optimieren. Sie ermöglicht eine Art „direkten Zugriff“ (im Gegensatz zum sequentiellen Zugriff der Traversierung). Sie wird in der Regel als vorausgehende Operation sowohl beim Einfügen als auch beim Löschen eingesetzt.

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

Einfügen[Bearbeiten]

Das Einfügen in den Rot-Schwarz-Baum funktioniert wie das Einfügen in einen binären Suchbaum. Der neue Knoten ersetzt einen NIL-Knoten, bringt zwei neue NIL-Knoten mit und wird rot gefärbt, damit die Schwarztiefe des Baumes erhalten bleibt. Nach dem Einfügen kann die Forderung Nummer 2 (»Kein roter Knoten hat ein rotes Kind«) verletzt sein. Deshalb kann es nötig werden, den Baum zu reparieren.

Der neue Knoten werde N (für node) genannt. Relativ zu N sei dessen Vater mit P (für parent), der Großvater mit G (für grandparent) und der Onkel mit U (für uncle) bezeichnet. N ist beim ersten Iterationsschritt der gerade betrachtete „Problemknoten“.

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;
 }

Schleifeninvariante: Zu Beginn der nun folgenden Iteration ist der Problemknoten N rot. Die Forderung Nummer 3 (»Die Anzahl der schwarzen Knoten von jedem beliebigen Knoten zu einem Blatt ist auf allen Pfaden gleich«) gilt für den ganzen Baum. Die Forderung Nummer 2 gilt für den ganzen Baum – mit der eventuellen Ausnahme des Paares P-N.

Die folgenden fünf Fälle decken die Situationen ab, die entweder in einem Schritt auf der betrachteten Ebene oder über weitere Iterationen auf höheren Ebenen zu einer Reparatur des Baumes führen. Zur Verdeutlichung wird bei jedem der Fälle ein Stück C-Code angegeben, das zeigt, wie der entstandene Baum repariert wird.[6]

Fall 1: Der Problemknoten N hat keinen Vater.

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

Der Knoten N ist die neue Wurzel. Wie oben bemerkt, wird eine rote Wurzel ohne Schaden sofort von rot auf schwarz umgefärbt.[5]

Fall 2: Der Vater P des Problemknotens N ist schwarz.

Nach Voraussetzung ist die Schwarztiefe auf allen Pfaden dieselbe. Alle Knoten in Vater-Kind-Beziehung (einschließlich P-N) erfüllen die Forderung Nummer 2.

 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 N einen Großvater G hat, da sein Vater P rot ist und somit nicht die Wurzel sein kann.[5] Da es sich aber bei einem Rot-Schwarz-Baum um einen Binärbaum mit externen Blättern 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 der Onkel U als auch der Vater P des Problemknotens N sind rot.

Fall 3: Sowohl der Onkel U als auch der Vater P des Problemknotens N sind rot.

In diesem Fall kann man P und U schwarz und G rot färben, wodurch die Forderung Nummer 2 im von G gewurzelten Unterbaum wiederhergestellt wird. Auf keinem Pfad ändert sich die Schwarztiefe. Durch diese Aktion wird das Problem um zwei Ebenen nach oben verschoben mit G als dem neuen Problemknoten.

 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)); /* Iteration */
     }
     else
         insert_case4(n);
 }

Vorbemerkung: In den beiden noch verbleibenden Fällen wird um der Kürze der Darlegung willen angenommen, dass der Vater P ein linkes Kind ist. Sollte er rechtes Kind sein, so ist jeweils links mit rechts zu vertauschen. (Im Beispielcode sind beide Fälle behandelt.)

Fall 4: Der Problemknoten N hat einen schwarzen Onkel und ist das rechte Kind seines roten Vaters P, der links am Großvater G hängt.

Fall 4: Der Problemknoten N hat keinen oder einen schwarzen Onkel U und ist das rechte Kind seines roten Vaters P, der links am Großvater G hängt.

In diesem Fall kann man eine Linksrotation um P ausführen, was die Rollen von N und P vertauscht. Durch diese Rotation wird 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) nun einen Knoten weniger hat. Da es sich jedoch in beiden Fällen um rote Knoten handelt, ändert sich an der Schwarztiefe nichts, womit die Forderung Nummer 3 erfüllt bleibt.

Die Ausgangskonstellation entspricht der Eingangskonstellation des fünften Falles mit P als dem neuen Problemknoten.

 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 Problemknoten N hat einen schwarzen Onkel und ist das linke Kind seines roten Vaters P, der links am Großvater G hängt.

Fall 5: Der Problemknoten N hat keinen oder einen schwarzen Onkel U und ist das linke Kind seines roten Vaters P, der links am Großvater G hängt.

In diesem Fall kann man eine Rechtsrotation um G ausführen, wodurch P zum Vater sowohl von N als auch von G wird. Da P rot war, muss nach der Forderung Nummer 2 (»Kein roter Knoten hat ein rotes Kind«) G schwarz sein. Vertauscht man nun die Farben von G und P, so ist in dem dadurch entstehenden Baum die Forderung Nummer 2 wieder erfüllt. Die Forderung Nummer 3 bleibt ebenfalls erfüllt, da alle Pfade, die durch einen dieser drei Knoten laufen, vorher durch G liefen und nun alle durch P laufen, der inzwischen – wie G 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 Schlüssel 7 aus dem Binärbaum zu löschen

Das Löschen eines Knotens, sein Name sei D (für delete), aus einem Rot-Schwarz-Baum erfolgt wie das Löschen eines Knotens aus einem Binärbaum. Falls D zwei echte Kinder hat (keine NIL-Knoten), so sucht man entweder den Knoten mit dem größten Schlüssel im linken oder den mit dem kleinsten Schlüssel im rechten Teilbaum von D. Da dieser Ersatzknoten maximal oder minimal ist, kann er kein rechtes resp. linkes Kind haben, hat also höchstens ein echtes Kind. Da D ohnehin gelöscht werden soll, es also auf eine korrekte Reihenfolge nicht mehr ankommt, vertauschen wir alle Verbindungen einschließlich Farbe zwischen D und dem Ersatzknoten.

Damit hat der zu löschende Knoten D höchstens ein einziges echtes Kind, das mit N bezeichnet sei. Hat D kein echtes Kind, soll N für einen seiner NIL-Knoten stehen.

Ist D rot, so kann man ihn durch N ersetzen, welcher wegen der Forderung Nummer 2 (»Kein roter Knoten hat ein rotes Kind«) schwarz sein muss. Da der Vater von D ebenfalls aufgrund von Forderung Nummer 2 schwarz gewesen sein muss, bleibt die Forderung Nummer 2 erfüllt. 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 nichts, womit die Forderung Nummer 3 erfüllt bleibt.

Ebenfalls noch einfach zu lösen ist der Fall, wenn D schwarz ist und N rot. Man färbt N schwarz und platziert ihn an die Stelle von D im Baum. Damit ist D aus dem Baum entfernt, und die Forderung Nummer 2 bleibt erfüllt. Ferner verlaufen nun alle Pfade, die durch den gelöschten schwarzen Knoten verliefen, durch sein schwarzes Kind, wodurch Forderung Nummer 3 erfüllt bleibt.

Schwieriger zu lösen ist der Fall, wenn beide, D und N schwarz sind. Nachdem D durch N ersetzt ist, verletzt N (der ein NIL-Knoten sein kann), die Forderung Nummer 3, da die durch N führenden Pfade nun einen schwarzen Knoten weniger enthalten als vorher.

Relativ zum Problemknoten N sei dessen Vater mit P (für parent), der Großvater mit G (für grandparent), der Bruder mit S (für sibling) und dessen linkes und rechtes Kind mit SL resp. SR bezeichnet.

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;
 }

Schleifeninvariante: Zu Beginn der nun folgenden Iteration ist der gerade betrachtete Problemknoten N dadurch gekennzeichnet, dass die Anzahl der schwarzen Knoten auf den Pfaden, die von einem gegebenen Knoten nicht durch N zu einem Blatt führen, gleich ist, während alle solche Pfade durch N einen schwarzen Knoten weniger enthalten. Die Forderung Nummer 2 (»Kein roter Knoten hat ein rotes Kind«) ist dagegen überall erfüllt.

Die folgenden sechs Fälle decken die Situationen ab, die entweder in einem Schritt auf der betrachteten Ebene oder über weitere Iterationen auf höheren Ebenen zu einer Reparatur des Baumes führen. Zur Verdeutlichung wird bei jedem der Fälle ein Stück C-Code angegeben, das zeigt, wie der entstandene Baum repariert wird.[6]

Fall 1: Der Problemknoten N ist die (ggf. neue) Wurzel. In diesem Fall ist man fertig, da alle vergleichbaren Pfade durch N gehen (und einen schwarzen Knoten weniger enthalten als vorher).

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

Vorbemerkung: In den Fällen 2, 5 und 6 wird um der Kürze der Darlegung willen angenommen, dass der Problemknoten N ein linkes Kind ist. Sollte er rechtes Kind sein, so ist links mit rechts zu vertauschen. (Im Beispielcode sind beide Fälle behandelt.)

Fall 2: Der Bruder S des Problemknotens N ist rot.

Fall 2: Der Bruder S des Problemknotens N ist rot. In diesem Fall kann man die Farben von P und S invertieren und anschließend eine Linksrotation um P ausführen, wodurch S zum Großvater von N wird. Alle Pfade haben weiterhin dieselbe Anzahl an schwarzen Knoten, aber N hat nun einen schwarzen Bruder (SL) und einen roten Vater (P), weswegen man nun zu Fall 4, 5, oder 6 weitergehen kann – mit N als dem Problemknoten.

 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 Problemknotens N, sein Bruder S und die Kinder SL und SR von S sind schwarz.

Fall 3: Der Vater P des Problemknotens N, sein Bruder S und die Kinder SL und SR von S sind alle schwarz. In diesem Fall kann man einfach S rot färben, wodurch alle Pfade die durch S führen – welches genau die Pfade sind, die nicht durch N führen – einen schwarzen Knoten weniger haben, wodurch die ursprüngliche Ungleichheit wieder ausgeglichen wird. Jedoch haben alle Pfade, die durch P laufen, nun einen schwarzen Knoten weniger als jene Pfade die nicht durch P laufen, wodurch die Forderung Nummer 3 immer noch verletzt wird. Durch diese Aktion wird das Problem um eine Ebene nach oben verschoben mit P als dem neuen Problemknoten.

 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); /* Iteration */
     }
     else
         delete_case4(n);
 }
Fall 4: Sowohl der Bruder S des Problemknotens N als auch die Kinder SL und SR von S sind schwarz, aber der Vater P von N ist rot.

Fall 4: Sowohl der Bruder S des Problemknotens N als auch die Kinder SL und SR von S sind schwarz, aber der Vater P von N ist rot. In diesem Fall reicht es aus, die Farben von P und S zu tauschen. Hierdurch bleibt die Anzahl der schwarzen Knoten auf den Pfaden, die nicht durch den Problemknoten laufen, unverändert, fügt aber einen schwarzen Knoten auf allen Pfaden, die durch den Problemknoten führen, hinzu und gleicht damit den fehlenden 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 Problemknotens N sind schwarz und N 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 S des Problemknotens N sind schwarz und N ist das linke Kind seines Vaters P. In diesem Fall kann man eine Rechtsrotation um S ausführen, sodass SL der neue Vater von S und zugleich zum Bruder von N wird. Danach vertauscht man die Farben von S und SL. Nun haben alle Pfade immer noch die gleiche Anzahl an schwarzen Knoten, aber N hat einen schwarzen Bruder (SL), dessen rechtes Kind (S) rot ist, womit man nun zum sechsten Fall weitergehen kann. Weder N noch P 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 Problemknotens N ist schwarz, das rechte Kind SR von S rot, und N ist linkes Kind.
Die 2 weiß dargestellten Knoten P und S haben dieselbe Farbe, rot oder schwarz.

Fall 6: Der Bruder S des Problemknotens N ist schwarz, das rechte Kind SR von S rot und N ist das linke Kind seines Vaters P. In diesem Fall kann man eine Linksrotation um P 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 Forderung Nummer 2 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 N nun S als schwarzen Großvater, weswegen die Pfade, welche durch N laufen, nun einen zusätzlichen schwarzen Knoten passieren.

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

  1. Der Pfad verläuft durch den neuen Bruder 3 von N. 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.
  2. 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 durch SR, S und P. Nach der Transformation geht er aber nur noch durch SR, der von Rot auf Schwarz (die vorige Farbe von S) umgefärbt wurde, und S, welcher die Farbe von P angenommen hat. Die Schwarztiefe eines solchen Pfades ändert sich also nicht.

Bei den Pfaden, die nicht durch N verlaufen, ändert sich die Anzahl der schwarzen Knoten nicht. Damit ist die Forderung Nummer 3 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.[7]

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 ■

Zusammenfassung[Bearbeiten]

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.

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

Die Folge A001137 in OEIS gibt in Abhängigkeit von der Knotenzahl die Anzahl von Rot-Schwarz-Bäumen mit schwarzer Wurzel, die Folge A001138 in OEIS die mit roter Wurzel.

In einem Szenario, das nur aus Einfügungen besteht, wird bspw. der Baum mit sieben schwarzen inneren Knoten nicht gebildet.

Es gibt mehrere gültige Rot-Schwarz-Einfärbungen bspw. für den vollständigen Baum mit sieben inneren Knoten (Schlüsseln). Beim Suchen und Traversieren ist wegen der identischen Form des Baums das Laufzeitverhalten identisch, beim Einfügen und Löschen aber möglicherweise verschieden, da letztere die Einfärbung berücksichtigen.

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

Im Java Development Kit sind die Klassen TreeSet[8] und TreeMap[9] 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, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. In: IEEE Computer Society (Hrsg.): Proceedings of the 19th Annual Symposium on Foundations of Computer Science. 1978, S. 8–21.
  3. Diese Abschätzung ist scharf (siehe #Höhenbeweis) und für n > 0 wegen
    
\begin{matrix}
                & \tfrac{n}2 & < & n \\
\Leftrightarrow & \tfrac{n+2}2 & < & n+1 \\
\Leftrightarrow & \log_2(n+2)-1 & < & \log_2(n+1) \\
\Leftrightarrow & 2\log_2(n+2)-2 & < & 2\log_2(n+1) \\
\end{matrix}
    marginal genauer als das häufig in der Literatur anzutreffende
    2 \log_2(n+1).
  4.  Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7, S. 273.
  5. 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 Nummer 2 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.
  6. a b Die verschiedenen Programmabschnitte sind als (interne) Unterprogramme ausgestaltet, die sich gegenseitig aufrufen – teilweise rekursiv. Diese Darstellung ist die kompakteste, eine iterative Programmierung bietet jedoch Vorteile hinsichtlich Platz und Zeit (s. a. Binärer Suchbaum#Iterative Programmierung).
  7. Sedgewick 2011 S. 444 Proof sketch.
  8. http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html
  9. 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