Rot-Schwarz-Baum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Rot-Schwarz-Baum
Komplexität
Platz \mathcal{O}(n)
Operation im Mittel Worst Case
Suchen \mathcal{O}(\log n) \mathcal{O}(\log n)
Querschritt \mathcal{O}(1) \mathcal{O}(\log n)
Min, Max \mathcal{O}(\log n) \mathcal{O}(\log n)
Einfügen \mathcal{O}(1) \mathcal{O}(\log n)
Löschen \mathcal{O}(1) \mathcal{O}(\log n)
n Knoten im Baum
Platz- und Zeit-Komplexitäten

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 Schlüsseln (Elementen) 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

Die auf allen Pfaden von Wurzel zu Blatt gleiche Anzahl schwarzer Knoten 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 schlüssellosen Blätter (sog. NIL-Blätter) haben 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 bei den Modifikationsoperationen (Einfügen oder Löschen) eingesetzt.

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

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, der entweder die Wurzel ist, falls der Baum vorher leer war, oder linker bzw. rechter Kindknoten bei einem Schlüssel tragenden Knoten. In beiden Fällen bringt er zwei neue NIL-Knoten mit. Er 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 Elter mit P (für parent), der Großelter 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ßelter 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;
 }

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

 void RBinsert(
     tree T, // Rot-Schwarz-Baum
     node P, // Nachbarknoten (wird zum Elter von N)
     int  d, // Richtung (linkes oder rechtes Kind)
     node N) // einzufügender Knoten
 {
     node G, U;

     N->color = RED;
     N->left = NULL;
     N->right = NULL;
     N->parent = P;
     if (P != NULL) {
         if (d == LEFT)
             P->left = N;
         else
             P->right = N;
     }
     do while (1) {
vorher Fall
Rot-
ation
nachher
Fall
x N P G U x N P G U
BlackRedNode.svg 1 BlackNode.svg return
RedNode.svg BlackNode.svg 2 RedNode.svg BlackNode.svg return
RedNode.svg RedNode.svg BlackNode.svg RedNode.svg 3 RedNode.svg 1,…
i RedNode.svg RedNode.svg BlackNode.svg BlackNode.svg 4 PS a RedNode.svg RedNode.svg BlackNode.svg BlackNode.svg 5
a RedNode.svg RedNode.svg BlackNode.svg BlackNode.svg 5 GP RedNode.svg BlackNode.svg RedNode.svg BlackNode.svg return
Einfügen: Zusammenschau der Fälle

Einfügen: Zusammenschau der Fälle

Die möglichen Konstellationen lassen sich in fünf Fälle aufteilen, zu denen es Transformationen gibt, die entweder in einem Schritt auf der betrachteten Ebene oder über weitere Iterationen auf höheren Ebenen zu einer Reparatur des Baumes führen.

Die 5 Spalten in der Gruppe vorher stellen die Konstellation (Farbe plus ggf. Kindesrichtung) von 4 Knoten vor der in der Spalte Fall → genannten Transformation dar. Angegeben ist die Farbe des Problemknotens N, und ausgehend von diesem die Farben der 3 weiteren relevanten Knoten. Bei einem Eintrag in der Spalte Rotation ist eine Rotation an der Transformation beteiligt. Mithilfe der Gruppe vorher kann die Vollständigkeit der Abdeckung durch die Fälle leichter verifiziert werden.

Die 5 Spalten in der Gruppe nachher enthalten die Folgekonstellation. Ein return in der Spalte → Fall zeigt an, dass die Einfügeoperation mit der genannten Transformation abgeschlossen ist.

Andernfalls findet sich dort die Nummer der nachfolgenden Transformation. Dann enthält die Folgekonstellation die Farbe des neuen Problemknotens N, und ausgehend von diesem ggf. die Farben anderer Knoten zur Eingabe in diese Transformation. Der Eintrag 1,… bedeutet einen neuen Iterationsschritt, der zwei Ebenen weiter oben stattfindet. Die Anzahl der Ebenen stimmt mit der Höhe h überein, somit können maximal \tfrac h2 Iterationen vorkommen. Nun ist der Aufwand für eine Iteration in \mathcal{O}(1) (d. h. beschränkt), also ist die Laufzeit für die gesamte Einfügeoperation in \mathcal{O}(h) = \mathcal{O}(\log n).

In den beiden Spalten x steht a (wie außen) für eine Rechts-Rechts- oder Links-Links-Kindesrichtung von N zu P zu G und i (wie innen) für Rechts-Links oder Links-Rechts.

Die Tabelle zeigt, dass bei einer Einfügung maximal 2 Rotationen erforderlich sind. Denn nach einer Rotation kann keine weitere Iteration mehr kommen, die Rotationen befinden sich endrekursiv am Ende der letzten Iteration.

Schleifeninvariante: Zu Beginn jeder Iteration ist der Problemknoten N rot. Er hat im Diagramm des resp. Falles eine blaue Kontur. Die Forderung Nummer 2 »Kein roter Knoten hat ein rotes Kind« gilt für den ganzen Baum – mit der eventuellen Ausnahme des Paares NP. 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 (wobei im Diagramm die kleinen schwarzen Kreisflächen an den Spitzen der die Unterbäume darstellenden Dreiecke der Überprüfung der Schwarztiefe dienen).

Zur Verdeutlichung wird jedem der Fälle ein Stück C-Code beigegeben, das zeigt, wie der Baum repariert wird.[6]

Einfügen Fall 1
Der Problemknoten N hat keinen Elter.
         if (P == NULL) { // Fall_1
             T->root = N; // neue Wurzel
             N->color = BLACK;
             return; // Einfügung fertiggestellt
         }

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

Einfügen Fall 2
Der Elter P des Problemknotens N ist schwarz.

Nach Voraussetzung ist die Schwarztiefe auf allen Pfaden dieselbe. Alle Paare Knoten–Elter (einschließlich NP) erfüllen die Forderung Nummer 2.

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

Anmerkung: In den nun folgenden Fällen kann angenommen werden, dass der einzufügende Knoten N einen Großelter G hat, da sein Elter 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ßelter auf jeden Fall noch ein Kind (auch wenn es sich bei diesem um einen NIL-Knoten handeln kann).

Einfügen Fall 3
Einfügen Fall 3

Sowohl der Onkel U als auch der Elter 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.

         G = P->parent; // Großelter von N
         U = uncle(N); // Onkel von N
         if (U != NULL && U->color == RED) { // Fall_3
             P->color = BLACK;
             U->color = BLACK;
             G->color = RED;
             N = G; // neuer Problemknoten
             P = N->parent;
             continue; // Iteration
         }

Vorbemerkung: In den verbleibenden Fällen wird um der Kürze der Darlegung willen angenommen, dass der Elter 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.)

Einfügen Fall 4
Einfügen Fall 4

Der Problemknoten N hat keinen oder einen schwarzen Onkel U und ist das rechte Kind seines roten Elters P, der links am Großelter 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 Diagramm mit 1 markiert) so verändert, dass er nun durch einen zusätzlichen Knoten führt, während ein anderer Pfad (im Diagramm 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 Zielkonstellation entspricht der Eingangskonstellation des Falles 5 mit P als dem neuen Problemknoten.

         if (N == P->right && P == G->left) { // Fall_4iR
             // Knoten ist rechts am Elter und Elter links am Großelter
             rotate_left(P);
             // P und sein jetziger Elter N sind linke Kinder
         } else if (N == P->left && P == G->right) { // Fall_4iL
             // Knoten ist links am Elter und Elter rechts am Großelter
             rotate_right(P);
             // P und sein jetziger Elter N sind rechte Kinder
         }
         N = P; // neuer Problemknoten (rot)
         P = N->parent; // neuer Elter (rot)
Einfügen Fall 5
Einfügen Fall 5

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

In diesem Fall kann man eine Rechtsrotation um G ausführen, wodurch P zum Elter 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.

         // Fall_5
         P->color = BLACK;
         G->color = RED;
         if (N == P->left && P == G->left) { // Fall_5aL
             // Knoten ist links am Elter und Elter links am Großelter
             rotate_right(G);
         } else { // Fall_5aR
             // Knoten ist rechts am Elter und Elter rechts am Großelter
             rotate_left(G);
         }
         return; // Einfügung fertiggestellt
     } // Ende der do-Schleife
 } // Ende RBinsert

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 bei einem Binärbaum. Hat D genau ein Kind, so sei dieses mit N (für node) bezeichnet. Hat D kein Kind, so stehe N für einen seiner NIL-Knoten. In beiden Fällen sei P (für parent) der Elter von D, d (für direction) seine Kindesrichtung bei P (rechtes oder linkes Kind) und c (für color) seine Farbe.

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, das mit N bezeichnet sei. P sei der Elter des Ersatzknotens, d seine Kindesrichtung und c seine Farbe. Nun geben wir dem Ersatzknoten alle Rot-Schwarz-Baum-Eigenschaften des zu löschenden Knotens D, d. s. alle Verbindungen (Zeiger) und die Farbe. Die Eigenschaften P, d und c des Ersatzknotens haben wir quasi schon auf D übertragen.

Nach dieser Überlegung können wir davon ausgehen, dass der zu löschende Knoten D höchstens ein einziges echtes Kind hat; N ist sein Name; N kann ein NIL-Knoten sein.

Ist c (die Farbe von D) rot, so kann man D durch N ersetzen, welch letzterer wegen Forderung Nummer 2 »Kein roter Knoten hat ein rotes Kind« schwarz sein muss. Da P ebenfalls aufgrund von Forderung Nummer 2 schwarz gewesen sein muss, bleibt diese Forderung 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 c schwarz ist und N rot. Man färbt N schwarz und macht ihn an der Kindesrichtung d zum Kind von P. 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, c (die Farbe von D) und N schwarz sind. (Nach Beobachtung 2 ist dann N ein NIL-Knoten.) Nach der Ersetzung von D bei P durch N enthalten die durch N führenden Pfade einen schwarzen Knoten weniger als vorher, also einen weniger als die nicht durch N führenden Pfade.

Relativ zu N sei sein neues Geschwister, d. i. beim ersten Iterationsschritt das nicht-d-Kind von P, mit S (für sibling) und dessen linkes und rechtes Kind mit SL resp. SR bezeichnet. Da D schwarz war und kein NIL-Knoten, kann S kein NIL-Knoten sein.

Das Geschwister (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;
 }
Beobachtungen zu Geschwisterknoten in einem Rot-Schwarz-Baum
  1. Ein echter Knoten ohne echtes Geschwister ist immer rot, es sei denn, es handelt sich um die Wurzel.
  2. Ein schwarzer Knoten ohne echtes Geschwister ist ein NIL-Knoten, es sei denn, es handelt sich um die Wurzel.
  3. Ein echter schwarzer Knoten hat immer ein echtes Geschwister.
  4. Ein NIL-Knoten hat immer ein Geschwister.

Der Kopf der Funktion RBdelete1 zum Löschen eines schwarzen Knotens D mit einem Kindknoten N, der ein NIL-Knoten, also schwarz ist, könnte wie folgt aussehen:

 void RBdelete1(
     tree T, // Rot-Schwarz-Baum
     node D, // zu löschender Knoten (war schwarz)
     node N) // Kind von D (NIL-Knoten)
 {
     node P, S;

     P = D->parent; // Elter von D
     if (P != NULL) { // ersetze D bei P durch N
         if (D == P->left)
             P->left = N;
         else
             P->right = N;
     // Ein NIL-Knoten hat kein .parent.
     }
     do while (1) {
vorher Fall
Rot-
ation
nachher
Fall
d N P S SL SR d N P S SL SR
BlackRedNode.svg 1 BlackNode.svg return
MinusNode.svg BlackNode.svg RedNode.svg BlackNode.svg BlackNode.svg 2 PS MinusNode.svg RedNode.svg BlackNode.svg 4,…
MinusNode.svg BlackNode.svg BlackNode.svg BlackNode.svg BlackNode.svg 3 MinusNode.svg 1,…
MinusNode.svg RedNode.svg BlackNode.svg BlackNode.svg BlackNode.svg 4 BlackNode.svg BlackNode.svg RedNode.svg BlackNode.svg BlackNode.svg return
L MinusNode.svg BlackRedNode.svg BlackNode.svg RedNode.svg BlackNode.svg 5L SSL L MinusNode.svg BlackRedNode.svg BlackNode.svg RedNode.svg 6L
L MinusNode.svg BlackRedNode.svg BlackNode.svg c RedNode.svg 6L PS L BlackNode.svg BlackNode.svg c return
R MinusNode.svg BlackRedNode.svg BlackNode.svg BlackNode.svg RedNode.svg 5R SSR R MinusNode.svg BlackRedNode.svg BlackNode.svg RedNode.svg 6R
R MinusNode.svg BlackRedNode.svg BlackNode.svg RedNode.svg c 6R PS R BlackNode.svg BlackNode.svg c return
Löschen: Zusammenschau der Fälle

Löschen: Zusammenschau der Fälle

Die möglichen Konstellationen lassen sich in sechs Fälle gruppieren, zu denen es Transformationen gibt, die entweder in einem Schritt auf der betrachteten Ebene oder über weitere Iterationen auf höheren Ebenen zu einer Reparatur des Baumes führen.

Die 6 Spalten in der Gruppe vorher stellen die Konstellation (Farbe plus ggf. Kindesrichtung) von 5 Knoten vor der in der Spalte Fall → genannten Transformation dar. Angegeben ist die Farbe des Problemknotens N, und ausgehend von diesem die Farben der 4 weiteren relevanten Knoten. Das Zeichen MinusNode.svg zeigt die schwarze Farbe bei einem Knoten an und gleichzeitig, dass die Zahl der schwarzen Knoten auf den Pfaden durch ihn um 1 vermindert ist. Bei einem Eintrag in der Spalte Rotation ist eine Rotation an der Transformation beteiligt.

Die Gruppe vorher hilft beim Verifizieren der Vollständigkeit der Abdeckung durch die Fälle. Die 6 Spalten in der Gruppe nachher enthalten die Folgekonstellation (die Konstellation nach der Transformation). Ein return in der Spalte → Fall zeigt an, dass die Löschoperation mit der genannten Transformation abgeschlossen ist.

Andernfalls findet sich dort die Nummer der nachfolgenden Transformation. Dann enthält die Folgekonstellation die Farbe des neuen Problemknotens N, und ausgehend von diesem ggf. die Farben anderer Knoten zur Eingabe in diese Transformation. Der Eintrag 1,… verweist auf einen neuen Iterationsschritt eine Ebene weiter oben. Die Anzahl der Ebenen stimmt mit der Höhe h überein, somit können höchstens h Iterationen vorkommen. Nun ist der Aufwand für eine Iteration in \mathcal{O}(1) (d. h. beschränkt), also ist die Laufzeit für die gesamte Löschoperation in \mathcal{O}(h) = \mathcal{O}(\log n).

In den beiden Spalten d bedeutet L (wie Links) bzw. R (wie Rechts) die Kindesrichtung von N. In ein und derselben Zeile bedeuten die 2 Zeichen BlackRedNode.svg dieselbe Farbe, ebenso die 2 Buchstaben c.

Die Tabelle zeigt, dass bei einer Löschung maximal 3 Rotationen erforderlich sind. Denn nach einer Rotation kann keine weitere Iteration mehr kommen; Rotationen gibt es somit nur in der letzten Iteration.

Schleifeninvariante: Zu Beginn eines jeden Iterationsschritts ist der gerade betrachtete Problemknoten N schwarz. In dem zum Fall gehörigen Diagramm hat er eine blaue Kontur. Die Forderung Nummer 2 »Kein roter Knoten hat ein rotes Kind« ist überall erfüllt. Die Anzahl der schwarzen Knoten auf den Pfaden, die nicht durch N führen, ist ungeändert, während die Pfade durch N einen schwarzen Knoten weniger enthalten. (In den Diagrammen erleichtern die kleinen schwarzen Kreisflächen an den Spitzen der die Unterbäume darstellenden Dreiecke das Nachprüfen der Schwarztiefe.)

Zur Verdeutlichung wird bei jedem der Fälle ein Stück C-Code angegeben, das zeigt, wie der Baum repariert wird.[6]

Löschen 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).
         if (P == NULL) { // Fall_1
             T->root = N; // neue Wurzel
             return; // Löschung fertiggestellt
         }
         S = sibling(N); // Geschwister von 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.)

Löschen Fall 2
Löschen Fall 2

Das Geschwister S des Problemknotens N ist rot.                                                                  

In diesem Fall führt man eine Linksrotation um P aus, wodurch S zum Großelter von N wird. Danach invertiert man die Farben von P und S. Alle Pfade haben weiterhin dieselbe Anzahl an schwarzen Knoten, aber N hat nun ein schwarzes Geschwister (SL) und einen roten Elter (P), weswegen man nun zu Fall 4, 5, oder 6 weitergehen kann – mit N als dem Problemknoten.

         if (S->color == RED) { // Fall_2
             S->color = BLACK;
             P->color = RED;
             if (N == P->left) { // Fall_2L
                 rotate_left(P);
                 S = P->right; // neues Geschwister von N (schwarz)
             }
             else {              // Fall_2R
                 rotate_right(P);
                 S = P->left; // neues Geschwister von N (schwarz)
             }
         }
         // S->color == BLACK nach Fall_2 oder !Fall_2
Löschen Fall 3
Löschen Fall 3

Der Elter P des Problemknotens N, sein Geschwister S und die Kinder SL und SR von S sind alle schwarz.

In diesem Fall kann man 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. Dadurch wird die Ungleichheit im Unterbaum von P ausgeglichen. Alle Pfade, die durch P laufen, haben jedoch nun einen schwarzen Knoten weniger als die Pfade, die nicht durch P laufen, weshalb die Forderung Nummer 3 weiterhin überprüft werden muss. Durch diese Aktion wird das Problem um eine Ebene nach oben verschoben mit P als dem neuen Problemknoten.

         else {
             if (P->color == BLACK &&
                 S->left->color == BLACK &&
                 S->right->color == BLACK)
             { // Fall_3
                 S->color = RED;
                 N = P; // neuer Problemknoten
                 P = N->parent; // Elter von N
                 continue; // Iteration
             }
         }
Löschen Fall 4
Löschen Fall 4

Sowohl das Geschwister S des Problemknotens N als auch die Kinder SL und SR von S sind schwarz, aber der Elter 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.

         if (P->color == RED &&
             S->left->color == BLACK &&
             S->right->color == BLACK)
         { // Fall_4
             S->color = RED;
             P->color = BLACK;
             return; // Löschung fertiggestellt
         }
Löschen Fall 5
Löschen Fall 5

Das linke Kind SL des Geschwisters S ist rot, das rechte Kind SR wie auch das Geschwister S des Problemknotens N sind schwarz und N ist das linke Kind seines Elters P.

In diesem Fall kann man eine Rechtsrotation um S ausführen, sodass SL der neue Elter von S und zugleich zum Geschwister 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 ein schwarzes Geschwister (SL), dessen rechtes Kind (S) rot ist, womit man zum Fall 6 weitergehen kann. Weder N noch P noch die Schwarztiefe werden durch diese Transformation beeinflusst.

         // S->color == BLACK nach Fall_2 oder !Fall_2
         S->color == RED;
         if (N == P->left && // Fall_5L
             S->left->color == RED &&
             S->right->color == BLACK) {
             S->left->color = BLACK;
             rotate_right(S);
             S = S->parent; // neues Geschwister von N (schwarz)
             // S->right ist rot
         }
         else
         if (N == P->right && // Fall_5R
             S->right->color == RED &&
             S->left->color == BLACK) {
             S->right->color = BLACK;
             rotate_left(S);
             S = S->parent; // neues Geschwister von N (schwarz)
             // S->left ist rot
         }
Löschen Fall 6
Löschen Fall 6

Das Geschwister S des Problemknotens N ist schwarz, das rechte Kind SR von S rot und N ist das linke Kind seines Elters P. Die im Diagramm weiß dargestellten Knoten P und S haben dieselbe Farbe, rot oder schwarz.

In diesem Fall kann man eine Linksrotation um P ausführen, so dass S zum Großelter 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ßelter, 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 das neue Geschwister 3 (s. Diagramm) 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 Geschwisters 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 den Knoten S, welcher die Farbe von P angenommen hat. Somit ändert sich die Schwarztiefe eines solchen Pfades nicht.

Da die Anzahl der schwarzen Knoten bei den Pfaden, die durch N verlaufen, sich um 1 erhöht, und bei denen, die nicht durch N verlaufen, sich nicht ändert, ist die Forderung Nummer 3 wiederhergestellt.

         // Fall_6
         S->color = P->color;
         P->color = BLACK;
         if (N == P->left) { // Fall_6L
             rotate_left(P);
             // War: S->color == BLACK &&
             //      S->right->color == RED
             S->right->color = BLACK;
         }
         else { // Fall_6R
             rotate_right(P);
             // War: S->color == BLACK &&
             //      S->left->color == RED
             S->left->color = BLACK;
         }
         return; // Löschung fertiggestellt
     } // Ende der do-Schleife
 } // Ende RBdelete1

Höhenbeweis[Bearbeiten]

Wie schon in der Einleitung ausgeführt, 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 schlechtesten 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 Elemente speichert, gilt: h \leq 2 \log_2(n+2)-2.

Vorbemerkung

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

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
Der leere Baum mit einem NIL-Knoten ist der einzige Rot-Schwarz-Baum der Höhe h=0.
Ist h > 0 und gerade, dann bauen wir einen Minimalbaum für die Höhe h aus dem uns schon bekannten Minimalbaum für die 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 für die 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

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
Die Bäume mit einem roten resp. schwarzen Knoten und 2 NIL-Knoten sind die einzigen Rot-Schwarz-Bäume der Höhe h=1.
Ist h > 1 und ungerade, dann bauen wir einen Minimalbaum für die 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 für die 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

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.

Durchschnittliche und amortisierte Laufzeit[Bearbeiten]

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

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

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

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 reinen Einfügeszenario wird bspw. von den 3 möglichen Bäumen mit 3 inneren Knoten (Schlüsseln) nur der eine Baum mit schwarzer Wurzel und 2 roten Kindern (der linke in der Abb.) gebildet.
Beim Suchen und Traversieren ist wegen der identischen Form (Gestalt) der 3 Bäume alles Verhalten einschließlich Laufzeit gleich. Unterschiede gibt es bspw. bei den Einfügungen: Bei den rechten 2 Bäumen sind alle Einfügungen vom Typ Fall_2 und beim linken Baum alle vom Typ Fall_3 gefolgt von Fall_1.

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

Im Java Development Kit sind die Klassen TreeSet[9] und TreeMap[10] 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}
    etwas (mindestens um 1, meist aber um 2) niedriger 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 Elter voraussetzen kann. Wir denken uns also bei der Darlegung des Algorithmus eine rote Wurzel stets auf schwarz umgefärbt.
  6. a b Die Fälle sind aufeinander folgende und ineinander übergehende Programmabschnitte wie bei einem switch/case-Block, dessen Syntax aber Bedingungen in der hier benötigten Komplexität nicht zulässt. 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.
  7. Sedgewick 2011 S. 444 Proof sketch.
  8.  Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures. The Basic Toolbox. Springer, Berlin/Heidelberg 2008, ISBN 978-3-540-77977-3, doi:10.1007/978-3-540-77978-0. S. 165.
  9. http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html
  10. 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