Rot-Schwarz-Baum
Ein Rot-Schwarz-Baum ist in der Informatik eine vom binären Suchbaum abgeleitete Datenstruktur, welche sehr schnellen Zugriff auf die in ihr gespeicherten Werte garantiert. Rot-Schwarz Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben, welcher sie symmetric binary B-trees nannte. Der heutige Name geht auf Leo J. Guibas und Robert Sedgewick zurück, welche 1978 die rot-schwarze Farbkonvention einführten. Die schnellen Zugriffzeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente werden durch fünf Eigenschaften erreicht, welche zusammen garantieren, dass ein Rot-Schwarz-Baum immer balanciert ist, wodurch die Höhe eines Rot-Schwarz-Baumes mit n Werten nie größer wird als O(log2 n). Somit können die wichtigsten Operationen in Suchbäumen – suchen, einfügen und löschen – garantiert in O(log2 n) ausgeführt werden.
Eigenschaften
Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, in dem jeder Knoten eine Zusatzinformation – seine Farbe – trägt. Neben den Bedingungen, die an binäre Suchbäume gestellt werden, wird an Rot-Schwarz-Bäume jedoch noch die Forderung gestellt, folgende fünf Eigenschaften immer zu erfüllen:
- Jeder Knoten im Baum ist entweder rot oder schwarz.
- Die Wurzel des Baums ist schwarz.
- Jedes Blatt (NIL-Knoten) ist schwarz.
- Kein roter Knoten hat ein rotes Kind.
- Die Anzahl der schwarzen Knoten von jedem beliebigen Knoten zu einem Blatt (Schwarztiefe) ist auf allen Pfaden gleich.
Durch diese fünf Bedingungen wird die wichtigste Eigenschaft von Rot-Schwarz-Bäumen sichergestellt: Der längste Pfad von der Wurzel zu einem Blatt ist nie mehr als doppelt so lang wie der kürzeste Pfad von der Wurzel zu einem Blatt. Hierdurch ist ein Rot-Schwarz-Baum immer annähernd balanciert, was für die Operationen suchen, einfügen und löschen wichtig ist, da diese Laufzeitkosten proportional zur Höhe des Baumes haben. 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 – im Gegensatz zu normalen binären Suchbäumen – eine obere Schranke für die Laufzeit der Operationen suchen, einfügen und löschen garantieren.
Um zu verstehen, warum diese fünf Eigenschaften eine obere Schranke für die Laufzeit garantieren, reicht es sich zu verdeutlichen, dass aufgrund der vierten Eigenschaft auf keinem Pfad zwei rote Knoten aufeinander folgen dürfen, weswegen sich auf dem längsten Pfad immer ein roter Knoten mit einem schwarzen Knoten abwechselt, während auf dem kürzesten Pfad nur schwarze Knoten vorhanden sind. Da die fünfte Eigenschaft 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 hierfür findet man unter Höhenbeweis weiter unten im Artikel.
Anmerkung: Während es auch möglich ist, Binärbäume zu betrachten, bei denen die Knoten nicht immer genau zwei Kinder haben müssen, betrachten wir in diesem Artikel der Einfachheit halber nur Bäume, welche immer genau zwei Kinder haben. Hierzu werden eventuell fehlende Kinder als schwarzes Blatt ohne Suchschlüssel (sog. NIL-Blatt) eingeführt. Somit sind alle Knoten mit Suchschlüssel innere Knoten (und haben genau zwei Kinder) und alle Blätter NIL-Knoten. (siehe hierzu auch den Beispielbaum)
Operationen
Suchen
Die Suchoperation erben Rot-Schwarz-Bäume von den allgemeinen binären Suchbäumen. Für eine genaue Beschreibung des Algorithmus siehe dort.
Einfügen
Das Einfügen in den Rot-Schwarz-Baum funktioniert wie das Einfügen in einen binären Suchbaum, wobei der neue Knoten rot gefärbt wird, damit die Schwarztiefe des Baumes erhalten bleibt. Nach dem Einfügen können jedoch eventuell die zweite oder – was wahrscheinlicher ist – die vierte Eigenschaft des Rot-Schwarz-Baumes verletzt sein, weswegen es nötig werden kann, den Baum zu reparieren. Hierbei unterscheidet man insgesamt fünf Fälle, welche im folgenden genauer betrachtet werden.
Anmerkung: Wenn im folgenden von Vater (parent), Großvater (grandparent) und Onkel (uncle) die Rede ist, so sind diese jeweils relativ zum neu einzufügenden Knoten (N) zu sehen.
Zur Verdeutlichung wird bei jedem der fünf Fälle ein Stück C-Code angegeben, welches zeigt, wie der entstandene Baum repariert wird.
Den Großvater bzw. den Onkel eines Knotens kann man wie folgt bestimmen:
node grandparent(node n) {
return n->parent->parent;
}
node uncle(node n) {
if (n->parent == grandparent(n)->left)
return grandparent(n)->right;
else
return grandparent(n)->left;
}
Fall 1: Der neu eingefügte Knoten ist die Wurzel des Baumes. Da hierdurch die zweite Eigenschaft verletzt wird (Die Wurzel des Baums ist schwarz) färbt man die Wurzel einfach um. Da dieser Fall nur eintritt, falls man ein Element in den leeren Baum einfügt, braucht man sich nicht um weitere Reparaturen zu kümmern, da es im Baum nach dem Einfügen nur diesen einen Knoten gibt, weswegen keine der weiteren Eigenschaften verletzt werden kann.
void insert_case1(node n) {
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(n);
}
Fall 2: Der Vater des neuen Knotens ist schwarz. Hierdurch wird die fünfte Eigenschaft gefährdet, da der neue Knoten selbst wieder zwei schwarze NIL Knoten mitbringt und somit die Schwarztiefe auf einem der Pfade um eins erhöht wird. Da der eingefügte Knoten selbst aber rot ist, und beim Einfügen einen schwarzen NIL-Knoten verdrängt hat, bleibt die Schwarztiefe auf allen Pfaden erhalten.
void insert_case2(node n) {
if (n->parent->color == BLACK)
return; /* Alle Eigenschaften des Baumes sind immer noch gewahrt */
else
insert_case3(n);
}
Anmerkung: In den nun folgenden Fällen können wir annehmen, dass der einzufügende Knoten einen Großvater hat, da sein Vater rot ist, und somit nicht selbst die Wurzel sein kann (Die Wurzel des Baums ist schwarz). Da es sich aber bei einem Rot-Schwarz-Baum um einen Binärbaum handelt, hat der Großvater auf jeden Fall noch ein Kind (auch wenn es sich bei diesem um einen NIL-Knoten handeln kann).
 Fall 3: Sowohl der Onkel als auch der Vater des neuen Knotens sind rot. In diesem Fall kann man beide Knoten einfach schwarz färben, und im Gegenzug den Großvater rot färben, wodurch die fünfte Eigenschaft wiederhergestellt wird. Durch diese Aktion wird das Problem um ein Level nach oben verschoben, da durch den nun rot gefärbten Großvater die zweite oder vierte Eigenschaft verletzten sein könnte, weswegen nun der Großvater betrachtet werden muss. Dieses Vorgehen wird solange rekursiv fortgesetzt, bis keine der Regeln mehr verletzt wird. |
void insert_case3(node n) {
if (uncle(n) != NULL && uncle(n)->color == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(grandparent(n));
}
else
insert_case4(n);
}
Anmerkung: In den beiden noch verbleibenden Fällen wird der Einfachheit halber angenommen, dass der Vaterknoten das linke Kind seines Vaters (also des Großvaters des einzufügenden Knotens) ist. Sollte er das rechte Kind seines Vaters sein, so müssen in den beiden folgenden Fällen jeweils links und rechts vertauscht werden. Der Beispielcode berücksichtigt diesen Fall bereits.
 Fall 4: Der neue Knoten hat einen schwarzen Onkel und ist das rechte Kind seines roten Vaters. In diesem Fall kann man eine Linksrotation um den Vater ausführen, welche die Rolle des einzufügenden Knotens und seines Vaters vertauscht. Danach kann man den ehemaligen Vaterknoten mit Hilfe des fünften Falles bearbeiten. Durch die oben ausgeführte Rotation wurde ein Pfad (im Bild mit 1 markiert) so verändert, dass er nun durch einen zusätzlichen Knoten führt, während ein anderer Pfad (im Bild mit 3 markiert) so verändert wurde, dass er nun einen Knoten weniger hat. Da es sich jedoch in beiden Fällen um rote Knoten handelt, ändert sich hierdurch an der Schwarztiefe nichts, womit die fünfte Eigenschaft erhalten bleibt. |
void insert_case4(node n) {
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n->parent);
n = n->left;
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n->parent);
n = n->right;
}
insert_case5(n);
}
 Fall 5: Der neue Knoten hat einen schwarzen Onkel und ist das linke Kind seines roten Vaters. In diesem Fall kann man eine Rechtsrotation um den Großvater ausführen, wodurch der ursprüngliche Vater nun der Vater von sowohl dem neu einzufügenden Knoten als auch dem ehemaligen Großvater ist. Da der Vater rot war, muss nach der vierten Eigenschaft (Kein roter Knoten hat ein rotes Kind) der Großvater schwarz sein. Vertauscht man nun die Farben des ehemaligen Großvaters bzw. Vaters, so ist in dem dadurch entstehenden Baum die vierte Eigenschaft wieder gewahrt. Die fünfte Eigenschaft bleibt ebenfalls gewahrt, da alle Pfade, welche durch einen dieser drei Knoten laufen, vorher durch den Großvater liefen, und nun alle durch den ehemaligen Vater laufen, welcher inzwischen – wie der Großvater vor der Transformation – der einzige schwarze der drei Knoten ist. |
void insert_case5(node n) {
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(grandparent(n));
} else {
/* Ab hier gilt, n == n->parent->right und n->parent == grandparent(n)->right */
rotate_left(grandparent(n));
}
}
Löschen
Das Löschen eines Knotens aus einem Rot-Schwarz-Baum erfolgt analog zum Löschen eines Knotens aus binären Suchbäumen. Falls der zu löschende Knoten zwei Kinder hat (keine NIL-Knoten), so sucht man entweder den maximalen Wert im linken Teilbaum oder den minimalen Wert im rechten Teilbaum des zu löschenden Knotens, schreibt diesen Wert in den eigentlich zu löschenden Knoten, und entfernt den gefundenen Knoten einfach aus dem Rot-Schwarz-Baum. Dies kann man immer ohne Probleme machen, da der gelöschte Knoten maximal ein Kind gehabt haben kann, da sein Wert sonst nicht maximal respektive minimal gewesen wäre. Somit lässt sich das Problem auf das Löschen von Knoten mit maximal einem Kind vereinfachen. |
Anmerkung: Im folgenden werden wir also nur noch Knoten mit mindestens einem Kind betrachten. Hierbei werden wir eventuelle NIL-Knoten falls nötig ebenfalls als Kinder bezeichnen. (falls der Knoten sonst keine weiteren Kinder haben sollte).
Falls wir nun einen roten Knoten löschen wollen, so können wir ihn einfach durch sein Kind ersetzen, welches nach der vierten Eigenschaft (Kein roter Knoten hat ein rotes Kind) schwarz sein muss. Da der Vater des gelöschten Knotens ebenfalls aufgrund derselben Eigenschaft schwarz gewesen sein muss, wird die vierte Eigenschaft somit nicht mehr verletzt. Da alle Pfade, die ursprünglich durch den gelöschten roten Knoten verliefen, nun durch einen roten Knoten weniger verlaufen, ändert sich an der Schwarztiefe ebenfalls nichts, und die fünfte Eigenschaft (Die Anzahl der schwarzen Knoten von jedem beliebigen Knoten zu einem Blatt ist auf allen Pfaden gleich) bleibt auch erhalten. Ebenfalls noch einfach abzuarbeiten ist der Fall, dass der zu löschende Knoten schwarz ist, aber ein rotes Kind hat. Würden wir einfach den schwarzen Knoten löschen, könnte dadurch sowohl die vierte als auch die fünfte Eigenschaft verletzt werden, was wir jedoch umgehen können, indem wir das Kind schwarz färben. Somit treffen garantiert keine zwei roten Knoten aufeinander (der eventuell rote Vater des gelöschten Knotens und sein rotes Kind) und alle Pfade, welche durch den gelöschten schwarzen Knoten verliefen, verlaufen nun durch sein schwarzes Kind, wodurch beide Eigenschaften erhalten bleiben.
Die oben angegebene Löschung eines Knotens mit einem Kind können wir mit dem folgenden Programm beheben, welches den Knoten n mittels replace_node durch den Knoten child ersetzt.
Anmerkung: Der Code setzt voraus, dass eventuelle NIL-Knoten durch tatsächliche Knoten repräsentiert werden und nicht einfache NULL-Pointer sind.
void delete_one_child(node n) {
/* Vorbedingung: n hat mindestens ein echtes Kind (keine zwei Nullzeiger) */
if (is_leaf(n->right))
node child = n->left;
else
node child = n->right;
replace_node(n, child);
if (n->color == BLACK) {
if (child->color == RED)
child->color = BLACK;
else
delete_case1(child);
}
free(n);
}
Nach dem Einfügen müssen eventuell Reparaturen am Baum durchgeführt werden, da einige der Eigenschaften eines Rot-Schwarz-Baumes verletzt sein könnten. Hierbei unterscheidet man insgesamt fünf Fälle, welche im folgenden genauer betrachtet werden.
Falls sowohl der zu löschende Knoten als auch sein Kind schwarz sind, ersetzen wir zuerst den zu löschenden Knoten mit seinem Kind, und löschen danach den Knoten. Nun verletzt dieser Knoten (im folgenden Konfliktknoten genannt) jedoch die Eigenschaften eines Rot-Schwarz-Baumes, da es nun einen Pfad gibt welcher vorher durch zwei schwarze Knoten führte, jetzt aber nur noch durch einen führt. Somit ist die fünfte Regel (Die Anzahl der schwarzen Knoten von jedem beliebigen Knoten zu einem Blatt ist auf allen Pfaden gleich) verletzt. Je nach Ausgangslage werden nun sechs verschiedene Fälle unterschieden wie der Baum wieder zu reparieren ist, welche im folgenden genauer betrachtet werden.
Anmerkung: Wenn im folgenden von Vater (parent), Bruder (sibling), Großvater (grandparent) und Onkel (uncle) die Rede ist, so sind diese jeweils relativ zum ehemaligen Kind des zu löschenden Knoten (Konfliktknoten) zu sehen, welcher nach dem Platztausch jetzt an der Stelle steht an der der zu löschende Knoten selbst ursprünglich stand. Diesen Konfliktknoten selbst bezeichnen wir in den Diagrammen mit N.
Zur Verdeutlichung wird bei jedem der fünf Fälle ein Stück C-Code angegeben, welches zeigt wie der entstandene Baum repariert wird.
Den Bruder (sibling) eines Knotens kann man wie folgt bestimmen:
node sibling(node n) {
if (n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}
Fall 1: Der Konfliktknoten (N) ist die neue Wurzel. In diesem Fall sind wir fertig, da wir einen schwarzen Knoten von jedem Pfad entfernt haben und die neue Wurzel schwarz ist, womit alle Eigenschaften erhalten bleiben.
void delete_case1(node n) {
if (n->parent == NULL)
return;
else
delete_case2(n);
}
Anmerkung: In den Fällen 2, 5 und 6 nehmen wir an dass Der Konfliktknoten (N) das linke Kind seines Vaters ist. Sollte er das rechte Kind sein, so müssen in den drei Fällen jeweils links und rechts vertauscht werden. Der Beispielcode berücksichtigt diesen Fall bereits.
 Fall 2: Der Bruder (S) des Konfliktknotens ist rot. In diesem Fall invertieren wir die Farben des Vaters und des Bruders des Konfliktknotens und führen anschließend eine Linksrotation seinen Vater aus, wodurch der Bruder des Konfliktknotens zu dessen Großvater wird. Alle Pfade haben weiterhin die selbe Anzahl an schwarzen Knoten, aber der Konfliktknoten hat nun einen schwarzen Bruder und einen roten Vater, weswegen wir zu Fall 4, 5, oder 6 weitergehen können. |
void delete_case2(node n) {
if (sibling(n)->color == RED) {
n->parent->color = RED;
sibling(n)->color = BLACK;
if (n == n->parent->left)
rotate_left(n->parent);
else
rotate_right(n->parent);
}
delete_case3(n);
}
 Fall 3: Der Vater (P) des Konfliktknotens, sein Bruder (S) und die Kinder seines Bruders (SL respektive SR) sind alle schwarz. In diesem Fall können wir einfach den Bruder rot färben, wodurch alle Pfade die durch diesen Bruder führen – welches genau die Pfade sind welche nicht durch den Konfliktknoten selbst führen – einen schwarzen Knoten weniger haben, wodurch die ursprüngliche Ungleichheit wieder ausgeglichen wird. Jedoch haben alle Pfade welche durch den Vater laufen nun einen schwarzen Knoten weniger als jene Pfade die nicht durch den Vater laufen, wodurch die fünfte Eigenschaft immer noch verletzt wird. Um dies zu reparieren versuchen wir nun den Vaterknoten zu reparieren indem wir versuchen einen der sechs Fälle – angefangen bei Fall 1 – anzuwenden. |
void delete_case3(node n) {
if (n->parent->color == BLACK &&
sibling(n)->color == BLACK &&
sibling(n)->left->color == BLACK &&
sibling(n)->right->color == BLACK)
{
sibling(n)->color = RED;
delete_case1(n->parent);
}
else
delete_case4(n);
}
 Fall 4: Sowohl der Bruder des Konfliktknotens als auch die Kinder des Bruders (SL respektive SR) sind schwarz, aber der Vater (P) des Konfliktknotens rot. In diesem Fall können wir einfach die Farben des Vaters und des Bruders tauschen. Hierdurch bleibt die Anzahl der schwarzen Knoten auf den Pfaden welche nicht durch den Konfliktknoten laufen unverändert, fügt aber einen schwarzen Knoten auf allen Pfaden welche durch den Konfliktknoten führen hinzu, und gleicht somit den gelöschten schwarzen Knoten auf diesen Pfaden aus. |
void delete_case4(node n) {
if (n->parent->color == RED &&
sibling(n)->color == BLACK &&
sibling(n)->left->color == BLACK &&
sibling(n)->right->color == BLACK)
{
sibling(n)->color = RED;
n->parent->color = BLACK;
}
else
delete_case5(n);
}
 Fall 5: Das linke Kind (SL) des Bruders (S) ist rot, das rechte Kind (SR) wie auch der Bruder des Konfliktknotens (N) sind jedoch schwarz und der Konfliktknoten selbst ist das linke Kind seines Vaters. In diesem Fall können wir eine Rechtsrotation um den Bruder ausführen, sodass das linke Kind (SL) des Bruders dessen neuer Vater wird, und damit der Bruder des Konfliktknotens wird. Danach vertauschen wir die Farben des Bruders und seines neuen Vaters. Nun haben alle Pfade immer noch die gleiche Anzahl an schwarzen Knoten, aber der Konfliktknoten hat einen schwarzen Bruder dessen rechtes Kind rot ist, womit wir in den sechsten Fall kommen. Weder der Konfliktknoten selbst noch sein Vater werden durch diese Transformation beeinflusst. |
void delete_case5(node n) {
if (n == n->parent->left &&
sibling(n)->color == BLACK &&
sibling(n)->left->color == RED &&
sibling(n)->right->color == BLACK)
{
sibling(n)->color = RED;
sibling(n)->left->color = BLACK;
rotate_right(sibling(n));
}
else if (n == n->parent->right &&
sibling(n)->color == BLACK &&
sibling(n)->right->color == RED &&
sibling(n)->left->color == BLACK)
{
sibling(n)->color = RED;
sibling(n)->right->color = BLACK;
rotate_left(sibling(n));
}
delete_case6(n);
}
 Fall 6: Der Bruder (S) des Konfliktknotens (N) ist schwarz, das rechte Kind des Bruders (SR) rot und der Konfliktknoten selbst ist das linke Kind seines Vaters. In diesem Fall können wir eine Linksrotation um den Vater des Konfliktknotens ausführen, sodass der Bruder der Großvater des Konfliktknotens und der Vater seines ehemaligen rechten Kindes. Nun tauschen wir die Farben des Bruders und dem Vaters des Konfliktknotens und färben das rechte Kind des Bruders schwarz. Der Unterbaum hat nun in der Wurzel immer noch die selbe Farbe wodurch die vierte Eigenschaft erhalten bleibt. Aber der Konfliktknoten hat nun einen weiteren schwarzen Vorfahren: Falls sein Vater vor der Transformation noch nicht schwarz war, so ist er nach der Transformation schwarz, und falls sein Vater schon schwarz war, so hat der Konfliktknoten nun seinen ehemaligen Bruder (S) als schwarzen Großvater, weswegen die Pfade welche durch den Konfliktknoten laufen nun einen zusätzlichen schwarzen Knoten passieren. Falls nun ein Pfad nicht durch den Konfliktknoten verläuft, so gibt es zwei Möglichkeiten:
In beiden Fällen verändert sich die Anzahl der schwarzen Knoten auf den Pfaden also nicht, wodurch die vierte Eigenschaft wiederhergestellt werden konnte. Anmerkung: Für den weißen Knoten im Bild ist es irrelevant ob er rot oder schwarz ist, solange seine Farbe sich während der Transformation nicht ändert. |
void delete_case6(node n) {
sibling(n)->color = n->parent->color;
n->parent->color = BLACK;
if (n == n->parent->left) {
/* Here, sibling(n)->color == BLACK &&
sibling(n)->right->color == RED */
sibling(n)->right->color = BLACK;
rotate_left(n->parent);
}
else
{
/* Here, sibling(n)->color == BLACK &&
sibling(n)->left->color == RED */
sibling(n)->left->color = BLACK;
rotate_right(n->parent);
}
}
Höhenbeweis
Wie schon in der Einleitung motiviert ist die besondere Eigenschaft von Rot-Schwarz Bäumen dass sie in logarithmischer Zeit – genauer in O(log2 n) – 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 nun 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 log2(n+1)) überschreitet, so hat man bewiesen dass die oben genannten Operationen im schlimmsten Fall logarithmische Kosten haben, nämlich die genannten Kosten von 2 log2(n+1) für einen Baum in dem n Elemente gespeichert sind. Somit haben wir zu zeigen dass folgende Aussage gilt:
Für die Höhe h eines Ein Rot-Schwarz-Baumes, der n Schlüssel speichert, gilt:
Beweisidee
Zum Beweis dieser Eigenschaft muss man zuerst einen Hilfssatz über die Anzahl der inneren Knoten im Baum beweisen, und verbindet diese später mit der vierten Eigenschaft von Rot-Schwarz Bäumen (es folgen nie zwei rote Knoten aufeinander) um die oben genannte Eigenschaft zu beweisen.
Hilfssatz
Jeder Unterbaum von x enthält mindestens innere Knoten
Beweis des Hilfssatzes
Den Beweis führen wir durch vollständige Induktion über die Schwarzhöhe S eines Knotens x.
Induktionsanfang (S = 0)
Falls S = 0, so handelt es sich um einen NIL-Knoten, der somit keine Kinder hat. Insbesondere ist die Anzahl der inneren Knoten dieses Baumes 0.
Somit gilt:
Induktionsschritt (S > 0)
Geht man davon aus dass der betrachtete Knoten x ein innerer Knoten sein muss, so hat dieser genau zwei Kinder ( und ). Falls x die Schwarzhöhe S hat, so hat jedes seiner Kinder eine Schwarzhöhe von entweder S oder S-1, je nach dem ob das Kind rot oder schwarz ist. Da die Schwarzhöhe der Kinder nun jedoch kleiner oder gleich der Schwarzhöhe des Vaterknotens x ist, können wir die Induktionsannahme verwenden, welche uns garantiert dass jedes der Kinder wieder innere Knoten hat. Somit folgt für die Anzahl der inneren Knoten in dem Unterbaum zu dem x die Wurzel bildet, dass diese kleiner oder gleich ist. Somit folgt die Behauptung.
Beweis
Betrachtet man nun noch die vierte Eigenschaft von Rot-Schwarz Bäumen, so sieht man dass auf einem Pfad von der Wurzel zu einem Blatt mindestens die Hälfte der Knoten schwarz sein müssen. Somit muss die Schwarzhöhe der Wurzel selbst mindestens ½h sein. Nach dem eben bewiesenen Hilfssatz muss nun für die Anzahl der Knoten n im Baum gelten:
Bringt man nun noch die 1 auf die linke Seite und logarithmiert, so folgt:
Somit folgt die Behauptung dass ein Rot-Schwarz-Baum hat eine maximale Höhe h von hat, und damit die Operationen suchen, einfügen und löschen in logarithmischer Zeit erledigt werden können. 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 O(log2 n) liegen.
Siehe auch
Literatur
- Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest: Introduction to Algorithms. MIT Press, 2001, ISBN 0262531968
- Andrew Binstock, Jon Rex: Practical Algorithms for Programmers. Addison-Wesley Professional, 1995, ISBN 020163208X
- Rudolf Bayer: Symmetric Binary B-Trees. Data Structures and Maintenance Algorithms. In: Acta Informatica Volume 1, S. 290-306, 1972.
- Leo J. Guibas and Robert Sedgewick: A Dichromatic Framework for Balanced Trees, Proceedings of the 19th Annual Symposium on Foundations of Computer Science, S. 8-21, IEEE Computer Society, 1978.
Weblinks
