Rot-Schwarz-Baum Komplexitätbei Elementen Platz Operation im Mittel,amortisiert Worst Case Suchen Querschritt Min, Max Einfügen Löschen Platz- und Zeit-Komplexitäten Ein Rot-Schwarz-Baum, auch RS-Baum oder RB-Baum, ( oder RB tree) ist eine Datenstruktur vom Typ binärer Suchbaum, die „sehr schnellen“ Zugriff auf die in ihr gespeicherten Schlüssel garantiert. Rot-Schwarz-Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben, 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. Die schnellen Zugriffszeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente (meist Paare vom Typ (Schlüssel,Wert)) werden durch zwei Forderungen erreicht, die die Balance des Baums in einer Weise festlegen, dass die Höhe eines Baums mit Elementen nie größer als sein kann.Diese Abschätzung ist scharf (s. Abschnitt Höhenbeweis) und für wegen
marginal genauer als das vielzitierte . Somit können die wichtigsten Operationen in Suchbäumen – Suchen, Einfügen und Löschen – garantiert in (s. Landau-Symbole) ausgeführt werden.
Definition Zusätzlich zu den Eigenschaften des binären Suchbaums hat jeder Knoten des Rot-Schwarz-Baums ein weiteres Attribut, genannt »Farbe«, das zwei Werte annehmen kann, genannt »rot« (RED) und »schwarz« (BLACK). Diese Einfärbung hat die folgenden zwei Forderungen zu Forderung !RR (»Nicht Rot-Rot«): Ein Kindknoten eines roten Knotens ist schwarz. Forderung S#= (»Schwarz-Zahl Gleich«): Jeder Pfad von einem gegebenen Knoten zu einem seiner Nachfahren mit Ausgangsgrad ≤1, d. h. zu Blättern oder Halbblättern, im Folgenden kurz Pfadenden enthält die gleiche Anzahl schwarzer Knoten. 322px|mini|Rot-Schwarz-Baumder Baumhöhe 4 und der Schwarzhöhe 2 Eine unmittelbare Folge aus den Forderungen ist, dass ein Halbblatt (bspw. der Knoten im Beispielbaum) schwarz und sein (einzelnes) Kind (der Knoten ) rot sein muss, denn beide sind Pfadenden, und der Pfad zum Pfadende ist um genau den Knoten kürzer.
Aus beiden Forderungen zusammen folgt ähnlich unmittelbar, dass ein schwarzer Knoten, der nicht die Wurzel ist, ein Geschwister hat.
Schwarzhöhe, Baumhöhe Die auf allen Pfaden von Pfadende zu Wurzel gleiche Anzahl schwarzer Knoten wird die »Schwarzhöhe« ()Bei Ben Pfaff ist die Schwarzhöhe eines Knotens die einheitliche Anzahl schwarzer Knoten auf allen Pfaden zu den Pfadenden im von ihm gewurzelten Teilbaum.Mehlhorn 2008 S. 155 färbt die Kanten rot/schwarz und zählt als Schwarztiefe () eines Knotens die Zahl der schwarzen Kanten von ihm zur Wurzel. genannt: des Baums, aber auch seiner Wurzel. Nach dieser Definition ist ein Knoten der Schwarzhöhe 0 ein rotes Blatt (dann ist seine Baumhöhe 1) wie bspw. die Knoten im Beispielbaum – oder ein unechter (und leerer) Knoten mit der Baumhöhe 0. In diesem Artikel sind schwarze Knoten echt (und Schlüssel tragend) und haben sowohl Schwarzhöhe wie Baumhöhe Die roten Knoten aber auch die schwarzen Knoten haben Schwarzhöhe 1. Die schwarzen Knoten haben Baumhöhe 2, die Knoten Baumhöhe 1, und ist der einzige Knoten mit Ausgangsgrad 1, das einzige Halbblatt.
Durch die zwei ForderungenEinige Autoren fordern noch, dass die Wurzel des Baums schwarz zu färben sei. Nicht jedoch z. B. Mehlhorn 2008 und Sedgewick. Tatsächlich ist diese Forderung ohne merkliche Bedeutung für das Laufzeitverhalten und stört die Rekursivität der Algorithmen etwas. Nun verletzt die Umfärbung einer roten Wurzel in schwarz keine der anderen Forderungen. In den Algorithmen für Einfügung und Löschung kann man jedoch mit einer Fallunterscheidung weniger auskommen, wenn man bei einem roten Knoten immer einen Elterknoten voraussetzen kann. wird die wichtigste Eigenschaft von Rot-Schwarz-Bäumen sichergestellt:
Ist die Schwarzhöhe des Baums, dann gibt es wegen der auf einem Pfad von der Wurzel zu einem Pfadende genau schwarze Knoten, aber wegen der höchstens einen roten Knoten mehr als schwarze, also insgesamt maximal Knoten. Damit gilt für die Zahl aller Knoten im Baum so dass der Rot-Schwarz-Baum immer gut genug balanciert ist – auf jeden Fall so gut, dass das Verhältnis zwischen der Baumhöhe für die gilt, und dem Logarithmus der Knotenzahl beschränkt bleibt. Diese logarithmische Beschränkung, die im Abschnitt Höhenbeweis formal bewiesen wird, ist aber gleichzeitig das informationstheoretische Optimum, d. h. es gibt keinen Binärbaum mit kleinerer maximaler Pfadlänge
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.
NIL-Knoten Dieser Artikel nimmt die im Artikel Binärer Suchbaum in dessen Abb. 1A aufgezeigte und bei vielen Baumstrukturen übliche Sichtweise ein, bei der die Knoten die Schlüssel tragen (knotenorientierte Speicherung), unabhängig davon, ob sie interne Knoten oder (interne) Blätter sind.
322px|mini|Derselbe Rot-Schwarz-Baum mit NIL-Knoten(Baum- und Schwarzhöhe sind 4 und 2 – wie oben) Sehr verbreitet in der Literatur über Rot-Schwarz-Bäume ist die nebenstehende und im Artikel Binärer Suchbaum in dessen Abb. 1B gezeigte Sichtweise, bei der – ebenfalls knotenorientiert – die die Schlüssel tragenden Knoten als intern angesehen werden, dem Baum aber zusätzliche Knoten, so genannte »NIL-Knoten«, als externe Blätter angeheftet sind, die an den Pfadenden für die (randlosen, „offenen“) Intervalle ( auch missing nodesJ. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan: Making Data Structures Persistent. In: Journal of Computer and System Sciences. Band 38, No. 1, 1989 (cs.cmu.edu)) zwischen den Schlüsseln stehen. Die Darstellung mit bringt das einseitige Pfadende (links am Knoten ähnlich deutlich heraus wie die paarigen Pfadenden an den Knoten Völlig unabhängig von der grafischen Darstellung lassen sich die NIL-Knoten sowohl als unterschiedslose Nullzeiger wie als unterschiedslose Zeiger zu ein und demselben Wächterknoten implementieren. Diese Option beim Zeigerwert wird zur Unterscheidung vom Nullzeiger im Text als oder NIL und im Beispielcode als NIL kenntlich gemacht.
Werden die NIL-Knoten jedoch als individuelle Knoten aufgefasst, dann kommt für sie eine Forderung hinzu, so dass folgende drei Forderungen aufzustellen NIL-Knoten sind schwarz. Kinder eines roten Knotens sind schwarz. Die Anzahlen schwarzer Knoten in einem Pfad von einem gegebenen Knoten zu jedem seiner NIL-Knoten sind gleich. Diese Auffassung hat für das Verständnis der Sachverhalte vernachlässigbaren Nutzen und hat bei „naiver“ Implementierung eher einen ungünstigen Einfluss.Werden nämlich die NIL-Knoten als minimale Rot-Schwarz-Knoten implementiert, so brauchen sie Speicher für zwei Kindzeiger, ggf. einen Elterzeiger, das Feld für die Farbe und ein Erkennungsfeld für die Eigenschaft »NIL-Knoten«. Bei Schlüssel tragenden Knoten braucht man NIL-Knoten, womit sich der Rot-Schwarz-Overhead mehr als verdoppelt. Die Verknüpfungen der NIL-Knoten mit den Schlüssel tragenden Knoten (bspw. bei den Rotationen) sind überdies zu pflegen, so dass sich auch die Laufzeit verlängert. Das bedeutet im Ergebnis einen erheblichen Aufwand für das Aufzeichnen und Pflegen von Informationen, die für die nachfolgenden Algorithmen nicht gebraucht werden oder sich unmittelbar aus den anderen Informationen herleiten lassen.
Datenstruktur Der nachfolgende Beispielcode, der in der Programmiersprache C formuliert ist, nimmt Bezug auf eine Deklaration des Baumknotens der folgenden Art:
struct RBnode // Knotenfeld { struct RBnode* child; // Zeiger zu ≤2 Kindknoten dieses Knotens // oder NIL: kein Kindknoten byte color; // RED oder BLACK ... // Benutzer-Daten (z. B. Schlüssel, Wert)
#define LEFT 0 #define RIGHT 1 #define left child[LEFT] // -> linker Kindknoten #define right child[RIGHT] // -> rechter Kindknoten #define RED 0 #define BLACK 1 Befindet sich NIL an einer Stelle im Baum, an der syntaktisch ein Zeiger zu einem Knoten erwartet wird, so soll dies verabredungsgemäß das Fehlen eines Knotens (einen Null- oder auch Wächterknoten) an dieser Stelle des Baums bedeuten (der Knoten gilt als unecht). M. a. W.: der von einem NIL-Knoten gewurzelte Teilbaum ist leer und hat Schwarz- und Baumhöhe 0. Sein Zeigerwert ist weniger wichtig als der Ort, wo dieser Wert in der Datenstruktur steht. Dieser Ort gibt die graphentheoretischen Beziehungen zu den anderen Elementen des Baums an: Ohne selbst einen Knoten zu repräsentieren, kann er in Kindesbeziehung, und damit auch in Geschwister- und Onkelbeziehung zu anderen Knoten stehen – niemals aber ein Elter sein.Seine Baumhöhe und Schwarzhöhe gelten beide als 0, und Farbe ist ihm auch nicht zugeordnet. Er hat einen Elter (wenn er die Wurzel ist, den Baum als logischen Elter), aber niemals einen Zeiger zum Elter.Funktionell entspricht er exakt dem NIL-Knoten, ohne dass ihm allerdings irgendeine Individualität zukäme.
Werden der Datenstruktur Rot-Schwarz-Baum Operationen zum Zugriff und zur Verwaltung beigegeben, so werden diese nur dann als zugehörig angesehen, wenn sie die Rot-Schwarz-Forderungen aufrechterhalten, indem sie insbesondere den Baum nach einer modifizierenden Operation überprüfen und wenn nötig reparieren. So erweitert wird die Datenstruktur zu einem Abstrakten Datentyp (ADT). Bei Suchbäumen gibt es im Englischen dafür auch die Charakterisierung als self-balancing tree.
Navigationsoperationen Die Navigationsoperationen, das sind die verschiedenen Suchoperationen, das Traversieren, Aufsuchen erstes oder letztes Element und ähnliche, lassen den Baum unverändert (nur lesender 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 eines Elements (oder einer Lücke) anhand seines Schlüssels ist die wichtigste unter den Navigationsoperationen. (Die des Rot-Schwarz-Baums versucht, auf diese Operation hin zu optimieren.) Sie unterstützt eine Art direkten Zugriff (im Gegensatz zum sequentiellen Zugriff der Traversierung) und wird in der Regel als vorausgehende Operation bei den Modifikationsoperationen (Einfügen oder Löschen) zum Auffinden der betreffenden Stelle im Baum eingesetzt.
Das Suchen setzt eine totale Quasiordnung auf der Menge der Schlüssel voraus, die am flexibelsten durch eine Vergleichsfunktion realisiert wird. Wenn Duplikate im Baum erlaubt sein sollen, dann empfiehlt sich eine leicht abgewandelte Suchfunktion.
Zeichenerklärung zu den Diagrammen Die komplizierteren Einzelfälle der Einfüge- und Löschoperation werden weiter unten in Diagrammen skizziert. Diese Diagramme stellen die für die Rebalancierung relevanten Beziehungen und Farben von Knoten heraus.
Ein Diagramm hat drei Spalten, wobei die linke Spalte die Überprüfung auf der untersten Stufe (ersten Iteration) eines Falles und die rechte die auf einer höheren Ebene desselben Falles beschreibt. Die mittlere Spalte unterteilt die Transformation in mindestens zwei Abschnitte: Der erste (und oberste, mit »Bedingung« beschriftete) Abschnitt zeigt die Ausgangskonstellation, eine eventuelle »Rotation« folgt im nächsten Schritt, danach eine »Umfärbung«, falls erforderlich. Wenn der Baum dann noch nicht rebalanciert ist, zeigt der letzte (mit »Neuzuweisung« beschriftete) Abschnitt die Konstellation nach der erneuten Zuweisung des Problemknotens und der durch ihn bestimmten anderen Knoten. Diese Konstellation wird zur Weiterbehandlung an den in der Spalte eingetragenen Fall übergeben.