Rot-Schwarz-Baum

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Rot-Schwarz-Baum
Komplexität
bei n Elementen
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)
Platz- und Zeit-Komplexitäten

In der Informatik ist der Rot-Schwarz-Baum (engl. red–black tree oder RB tree) eine Datenstruktur vom Typ Binärer Suchbaum, die „sehr schnellen“ Zugriff auf die in ihr gespeicherten Werte garantiert. Rot-Schwarz-Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben,[1] welcher sie symmetric binary B-trees nannte. Der heutige Name geht auf Leonidas J. Guibas und Robert Sedgewick zurück, die 1978 die rot-schwarze Farbkonvention einführten.[2] Die schnellen Zugriffszeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente werden durch 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) (s. Landau-Symbole) 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 externen Blatt-Knoten (d. s. die #NIL-Knoten) 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[5] (auch Schwarzhöhe, engl. black-height) des Baums genannt. Dabei seien in diesem Artikel die die Pfade abschließenden und immer schwarzen NIL-Knoten nicht mitgezählt, auch nicht bei der Baumhöhe.

Durch diese drei Forderungen[6] wird die wichtigste Eigenschaft von Rot-Schwarz-Bäumen sichergestellt:

Wegen der Forderung Nummer 2 kann es auf keinem Pfad von der Wurzel zu einem Blatt mehr rote als schwarze Knoten geben, 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 ein Pfad, auf dem nur schwarze Knoten liegen. Hierdurch ist ein Rot-Schwarz-Baum immer gut genug balanciert – auf jeden Fall so gut, dass das Verhältnis zwischen der Höhe des Baums und dem Logarithmus der Knotenzahl beschränkt bleibt. Diese asymptotische logarithmische Beschränkung, für die sich unter #Höhenbeweis ein formaler Beweis findet, ist aber gleichzeitig das informationstheoretische Optimum, d. h. es gibt keinen binären (Such)baum mit kleinerer maximaler Pfadlänge (= Höhe).

Bei den herausgehobenen Operationen Suchen, Einfügen und Löschen ist der auf einer Ebene des Baums anfallende Aufwand konstant. Also ist die Laufzeit höchstens proportional zur Anzahl der Knoten in einem Pfad, die wieder durch die Höhe limitiert ist, welche ihrerseits durch den Logarithmus der Knotenzahl limitiert ist.

Anmerkung: Dieser Artikel nimmt die im Artikel Binärer Suchbaum in dessen Abbildung 2 aufgezeigte und bei Rot-Schwarz-Bäumen außerordentlich verbreitete Sichtweise ein, bei der die internen 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 Abbildung mit dem Beispielbaum). Hierbei haben die Schlüssel tragenden Knoten immer genau zwei Kinder, und die schlüssellosen Blätter (die sog. „NIL-Knoten“ oder NIL-Blätter) haben die Farbe schwarz. Die Sichtweise vereinfacht die Beschreibung des Algorithmus, indem sie weniger Fallunterscheidungen erfordert. Sie präjudiziert aber die Implementierung nicht wirklich (bspw. von NIL-Knoten, die in den C-Beispielen als Nullzeiger implementiert sind).

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 (nur lesender (engl. read-only) Zugriff) und funktionieren im Prinzip auf jedem binären Suchbaum. Die dortigen Algorithmen und Angaben zur Komplexität gelten genauso für Rot-Schwarz-Bäume – mit der Präzisierung, dass die Höhe des Rot-Schwarz-Baums sich immer logarithmisch zur Anzahl der Knoten verhält.

Das Suchen (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]

Die ersten Aktionen beim Einfügen eines neuen Elements in den Rot-Schwarz-Baum sind dieselben wie bei einem 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; // NIL-Knoten
   N->right = NULL;
   N->parent = P;
   if (P != NULL) { // N ist nicht die Wurzel
     if (d == LEFT)
       P->left = N;
     else
       P->right = N;
   }
   do while (1) { // Beginn der do-Schleife

Einfügen: Schleifeninvariante: Zu Beginn jedes Iterationsschritts ist der Problemknoten N rot. (Er hat im Diagramm des resp. Falles eine blaue Kontur.) 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 »Kein roter Knoten hat ein rotes Kind« gilt für den ganzen Baum – mit der einzigen möglichen Ausnahme beim Paar PN. In den Diagrammen stellen die (nummerierten) Dreiecke (Rot-Schwarz-)Teilbäume dar. Sie haben alle dieselbe Schwarztiefe, es sei denn, das Dreieck trägt einen schwarzen Punkt an der Spitze. Dann ist die Schwarztiefe um 1 höher (und der Teilbaum hat eine schwarze Wurzel).

Bedingung Fall
Rota-
tion
Ergebnis
Fall
N P G U x N P G U x
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,…
RedNode.svg RedNode.svg BlackNode.svg BlackNode.svg i 4 PN RedNode.svg RedNode.svg BlackNode.svg BlackNode.svg a 5
RedNode.svg RedNode.svg BlackNode.svg BlackNode.svg a 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 auf der betrachteten Ebene oder über weitere Iterationsschritte auf höheren Ebenen zu einer Reparatur des Baumes führen.

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

  1. die Bedingung, d. i. die Konstellation, die den Fall definiert,
  2. die Fallnummer,
  3. die Ergebniskonstellation

enthält. Eine Konstellation (5 Spalten) besteht aus den 4 Farben der 4 Knoten N, P, G und U plus ggf. einer Angabe x zur Kindesrichtung von N, und zwar 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 Konstellationen in der Gruppe Bedingung genügen der Schleifeninvariante, und ihre logische Summe schöpft diese genau aus.

Die Transformation, deren Fallnummer in der Spalte Fall → verlinkt ist, transformiert die Eingabe in eine Konstellation, die durch die 5 Spalten in der Gruppe Ergebnis charakterisiert ist. Steht return in der Spalte → Fall, so schließt die Transformation hiermit die Einfügeoperation ab.

Andernfalls findet sich dort die Fallnummer der Bedingung, zu deren Test die Ergebniskonstellation mit ggf. neu zugewiesenem Problemknoten N und relativ zu diesem mit neuen Knoten P, G, U weitergereicht wird.

Der Eintrag 1,… bedeutet einen neuen Iterationsschritt – zwei Ebenen näher bei der Wurzel. Da die Anzahl der Ebenen mit der Höhe h übereinstimmt, können maximal \tfrac h2 Iterationen vorkommen. Nun ist der Aufwand für eine Iteration beschränkt (d. h. in \mathcal{O}(1)) und damit der für die gesamte Einfügeoperation in \mathcal{O}(h) = \mathcal{O}(\log n). Im Mittel ist der Aufwand gemäß Abschnitt #Durchschnittliche und amortisierte Laufzeit sogar konstant.

Bei einem Eintrag in der Spalte Rotation ist eine Rotation an der Transformation beteiligt. Man entnimmt der Tabelle sofort, dass bei einer Einfügung maximal 2 Rotationen vorkommen. Denn nach einer Rotation (Transformation_4 und Transformation_5) gibt es keine weitere Iteration, die Rotationen befinden sich endrekursiv am Ende der letzten Iteration.

Jeder Fall wird unter seiner Nummer erläutert und einschließlich Test und Transformation durch ein Stück C-Code genau beschrieben.[7]

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

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

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

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

     // Bedingung_2:
     if (P->color == BLACK) // Transformation_2:
       return; // Einfügung fertiggestellt
     // !Bedingung_2: Ab hier: RED: P
     G = P->parent; // Großelter von N
     U = uncle(N); // Onkel von N

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

Eine Umfärbung von P und U in schwarz und von G in rot stellt die Forderung Nummer 2 im von G gewurzelten Teilbaum wieder her. 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.

     // Bedingung_3:
     if (U != NULL && U->color == RED) { // Transformation_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.

Eine Linksrotation um P vertauscht die Rollen von N und P. Dadurch 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 Ergebniskonstellation entspricht der Eingangskonstellation des Falles 5 mit P als dem neuen Problemknoten.

     // Bedingung_4:
     if (N == P->right && P == G->left) { // Transformation_4R:
       // N ist rechts an P und P links an G (==> N innerer Enkel von G)
       rotate_left(P);
       // P und sein jetziger Elter N sind linke Kinder
       N = P; // neuer Problemknoten (RED) und äußerer Enkel von G
       P = G->left; // neuer Elter (RED)
     } else if (N == P->left && P == G->right) { // Transformation_4L:
       // N ist links an P und P rechts an G (==> N innerer Enkel von G)
       rotate_right(P);
       // P und sein jetziger Elter N sind rechte Kinder
       N = P; // neuer Problemknoten (RED) und äußerer Enkel von G
       P = G->right; // neuer Elter (RED)
     }
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.

Eine Rechtsrotation um G macht P zum Elter sowohl von N als auch von G. 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.

     // Bedingung_5:
     // N (RED) ist äußerer Enkel von G.
     // Transformation_5:
     if (N == P->left && P == G->left) { // Transformation_5L:
       // N und P sind linke Kinder
       rotate_right(G);
     } else { // Transformation_5R:
       // N und P sind rechte Kinder
       rotate_left(G);
     }
     P->color = BLACK;
     G->color = RED;
     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 (rechtes oder linkes Kind von P) 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 E maximal oder minimal ist, kann er kein rechtes resp. linkes Kind haben, hat also höchstens ein echtes Kind, das mit N bezeichnet sei. Jetzt sei P der Elter von E, d die Kindesrichtung und c die Farbe. Dem Ersatzknoten E geben wir alle Rot-Schwarz-Baum-Eigenschaften des zu löschenden Knotens D, d. s. alle Verknüpfungen (Zeiger von und zu D) und die Farbe. Die Eigenschaften P, d und c von E 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 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, also D ohne echtes Kind.) 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 (#Beobachtung 3).

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. In einem nicht-leeren Rot-Schwarz-Baum hat ein NIL-Knoten immer ein Geschwister.

Der Kopf der Funktion RBdelete1 zum Löschen eines schwarzen Knotens D ohne echtes Kind mit einem Kindknoten N könnte wie folgt aussehen:

 void RBdelete1(
   tree T, // Rot-Schwarz-Baum
   node D, // schwarzer zu löschender Knoten
   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 benötigt kein .parent.
   }
   do while (1) { // Beginn der do-Schleife

Löschen: Schleifeninvariante: Zu Beginn jedes 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 stellen die (nummerierten) Dreiecke Teilbäume dar, die alle dieselbe Schwarztiefe haben, es sei denn, das Dreieck hat einen schwarzen Punkt an der Spitze – dann ist die Schwarztiefe um 1 höher.

Bedingung Fall
Rota-
tion
Ergebnis
Fall
N P SL S SR d N P SL S SR d
BlackRedNode.svg 1 BlackNode.svg return
MinusNode.svg BlackNode.svg BlackNode.svg RedNode.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 BlackNode.svg RedNode.svg BlackNode.svg return
MinusNode.svg
MinusNode.svg
BlackRedNode.svg
BlackRedNode.svg
RedNode.svg
BlackNode.svg
BlackNode.svg
BlackNode.svg
BlackNode.svg
RedNode.svg
L
R
5 SSL
SSR
MinusNode.svg
MinusNode.svg
BlackRedNode.svg
BlackRedNode.svg
 
RedNode.svg
BlackNode.svg
BlackNode.svg
RedNode.svg
 
L
R
6
MinusNode.svg
MinusNode.svg
BlackRedNode.svg
BlackRedNode.svg
c
RedNode.svg
BlackNode.svg
BlackNode.svg
RedNode.svg
c
L
R
6 PS
PS
BlackNode.svg
BlackNode.svg
BlackNode.svg
BlackNode.svg
c
c
L
R
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 auf der betrachteten Ebene oder über weitere Iterationsschritte auf höheren Ebenen zu einer Reparatur des Baumes führen.

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

  1. die Bedingung, d. i. die Konstellation, die den Fall definiert,
  2. die Fallnummer,
  3. die Ergebniskonstellation

enthält. Eine Konstellation (6 Spalten) besteht aus den 5 Farben der 5 Knoten N, P, SL, S, SR plus ggf. einer Angabe d zur Kindesrichtung von N, und zwar steht L für Links bzw. R für Rechts. 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. In ein und derselben Zeile bedeuten die 2 Zeichen BlackRedNode.svg dieselbe Farbe, ebenso die 2 Buchstaben c.

Die Konstellationen in der Gruppe Bedingung genügen der Schleifeninvariante, und ihre logische Summe schöpft diese genau aus.

Die Transformation, deren Fallnummer in der Spalte Fall → verlinkt ist, transformiert die Eingabe in eine Konstellation, die durch die 6 Spalten in der Gruppe Ergebnis charakterisiert ist. Steht return in der Spalte → Fall, so schließt die Transformation hiermit die Löschoperation ab.

Andernfalls findet sich dort die Fallnummer der Bedingung, zu deren Test die Ergebniskonstellation mit ggf. neu zugewiesenem Problemknoten N und relativ zu diesem mit neuen Knoten P, SL, S, SR weiterzuleiten ist.

Der Eintrag 1,… bedeutet einen neuen Iterationsschritt auf der um 1 höheren Ebene im Baum, beginnend mit dem Test zum Fall 1. Die Anzahl der Ebenen stimmt mit der Höhe h überein, so dass höchstens h Iterationen vorkommen können. Nun ist der Aufwand für eine Iteration beschränkt (d. h. in \mathcal{O}(1)) und damit der für die gesamte Löschoperation in \mathcal{O}(h) = \mathcal{O}(\log n). Gemäß Abschnitt #Durchschnittliche und amortisierte Laufzeit ist der Aufwand im Mittel sogar konstant.

Bei einem Eintrag in der Spalte Rotation ist eine Rotation an der Transformation beteiligt. Und die Tabelle zeigt, dass bei einer Löschung maximal 3 Rotationen erforderlich sind. Denn nach einer Rotation (Transformation_2, Transformation_5 und Transformation_6) kommt kein weiterer Iterationsschritt; Rotationen gibt es somit nur in der letzten Iteration.

Jeder Fall wird unter seiner Nummer erläutert und einschließlich Test und Transformation durch ein Stück C-Code genau beschrieben.[7]

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).
     // Bedingung_1:
     if (P == NULL) { // Transformation_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.                                                                  

Eine Linksrotation um P macht S zum Großelter von N. 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 altem und neuem Problemknoten.

     // Bedingung_2:
     if (S->color == RED)
     { // ==> BLACK: P && S->left && S->right
       // Transformation_2:
       S->color = BLACK;
       P->color = RED;
       if (N == P->left) {  // Transformation_2L:
         rotate_left(P);
         S = P->right; // neues Geschwister von N (BLACK)
       }
       else {               // Transformation_2R:
         rotate_right(P);
         S = P->left; // neues Geschwister von N (BLACK)
       }
       // In beiden Fällen bleibt P == N->parent (RED).
     }
     // ==> BLACK: S (nach beidem, Transformation_2 und !Bedingung_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.

Eine Umfärbung von S von schwarz in rot vermindert in allen Pfaden, die durch S führen, die Zahl der schwarzen Knoten um 1. Das sind genau die Pfade im Teilbaum von P, die nicht durch N führen. Damit ist in diesem Teilbaum die Ungleichheit ausgeglichen. Aber alle Pfade, die durch P laufen, haben 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 // BLACK: S
     { // Bedingung_3:
       if (P->color == BLACK &&
         S->left->color == BLACK &&
         S->right->color == BLACK)
       { // Transformation_3
         S->color = RED;
         N = P; // neuer Problemknoten
         P = N->parent; // Elter von N
         continue; // Iteration
       }
     // !Bedingung_3 ==> RED: P || S->left || S->right
     }
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.

Eine Vertauschung der Farben von P und S lässt die Anzahl der schwarzen Knoten auf den Pfaden, die durch S laufen, unverändert, fügt aber auf allen Pfaden durch N einen schwarzen Knoten hinzu und gleicht damit den fehlenden schwarzen Knoten auf diesen Pfaden aus.

     // Ab hier: BLACK: S (Transformation_2 oder !Bedingung_2)
     // Bedingung_4:
     if (P->color == RED &&
       S->left->color == BLACK &&
       S->right->color == BLACK)
     { // Transformation_4:
       S->color = RED;
       P->color = BLACK;
       return; // Löschung fertiggestellt
     }
Löschen Fall 5
Löschen Fall 5

Der Problemknoten N ist das linke Kind seines Elters P. Das Geschwister S von N ist schwarz, und das rechte Kind SR von S (der äußere Neffe von N) ist schwarz, wogegen das linke Kind SL des Geschwisters S (der innere Neffe von N) rot ist.

Eine Rechtsrotation um S macht SL zum Elter von S und zugleich zum Geschwister von N. 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.

     // Ab hier: Wegen (Bedingung_3 || Bedingung_4)
     //                   [<==> beide BLACK: S->left && S->right]
     // ==> wenigstens eines von beiden RED: S->left || S->right
     // Bedingung_5:
     if (N == P->left && // Transformation_5L:
       S->right->color == BLACK) // ==> RED: S->left
     { S->color = RED; // S wird zum äußeren Neffen S->right von N
       S->left->color = BLACK;
       rotate_right(S);
       S = S->left;    // neues Geschwister von N (BLACK)
     }
     else
     if (N == P->right && // Transformation_5R:
       S->left->color == BLACK) // ==> RED: S->right
     { S->color = RED; // S wird zum äußeren Neffen S->left von N
       S->right->color = BLACK;
       rotate_left(S);
       S = S->right;   // neues Geschwister von N (BLACK)
     }
Löschen Fall 6
Löschen Fall 6

Der Problemknoten N ist das linke Kind seines Elters P. Das Geschwister S von N ist schwarz, und das rechte Kind SR von S (der äußere Neffe von N) ist rot. Die im Diagramm weiß dargestellten Knoten P und S haben dieselbe Farbe, rot oder schwarz.

Eine Linksrotation um P macht S zum Großelter von N. Nun reicht es, die Farben von S und P zu vertauschen 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 zusätzlichen 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, die durch N führen, nun einen zusätzlichen schwarzen Knoten passieren.

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

  1. Der Pfad verläuft durch SL, den beliebig eingefärbten Wurzelknoten des Teilbaums 3 (s. Diagramm), der zum neuen Geschwister von N wird. 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 in den Pfaden, die durch N führen, sich um 1 erhöht, und in denen, die nicht durch N gehen, sich nicht ändert, ist die Forderung Nummer 3 wiederhergestellt.

     // Bedingung_6: RED: äußerer Neffe von N
     // Transformation_6:
     S->color = P->color;
     P->color = BLACK;
     if (N == P->left) { // Transformation_6L:
       rotate_left(P);
       S->right->color = BLACK;
     }
     else { // Transformation_6R:
       rotate_right(P);
       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.

Rot-Schwarz-Bäume mit kleinster Knotenzahl zu gegebener Höhe
Rot-Schwarz-Bäume RBh der Höhen h=1,2,3,4,5,
jeweils mit minimaler Knotenzahl 1,2,4,6 resp. 10.

Zu h\geq 0 gibt es einen Rot-Schwarz-Baum der Höhe h mit

m_h = 2^{\lfloor(h+1)/2\rfloor} + 2^{\lfloor h/2 \rfloor} - 2

internen Knoten, und keinen mit weniger.[8]

Beweis

Damit ein Rot-Schwarz-Baum einer bestimmten Höhe h eine minimale Knotenzahl besitzt, muss er genau einen längsten Pfad enthalten, und dieser eine größtmögliche Anzahl roter Knoten, um eine möglichst große Baumhöhe mit möglichst kleiner Schwarztiefe zu erreichen. Seine Einfärbung hat also unten beim internen Blatt mit Rot zu beginnen, und sich in der Folge nach oben bis zur Wurzel mit Schwarz und Rot streng abwechselnd fortzusetzen. Außerhalb dieses die Baumhöhe definierenden Pfades hat er nur schwarze Knoten.[9][10] Denn das Entfernen eines roten Knotens beeinträchtigt die Rot-Schwarz-Eigenschaften nicht, sofern einer von seinen zwei (schwarzen) Kindknoten an seine Stelle nachrückt und der andere gleichzeitig einschließlich seines Teilbaums entfernt wird. Alle Teilbäume außerhalb des längsten Pfades sind somit vollständige Binärbäume mit ausschließlich schwarzen Knoten.

Es gibt genau einen Rot-Schwarz-Baum der Höhe h=1 mit einem roten internen Blatt, welches gleichzeitig die Wurzel ist. Also ist m_1 = 1 in Übereinstimmung mit 2^{\lfloor (1+1)/2\rfloor} + 2^{\lfloor 1/2 \rfloor} - 2 = 2^1+2^0-2.

Bei einem Minimalbaum (RBh in der Abbildung) der Höhe h>1 sind die zwei Kindbäume der Wurzel von unterschiedlicher Höhe: der höhere enthält den die Höhe definierenden längsten Pfad und ist ein Minimalbaum der Höhe h-1 mit m_{h-1} Knoten und der Schwarztiefe s:=\lfloor(h-1)/2\rfloor; der niedrigere ist ein vollständiger Binärbaum mit Höhe = Schwarztiefe s, hat also 2^s-1=2^{\lfloor(h-1)/2\rfloor}-1 interne Knoten. Damit ist rekursiv

m_h = (m_{h-1}) + (1) + (2^{\lfloor(h-1)/2\rfloor}-1)
(großer Kindbaum) (Wurzel) (kleiner Kindbaum)
woraus man
m_h = 2^{\lfloor h/2 \rfloor} + 2^{\lfloor(h-1)/2\rfloor} - 2 + 2^{\lfloor(h-1)/2\rfloor}
= 2^{\lfloor h/2 \rfloor} + 2^{\lfloor(h+1)/2\rfloor} - 2

ausrechnet.  ■

Der Graph der Funktion m_h ist konvex nach unten und stückweise linear mit den Ecken an den Punkten (h=2k\;|\;m_h=2^{k+1}\!-2). Ferner ist m_h= A027383(h–1) für h\geq 1 mit der Folge A027383 in OEIS.

Zur Höhe h gibt es 2^{h-1} Formen von Minimalbäumen, da die Position des längsten Pfades der Position eines externen Blattes des vollständigen Binärbaums der Höhe h-1 entspricht und dadurch auch die Lage der Knoten außerhalb dieses Pfades bestimmt ist. (Die Abbildung zeigt die äußerste linke Position.)

Umformung

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[11] 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 A001131(n+1) in OEIS gibt in Abhängigkeit von der Knotenzahl n die Gesamtzahl der Rot-Schwarz-Bäume, Folge A001137 in OEIS derer mit schwarzer Wurzel und Folge A001138 in OEIS derer mit roter Wurzel.

In einem reinen Einfügeszenario wird bspw. von den 3 möglichen Bäumen mit 3 internen Knoten (Schlüsseln) nur der eine Baum mit schwarzer Wurzel und 2 roten Kindern (der linke in der Abbildung) gebildet.
Beim Suchen und Traversieren ist wegen der identischen Form (Gestalt) der 3 Bäume alles Verhalten einschließlich Laufzeit gleich. Unterschiede gibt es aber bei den Einfügungen: Bei den rechten 2 Bäumen sind alle Einfügungen vom Typ Transformation_2 und beim linken Baum alle vom Typ Transformation_3 gefolgt von Transformation_1.

Verwandtschaft mit 2-3-4-Bäumen[Bearbeiten]

2 Kinder
3 Kinder
3 Kinder
4 Kinder

Die 4 kleinen Grafiken links und rechts zeigen, wie kleine Bausteine eines Rot-Schwarz-Baums (linke Hälften der Grafiken) mit einem (dicken) Knoten eines 2-3-4-Baums (rechte Hälften der Grafiken) zur Entsprechung gebracht werden können. Man erzeugt aus einem Rot-Schwarz-Baum einen 2-3-4-Baum, indem man rote Kinder entsprechend ihrer Kindesrichtung links oder rechts als Datenelemente in den schwarzen Elterknoten hereinholt.[12]

Der Rot-Schwarz-Baum des Beispiels dargestellt als 2-3-4-Baum

Umgekehrt kann man einen 2-3-4-Baum ganz einfach in einen Rot-Schwarz-Baum überführen: Aus einem Knoten mit 2 Datenelementen und 3 Kindzeigern (wie der Knoten [NIL,1,6] in der Abbildung) wird ein schwarzer Knoten (Datenelement) mit 1 Kindzeiger und einem roten Kindknoten (Datenelement), der noch 2 Kindzeiger enthält; aus einem Knoten mit 3 Datenelementen und 4 Kindzeigern (wie die Knoten [8,13,17] und [22,25,27] in der Abbildung) wird ein schwarzer Knoten (Datenelement) mit 2 roten Kindknoten (jeweils 1 Datenelement und 2 Kindzeiger).

Darüber hinaus gibt es Entsprechungen bei den Modifikationsoperationen (Einfügen, Löschen) zwischen Farbwechsel und Rotationen auf Seite der Rot-Schwarz-Bäume und den Aktionen Spalten und Verschmelzen bei den 2-3-4-Bäumen.

Im Gegensatz zu 2-3-4-Bäumen muss man bei Rot-Schwarz-Bäumen nicht den „Füllzustand“ (Speicherausnutzung, engl. fill factor) der Knoten beobachten und verwalten, weshalb letztere als sehr effiziente Art der Implementierung der 2-3-4-Bäume gelten.[13]

Vergleich mit AVL-Baum[Bearbeiten]

Die Menge der AVL-Bäume ist eine echte Teilmenge in der Menge der Rot-Schwarz-Bäume. Denn jeder Binärbaum, der das AVL-Kriterium erfüllt, lässt sich in einer das Rot-Schwarz-Kriterium erfüllenden Weise einfärben.[14]

Rot-Schwarz-, aber nicht AVL-Baum

Es gibt aber Rot-Schwarz-Bäume, die das AVL-Kriterium nicht erfüllen. Die nebenstehende Abbildung zeigt zum Beispiel einen Rot-Schwarz-Baum mit 6 (internen) Knoten und der externen Pfadlängensumme 21, während 20 die größte externe Pfadlängensumme bei AVL-Bäumen (und zugleich die kleinstmögliche für alle Binärbäume) dieser Größe ist. Konsequenterweise ist auch die Worst-Case-Höhe des AVL-Baums kleiner als die des Rot-Schwarz-Baums, und zwar um den Faktor (2 log2 Φ)−1 ≈ 0,720. Allgemein werden AVL-Bäume als besser balanciert und ihr Suchverhalten als günstiger angesehen.

Der Speicherplatzbedarf ist praktisch identisch: 1 Bit für die Rot-Schwarz-Farbe gegenüber 2 Bits[15] für den AVL-Balance-Faktor.

Das asymptotische Laufzeitverhalten für die angeführten Operationen ist im Mittel und im Worst Case identisch. Der Rot-Schwarz-Baum bietet allerdings amortisiert konstante Modifikationskosten und der AVL-Baum nur im Mittel konstante. Darüber hinaus können im Rot-Schwarz-Baum die für die Einfügung oder Löschung erforderlichen Farbänderungen und Rotationen schon während des Suchvorgangs – also beim Abstieg – vorgenommen werden.[16] Diese „Top-Down-Strategie“[17] ist bspw. für nebenläufige und persistente Programmierung interessant.[18]

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

Realistische Anwendungssituationen mit Performancedaten und -vergleichen – auch mit weiteren Suchalgorithmen und Spielarten der Datenstrukturen – finden sich bei Ben Pfaff.[19] Seine Ergebnisse zeigen in 79 Messungen unter anderem die sehr große Ähnlichkeit von AVL-Bäumen (AVL) und Rot-Schwarz-Bäumen (RB) mit Laufzeitverhältnissen AVLRB zwischen 0,677 und 1,077 bei einem Median von ≈0,947 und einem geometrischen Mittelwert von ≈0,910.

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

Im Java Development Kit sind die Klassen TreeSet[20] und TreeMap[21] 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
    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. Mehlhorn 2008 S. 154.
  6. a b c Einige Autoren fordern noch, dass die Wurzel des Baums schwarz zu färben sei. Nicht jedoch z. B. Mehlhorn 2008 und Sedgewick. Tatsächlich stört diese Forderung die Rekursivität und erübrigt sich. Denn ist die Wurzel rot, so müssen ihre Kinder nach Forderung Nummer 2 schwarz sein, und bei ihrer Umfärbung auf schwarz wird keine der anderen Forderungen verletzt. Um jedoch in den Algorithmen 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 der Algorithmen eine rote Wurzel stets auf schwarz umgefärbt.
  7. a b Für die Vorteile der iterativen Programmierung hinsichtlich Platz und Zeit gegenüber einer rekursiven Programmierung s. a. Binärer Suchbaum#Iterative Programmierung. Darüber hinaus erzwingt erstere eine genauere Beachtung der Knoteneigenschaften.
  8. Diese Minimalbäume spielen bei den Rot-Schwarz-Bäumen eine ähnliche Rolle wie die Fibonacci-Bäume bei den AVL-Bäumen.
  9. Sedgewick 2011 S. 444 Proof sketch
  10. s. a. die Überlegungen bei der Folge A027383 in OEIS
  11. Mehlhorn 2008 S. 165.
  12. Mehlhorn 1988 S. 193
  13. Mehlhorn 1988 S. 187
  14. s. „One should be able to color any AVL tree, without restructuring or rotation, to transform it into a Red-Black tree.“ Junghyun Chae in AVL Trees vs. Red-Black Trees? abgerufen am 14. Oktober 2015 und Beweis in AVL-Baum#Vergleich mit Rot-Schwarz-Baum
  15. oder auch nur 1 (s. Implementierung)
  16. Red Black Trees. Abgerufen am 14. Oktober 2015.
  17. Mehlhorn 1988 S. 197–198.
  18. s. a. Comparison of Binary Search Trees abgerufen am 14. Oktober 2015; oder Paul Callahan in AVL Trees vs. Red-Black Trees? abgerufen am 14. Oktober 2015
  19. Ben Pfaff: Performance Analysis of BSTs in System Software. Stanford University 2004.
  20. http://docs.oracle.com/javase/7/docs/api/java/util/TreeSet.html
  21. 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