Left-leaning red-black trees
Samstag, August 22nd, 2009Die meisten Spezifikationen des herkömmlichen Rot-Schwarz-Baums (red-black tree) wirken dank ausgiebiger Fallunterscheidung ziemlich unübersichtlich. Außerdem sind die üblichen Implementierungen durch die Verwendung von Hilfsknoten (”NIL”) und Referenzierung der Mutterknoten verkompliziert. Eine komplette Implementierung der delete-Methode ist sowieso nur schwer zu finden. Auch in der ursprünglichen Veröffentlichung des Schwarz-Rot-Baums durch Sedgewick und Guibas von 1978 war der Löschvorgang nicht vollständig spezifiziert. Unter anderem deshalb hat Robert Sedgewick im letzten Jahr den linksgerichteten Rot-Schwarz-Baum (left-leaning Red-Black Tree) vorgestellt.
Im Gegensatz zu anderen binären Suchbäumen wird jedem Knoten im Rot-Schwarz-Baum eine Farbe zugewiesen, anhand derer die Balance aufrechterhalten werden kann, nämlich Schwarz oder Rot. Für die Speicherung der Farbinformation wird entweder ein zusätzliches Feld in der Knotenstruktur angelegt oder beispielsweise der Knotenzeiger manipuliert, um Speicherplatz zu sparen. Auf einen roten Knoten dürfen unmittelbar nur schwarze Knoten folgen. Von jedem Knoten enthalten alle Pfade zu den von ihm erreichbaren Blattknoten die selbe Anzahl schwarzer Knoten. Die Wurzel ist immer schwarz.
Aus diesen drei zentralen Eigenschaften folgt eine maximale Höhe von 
insert und delete werden sie durch Rotationen und Farbverschiebungen aufrechterhalten.
Left-leaning red-black trees
Durchschnittliche und maximale Baumhöhe
(Durchschnitt aus 10000 zufälligen Bäumen)
Im linksgerichteten (linkslastigen) Rot-Schwarz-Baum wird nun zusätzlich vorausgesetzt, daß ein Knoten kein rechtes rotes ohne ein linkes rotes Kind haben darf. Dadurch fällt die Spiegelung der zu behandelnden Fälle von Ungleichgewicht weg, was den Code deutlich übersichtlicher macht. Die Wiederherstellung der Balance findet auf dem Rückweg der rekursiven Aufrufe von insert und delete statt. Sedgewick verspricht einen bis zu viermal kürzeren Code im Vergleich mit Implementierungen des herkömmlichen Rot-Schwarz-Baumes.
Ich habe die Implementierung von Sedgewick abgeschrieben und halbwegs gemäß Spezifikation vervollständigt. Weil die Implementation hauptsächlich zur Veranschaulichung dient, enthalten die Knoten lediglich ihren Schlüssel. Dafür speichert der Baum die Anzahl seiner Elemente (size) und kann seine Höhe ermitteln (height()). Beim Testen von insert überschritt Java nach dem Einfügen von ca. 7,5 Millionen Elementen seinen Heap Space und brach ab.
Einfügen des Elements 310
Einfügen (insert)
Auf der Suche nach dem Blatt, hinter dem der neue Knoten angehängt wird, wird nach Knoten mit zwei roten Kindern Ausschau gehalten. Die Kinder werden in diesem Fall schwarz, die Mutter rot eingefärbt. Dadurch wird verhindert, daß der neu angefügte Knoten (immer rot) sowohl eine rote Mutter als auch eine rote Tante hat. Dieser Fall könnte mit den vorgesehenen Mitteln nicht behoben werden.
Ergibt sich jedoch nach dem Anfügen der Fall zweier aufeinanderfolgender roter Knoten, kann dies durch eine Rechtsrotation um die Großmutter des angefügten Knotens geklärt werden. Daß es wirklich nur eine Rechtsrotation braucht, wird dadurch gewährleistet daß einzelne rote Kinder durch Linksrotation immer zu linken Kindern gemacht werden. Diese beiden Maßnahmen werden auf dem Rückweg der Rekursion in der Methode fixUp() ergriffen.
Löschen (delete)
Auf der rekursiven Suche nach dem zu löschenden Knoten schiebt der Algorithmus rote Knoten vor sich her, damit zum Schluß einfach ein rotes Blatt abgesägt werden kann, wodurch die Baumeigenschaften nicht verletzt werden. Die ensprechende Invariante für den Weg abwärts erfordert, daß entweder der aktuelle Knoten oder je nach Suchrichtung das linke oder rechte Kind rot ist. Um dies aufrechtzuerhalten werden die Hilfsfunktionen moveRedLeft() und moveRedRight() verwendet, die einen roten Knoten aus einem Unterbaum in den anderen verschieben oder zur Not erzeugen. Verletzungen der Linkslastigkeit durch vorangegangene Rechtsrotationen etc. werden wie beim Einfügen auf dem Rückweg der Rekursion mit fixUp() behoben.
Auswuchern nach dem Löschen des Schlüssels “0″
Das Löschen eines inneren Knotens n findet mittels Ersetzen des Knoteninhalts von n mit dem des kleinsten Nachkommens im rechten Unterbaum von n statt. Damit wird also der gelöschte Knoten mit dem lexikalisch nächstgrößeren Schlüssel überschrieben. Dazu dient die Methode deleteMin(). Aufgrund der immanenten Linkslastigkeit ist das Minimum eines (Unter-)Baums immer ein Blattknoten. Auch hier wird die erwähnte Invariante mitgenommen, so daß der ensprechende Blattknoten gelöscht werden kann, ohne daß nach Durchführung des fixup die Baumeigenschaften verletzt wären.
Ein Nachteil dieses Verfahrens ist, daß komplett schwarze Pfade auf ihre doppelte Länge anwachsen können. Damit tritt der worst case von einer Baumhöhe nahe 
Desweiteren schlägt sich die Übersichtlichkeit und Anschaulichkeit der Implementierung des linksgerichteten Rot-Schwarz-Baums besonders in der Methode delete nieder. Statt seitenweiser Fallunterscheidungen samt deren Spiegelung, wie beim symmetrischen Rot-Schwarz-Baum, braucht es für die left leaning version lediglich eine überschaubare Erweiterung des rekursiven Codes für den unbalancierten binären Suchbaum und ein paar kurze Hilfsfunktionen. Es ist weder die Speicherung der Knotentiefe noch die des Mutterknotens in der Knotenklasse notwendig.
Anzahl von Balanceoperationen beim Einfügen bzw. Löschen
(Durchschnitt bei 10000 Bäumen)
Eigenschaften
Aus den Eigenschaften des left-leaning red-black tree folgt eine maximale Höhe von 
