4.6 Rot-Schwarz-Bäume

Soweit ich es verstanden habe, kann man die historische Entwicklung der Rot-Schwarz-Bäume begreifen als den Versuch, B-Bäume (insbesondere \((2,3)\)-Bäume oder \((2,4\))-Bäume) als Binärbäume darzustellen. Ganz allgemeinen können wir jeden B-Baum als Binärbaum "codieren":

Der Baum ganz links ist der ursprüngliche B-Baum. In der Mitte haben wir die Listen "auseinandergezogen"; das ist wahrscheinlich ist die Pointer-Struktur, die in unserer Datenstruktur existiert. Im dritte Baum ist der gleiche wie der in der Mitte, nur dass (1) wir ihn anders zeichnen und (2) wir uns merken, welche Knoten im Ursprungsbaum Geschwisterknoten ihrer (neuen) Elternknoten sind. Die Aussage "jeder Knoten hat höchtens drei Kinder" übersetzt sich nun zu "jeder rote Knoten ist das rechtes Kind eines schwarzen Elternknotens", einer Färbungsinvariante.

Der Vorteil gegenüber B-Bäumen ist, dass unsere Datenstruktur nun ganz einfach BSTs sind, allerdings mit einem zusätzlichen Bit pro Knoten. Der Nachteil ist, dass wir Rotationen, Knotenzerfall und -verschmelzung nun in einem BST simulieren müssen und darauf achten müssen, dass die Färbungsinvariante erhalten bleibt.

In der Tat gibt es nun mehrere Varianten von Rot-Schwarz-Bäumen, jede mit einer anderen Färbungsinvariante und anderen Mechanismen, diese nach einer insert- oder delete-Operation wiederherzustellen. Im folgenden verzichte ich auf weitere Parallelen mit B-Bäumen und stelle Rot-Schwarz-Bäume als eigene, unabhängige Datenstruktur dar.

Definition (Rot-Schwarz-Baum). Ein Rot-Schwarz-Baum (Red-Black-Tree, RBT) ist ein BST mit einer Zusatzinformation: jeder Knoten ist entweder schwarz oder rot. Für die formelle Definition nehmen wir die Version vollständiger Binärbäume, d.h., jeder Knoten ist ein Blatt \(\square\) oder ein innerer Knoten mit genau zwei Kindern. Die Schwarztiefe eines Knotens \(u\), bezeichnet mit \(\blackdepth(u,T)\) oder nur \(\blackdepth(u)\) ist die Anzahl schwarzer Knoten auf dem Weg von der Wurzel des Baumes zu \(u\). Diese Färbung muss drei Bedingungen erfüllen:
  1. Alle Blätter sind schwarz.
  2. Alle Blätter haben die gleiche Schwarztiefe.
  3. Keine zwei roten Knoten sind mit einer Kante verbunden.

Wir bezeichnen Bedingung 2 als Schwarz-Bedingung und 3 als Rot-Bedingung. Die Schwarzhöhe eines RBTs \(T\), kurz \(\blackheight(T)\), ist die Schwarztiefe eines Blattes (die ja alle die gleiche Schwarztiefe haben).

Hier sind ein paar Beispiele für die Schwarz-Bedingung und Rot-Bedingung. Ich habe hier die Schlüssel weggelassen, da sie für diese Beispiel nicht relevant sind.

Ein Rot-Schwarz-Baum mit vier inneren Knoten. Seine Schwarzhöhe ist 3 (wir rechnen die Blätter mit).
Kein Rot-Schwarz-Baum. Die Schwarz-Bedingung ist verletzt. Die zwei linken Blätter haben Schwarztiefe 4, alle anderen nur 3.
Kein Rot-Schwarz-Baum. Alle Blätter haben zwar die gleiche Schwarztiefe 3, allerdings sind zwei rote Knoten durch eine Kante verbunden. Die Rot-Bedingung ist also verletzt.

Jeder innere Knoten enthält natürlich einen Schlüssel (Key) und in der Praxis wohl auch noch einen Value. In Bezug auf die Keys ist der RBT ein ganz normaler BST (binärer Suchbaum):

Übungsaufgabe Finden Sie für den folgenden Baum eine gültige Rot-Schwarz-Färbung:
Zeigen Sie, dass das nur geht, wenn die Wurzel schwarz ist.

Um Rot-Schwarz-Bäume zu einer guten Dictionary-Datenstruktur zu machen, müssen wir zwei Dinge zeigen:

  1. Die gesamte Höhe eines RBTs ist logarithmisch: \(\height(T) \in O(\log n)\).
  2. Wir können insert und delete so implementieren, dass sie in \(O(\log n)\)) laufen und das Endresultat wieder ein gültiger RBT ist.
Theorem Sei \(T\) ein RBT mit schwarzer Wurzel und mit \(n\) inneren Knoten; sei und Dann gilt \( \height(T) \leq \log_2 (n+1)\).
Beweis. Sei \(h_b := \blackheight(T)\). Wir zeigen zuerst, dass \(h_b\) nicht groß sein kann; dann zeigen wir, dass \(\height(T)\) nicht viel größer als \(h_b\) werden kann.
Behauptung Für \(1 \leq i \leq h_b\) gibt es mindestens \(2^{i-1}\) schwarze Knoten der Schwarztiefe \(i\).
Beweis. Wir verwenden Induktion über \(i\). Für die Induktionsbasis, also \(i=1\), sehen wir, dass es genau einen schwarzen Knoten der Schwarztiefe 1 gibt: die Wurzel; auch ist \(2^{i-1} = 1\), so dass die Behauptung im Falle \(i=1\) stimmt.

Für den Induktionsschritt nehmen wir an, dass es mindestens \(2^{i-2}\) schwarze Knoten der Schwarztiefe \(i-1\) gibt. Sei nun \(u\) ein solcher schwarzer Knoten. Da \(\blackdepth(u) = i-1 \leq h_b\) gilt, ist er kein Blatt und hat daher zwei Kindbäume \(T_L, T_R\); von diesen hat jeder wiederum mindestens einen schwarzen Knoten (und sei es ein Blatt) von Schwarztiefe \(i\). Wir folgern: jeder der mindestens \(2^{i-2}\) schwarzen Knoten mit Schwarztiefe \(i-1\) hat mindestens zwei schwarze Nachfahren der Schwarztiefe \(i\), was eine Gesamtzahl von mindestens \(2 \cdot 2^{i-2} = 2^{i-1}\) solcher Knoten ergibt. Dies ist die behauptete Aussage: es gibt mindestens \(2^{i-1}\) schwarze Knoten der Schwarztiefe \(i\).

\(\square\)

Die Anzahl der Blätter ist also mindestens \(2^{h_b-1}\). Weiterhin wissen wir, dass ein vollständiger Binärbaum mit \(n\) inneren Blättern genau \(n+1\) Blätter hat. Es gilt also \begin{align*} n + 1 \geq 2^{h_b-1} , \end{align*} also \begin{align*} \blackheight(T) \leq \log_2(n+1) + 1 \ . \end{align*}

Zum Schluss setzen wir Schwarzhöhe mit der (traditionallen) Höhe in Bezug. Die Höhe ist die Anzahl der Kanten auf dem längsten Pfad von Wurzel zu Blatt. Auf so einem Pfad folgen nie zwei roten Knoten aufeinander. Wie lang kann also ein solcher Pfad sein, wenn er \(h_b\) viele schwarze Knoten enthält, wobei der erste Knoten (die Wurzel) und der letzte Knoten (das Blatt) schwarz sind? Im maximalen Fall wechseln sich schwarz und rot immer ab und wir haben \(h_b - 1\) rote Knoten, also insgesamt \(2h_b - 1\) Knoten, sprich \(2 h_b - 2\) Kanten. Daher gilt nun \( \height(T) \leq 2 h_b - 2 \leq 2 (\log_2(n+1) + 1 ) - 2 = \log_2 (n+1) \ . \) \(\square\)

Als nächstes müssen wir zeigen, wie wir find, insert und delete in logarithmischer Komplexität implementieren. Die Operation find läuft genau so wie auf einem normalen BST und braucht somit höchstens \(\height(T)\) viele Schritte.

Einfügen in einen Rot-Schwarz-Baum: insert

Für insert(x,T) führen wir zuerst eine normale BST-insert-Operation durch; wir erreichen also ein Blatt \(\square\) und ersetzen es durch einen inneren Knoten mit Schlüssel \(x\). Wir färben den neuen Knoten rot. Die Schwarzbedingung ist nach wie vor erfüllt, aber womöglich ist die Rot-Bedingung des Baumes verletzt. In diesem Falle müssen wir ihn reparieren. In Bildern:

Die Herausforderung liegt im effizienten Reparieren, also restore. Ein paar Worte im Voraus: die Prozedur restore arbeitet von unten nach oben und versucht, die Verletzung der Rot-Bedingung nach oben zu verschieben. Die Schwarz-Bedingung wird nie verletzt werden. Auch wird zu jedem Zeitpunkt die Rot-Bedingung an höchstens einer Kante im ganzen Baum verletzt sein. Wir werden zur Verdeutlichung die verletzte Kante auch rot markieren.

Fall 1, "roter Onkel".

Eine Kante unterhalb von u ist verletzt: beide Knoten sind rot. Der Vater von u muss schwarz sein (da die Elternkante von u nicht verletzt ist). Falls w, die Tante von u, auch rot ist, müssen wir den Baum nicht umbauen; es langt, die Färbung zu ändern. Beachten Sie, dass die Schwarztiefe eines jeden Blattes gleichbleibt: manche verlieren zwar einen schwarzen Vorfahren, nämlich v, gewinnen aber einen schwarzen hinzu, nämlich u oder w.

Die drei analogen Fälle, wo die verletzte Kante eine der drei anderen von u oder w nach unten ausgehenden ist, gehen genauso.

Im Fall 1 kann es jetzt sein, dass die Kante, die von v nach oben führt, verletzt ist; in diesem Falle müssen wir (iterativ, rekursiv) unsere restore-Funktion weiter oben fortsetzen.

Fall 2.1, "schwarzer Onkel", verletzte Kante liegt am Rand

Falls der Onkel w von x schwarz ist, müssen wir eine Rotation durchführen. Beachten Sie, dass die Schwarztiefe eines jeden Blattes unverändert bleibt: die Teilbäume \(T_4, T_5\) haben in beiden Bildern zwei schwarze Knoten über sich; die Teilbäume \(T_1, T_2, T_3\) jeder einen.

Fall 2.2, "schwarzer Onkel", verletzte Kante geht nach innen

Der Umabu in diesem Fall ist etwas komplizierter, weil x zwei Ebenen nach oben springt. Überzeugen Sie sich, dass auch in diesem Falle die Schwarztiefe jedes Blattes unverändert bleibt.

Fall 2 ist zwar komplizierter als Fall 1, allerdings können wir nun sicher sein, dass wir fertig sind: der Wurzelknoten des Teilbaumes ist in Fall 2.1 und Fall 2.2 schwarz; die Elternkante ist also nicht verletzt. Wir müssen restore nicht weiter oben fortsetzen. Überzeugen Sie sich bitte, dass in keinem der drei Fälle 1, 2.1 und 2.2 weiter unten eine Kante verletzt wird.

Alle betrachteten Fälle nehmen an, dass es oberhalb der verletzten Kante noch einen "Großvater" v gibt. Was, wenn dies nicht der Fall ist?

Fall 3, "kein Großvater"

Wir färben u schwarz. Dadurch steigt die Schwarzhöhe des gesamten RBTs um 1. Das dürfen wir natürlich nur tun, wenn u die globale Wurzel ist und nicht nur die eines Unterbaums. Klar, dass es so einen Fall geben muss: die vorherigen drei verändern nie die Schwarztiefe eines Blattes. Irgendwie muss aber die Schwarzhöhe des Baums ja wachsen können, und das kann sie nur, wenn die Schwarztiefe für alle Blätter simultan wächst.

Eine bemerkenswerte Eigenschaft von restore ist, dass die Laufzeit zwar proportional zur Höhe des Baumes sein kann, die Anzahl der Pointer-Veränderungen jedoch konstant ist: Fall 1 führt nur "Umlackierungen" um und verändert keine Pointer; Fall 2.1 und 2.2 verändern Pointer, stellen aber sicher, dass wir gleich danach fertig sind.

Theorem Die Operationen find und insert haben Laufzeit \(O(\log n)\).

Löschen aus einem Rot-Schwarz-Baum: delete

Wir gehen bei delete(x,T) erst einmal vor wie beim Löschen aus einem BST (nicht Treap). Wenn wir x lokalisiert haben, suchen wir den kleinsten Schlüssel y aus dem rechten Teilbaum von x, vertauschen die Schlüssel x und y (ohne die Farben der sie enthaltenden Knoten zu ändern). Der Schlüssel x liegt nun in einem Knoten, der mindestens ein leeres Kind hat. Wir löschen nun den Knoten, der x enthält:

Ich wähle hier die Farbe blau, um zu verdeutlichen, dass wir diesen Schritt tun, egal, welche Farbe u,x haben. Im weiteren identifizieren wir die Farbe rot mit 0 und schwarz mit 1. Um die Schwarztiefe eines Knotens zu ermitteln, müssen wir also nur die Farben seiner Vorfahren "addieren". Beachten Sie, dass das Löschen von x, so wie oben dargestellt, womöglich die Schwarzbedingung verletzt, z.B. wenn sowohl x als auch u schwarz sind. Wir müssen also unter Umständen die Farbe von u ändern. In den folgenden Abbildungen stelle ich die Farbe immer auch als Zahl neben den Knoten dar. Falls die Farbe nicht bestimmt ist, verwende ich Variable, wie zum Beispiel cx für "Farbe von x". Hier ist also nochmal obige Abbildung, jetzt der "richtigen" Färbung:

Konkret heißt das: falls genau einer von u,x schwarz ist und der andere rot, so wird u im neuen Baum schwarz. Falls beide rot sind, dann, Nein!, das kann ja gar nicht sein, dass beide, die ja mit einer Kante verbunden sind, rot sind. Falls beide schwarz sind, dann kriegt u im neuen Baum die Farbe 2, also, doppelt-schwarz?

Das ist der geniale Trick des Delete-Algorithmus: wir erlauben zeitweise die Farbe doppelt-schwarz, aber immer nur für höchstens einen Knoten. Durch Rotationen versuchen wir, den doppelt-schwarzen Knoten nach oben zu schieben. Wenn die Wurzel doppelt-schwarz ist, können wir sie getrost einfach-schwarz färben; in diesem Falle reduziert sich die Schwarztiefe aller Blätter um eins, somit auch die Schwarzhöhe des ganzen Baumes.

Im Folgenden schauen wir uns die Umgebung des doppelt-schwarzen Knotens an, den wir fortan mit u bezecihnen. Die Farbe des Vaters bleibt meistens unbestimmt und durch eine Variable c beschrieben. Entscheidend ist die Farbe des Bruders von u, den wir als y bezeichnen, und von dessen Kindern.

Fall 1, "schwarzer Bruder, zwei schwarze Neffen"

In diesem Fall können wir einen "Schwarz-Punkt" von u und seinem Bruder y abziehen und dem Vater hinzurechnen. Beachten Sie: falls der Vater schwarz war, ist er nun doppelt-schwarz. Wir müssen also weiter oben (iterativ oder rekursiv) weitermachen.

Fall 2.1, "schwarzer Bruder, roter Neffe"

Wir führen eine Rotation durch und färben mehrere Knoten um. Nach diesem Schritt sind wir fertig: kein Knoten ist mehr doppelt-schwarz. Überzeugen Sie sich, dass die Schwarztiefe aller Blätter gleich bleibt.

Fall 2.2, "schwarzer Bruder, rote Nichte"

Dieser Fall unterscheidet sich nicht wesentlich von 2.1.

Fall 3, "roter Bruder"

In diesem Falle müssen wir eine Rotation durchführen, die u nach unten drückt. Das ist erstmal schlecht, allerdings hat u nun einen schwarzen Bruder, somit landen wir in Fall 1, 2.1 oder 2.2.

Um die Laufzeit zu analysieren, sehen Sie, dass die Fälle 2.1 und 2.2 den doppelt-schwarzen Knoten verschwinden lassen. Fall 1 lässt ihn entweder verschwinden oder schiebt ihn um eins nach oben. Fall 3 schiebt ihn nach unten. Die Gefahr ist nun, dass sich Fall 3 und Fall 1 in eine Endlosschleife begeben. Dies ist nicht möglich: das Ergebnis von Fall 3 ist ein Baum, in dem u doppelt-schwarz ist, einen schwarzen Bruder und einen roten Vater hat. Das heißt, auch wenn auf Fall 3 der Fall 1 folgt, wird dieser sofort terminieren, weil \(c\), die Farbe des Vaterknotens, 0 sein wird und somit nach Anwendung von Fall 1 schwarz, nicht doppelt-schwarz. Wir schließen, dass die Laufzeit von delete durch die Höhe des Baumes begrenzt ist, also \(O(\log n)\).