© photocase.com

Was haben ein Eichhörnchen und der Linux-Kernel gemeinsam? Beide durchqueren Bäume, um Dinge zu hamstern und wiederzufinden. Im direkten Vergleich geht der Linux-Kernel intelligenter zu Werke – wenn er auch etwas unfair mit zweifarbig lackierten Bäumen hantiert.

Eichhörnchen Sandy ist nicht mehr die Jüngste. Nicht nur die Knochen schmerzen, auch das früher sehr gute Gedächtnis lässt sie immer häufiger im Stich. Als sie letztes Jahr nach ihren Lieblings-Walnüssen vom Vorjahr suchte, musste sie sogar alle ihre Verstecke aufbuddeln. Wie im wirklichen Leben üblich verbargen sich die Leckereien erst unter dem letzten Vorratsstein.

Vielen Programmierern wird Sandys Leid sicherlich irgendwie bekannt vorkommen. Wie das altersschwache Eichhörnchen legen auch sie ihre Daten ungeordnet im Speicher ab. Als Behälter dienen dann ein Array oder eine lange, über Zeiger verkettete Liste, zum Beispiel:

typedef struct _element{
        void *zeigeraufmeinedaten;
        struct _element *naechstes;
} element;

Der Zeiger »naechstes« verweist einfach immer auf das jeweils folgende Element in der Liste. Sucht der Programmierer nun nach einem darin gespeicherten Element, muss er sich mühsam durch die gebildete Kette hangeln. Je mehr Dinge diese Liste speichert, desto länger braucht die Suche – im schlimmsten Fall muss man jedes Element einmal anfassen. Wer diese ineffiziente Suche auch noch in eine hübsche und möglichweise mehrfach verschachtelte Schleife verpackt, lässt die Laufzeit wie eine Rakete in den Himmel schießen.

Kerniges

Auch der Linux-Kernel kämpft häufig mit solchen Problemen. So muss sich das Betriebssystem beispielsweise merken, welche Speicherregionen bereits belegt sind. Diese Informationen könnte es in einer derartigen Liste ablegen. Möchte der Kernel nun feststellen, ob eine Speicherregion noch frei ist, müsste er diese unter Umständen recht lange Kette immer komplett durchlaufen. Ein anderes Beispiel liefert der so genannte I/O-Scheduler: Sobald ein Programm auf die Festplatte zugreifen möchte, sendet es eine entsprechende Anfrage an den Betriebssystemkern.

Dort übernimmt dann der I/O-Scheduler die weitere Regie (siehe [1]). Vereinfacht ausgedrückt merkt er sich alle eingehenden Aufträge zunächst in einer Warteschlange, um sie dann anschließend in eine optimierte Reihenfolge zu bringen. Das soll die Festplattenzugriffe beschleunigen. Je mehr Programme eine Anfrage stellen, mit desto mehr Daten muss der Scheduler jonglieren. Eine einfache Liste würde hier das gesamte System zu stark ausbremsen und den erhofften Geschwindigkeitsvorteil zumindest teilweise wieder auffressen.

Auf die Bäume

Weil Eichhörnchen Sandy zwar schon etwas senil ist, aber doch noch nicht auf den Kopf gefallen, soll in diesem Jahr ein ausgeklügeltes Lagersystem Ordnung in ihre Vorratshaltung bringen. Dazu hat sie sich extra einen schönen alten Baum mit vielen Astlöchern ausgesucht. Bevor sie ihre Nüsse dort verstaut, sortiert sie sie noch nach der Sorte. Die Informatiker hatten diese Idee schon etwas früher. Gegenüber Sandys realem Baum bieten sich jedoch erfreulicherweise ein paar zusätzliche Gestaltungsspielräume und somit einige Vorteile.

Er besteht jetzt aus einer Wurzel und vielen Gabelungen, den so genannten Knoten, die beliebige Daten aufnehmen können. Die Verbindungsäste werden Kanten genannt. Die allerletzten Knoten in der Baumkrone heißen wie ihre realen Pendants Blätter. Im Unterschied zum Eichhörnchen-Leben stehen Bäume in der Informatiker-Welt aber auf dem Kopf, die Wurzel wird also meist oben eingezeichnet, der Weg zu den Blättern verläuft nach unten.

Baum binär

Damit das Ganze noch etwas einfacher wird, darf in den folgenden Ausführungen jeder Knoten maximal zwei ausgehende Äste – pardon – Kanten aufweisen. In C lässt sich ein solcher Knoten so realisieren:

typedef struct _knoten{
        int data;
        struct _knoten *links;
        struct _knoten *rechts;
        struct _knoten *vater;
} knoten;

Die in einem Knoten gespeicherten Daten sollen im Beispiel der Einfachheit halber natürliche Zahlen sein. Selbstverständlich darf man stattdessen auch beliebige andere Informationen verwenden, vorausgesetzt sie sind irgendwie vergleichbar. In der Sprache der Mathematiker: Für die Knoten existiert eine (partielle) Ordnung.

Die beiden Zeiger deuten auf den linken beziehungsweise rechten Knotennachfolger im Baum. Diese Nachfolger heißen Söhne. Um später die Realisierung der Algorithmen etwas einfacher zu gestalten, speichert die Struktur auch noch den Vorgängerknoten, der konsequenterweise als Vater bezeichnet wird. Der Wurzelknoten lässt sich daran erkennen, dass seine Variable »vater« den Wert »NULL« besitzt.

Etikettenwahn

Sandy steht nun vor ihren Häufchen mit Nüssen. Von deutscher Gründlichkeit gepackt füllt sie jedes Häufchen sorgsam in einen kleinen Sack und beschriftet ihn mit der enthaltenen Nusssorte. So kann keine Nuss entwischen und die Etikettierung vereinfacht die Identifikation des Beutelinhalts im winterlichen Halbschlaf (Abbildung 1). Sandy gelangt ab sofort nur noch über eben jene Beschriftung an den Inhalt.

Programmierer kennen diese Situation. Beispielsweise arbeitet ein Thesaurus (Synonymwörterbuch) auf genau die gleiche Weise: Zu dem eingetippten Wort existiert ein Eintrag im virtuellen Wörterbuch. Fehlt er dort, gibt es zu diesem Wort kein Synonym.

Angelehnt an die Datenbankwelt heißt die Beschriftung des Sacks Schlüssel. Allgemein formuliert möchte der Benutzer zu einem Schlüssel möglichst schnell das zugehörige Element finden. Während Sandy es nach einer bestimmten Nusssorte gelüstet, sucht der Kernel zu einer Speicherregion den entsprechenden Belegungsplan.

Eine Datenstruktur, die diese Aufgabe löst, kennen Programmierer unter dem Namen Wörterbuch oder assoziatives Array. Es genügt also nicht mehr, in einem Knoten nur die Nüsse, also die Daten zu speichern. Stattdessen sind auch noch die besagten Schlüssel dort abzulegen. Die folgenden Beispiele machen es sich etwas einfacher und verwenden statt kompletter Nusssorten wieder nur aufsteigende natürliche Zahlen.

Verteiler

Als Nächstes überlegt Sandy, wie sie die Nusssäckchen am besten so auf die Astlöcher verteilt, dass sie bei der Suche nach einer bestimmten Sorte möglichst ohne viel zu klettern an das entsprechende Astloch gelangt. Nach kurzem Grübeln fällt ihr ein vermeintlich geniales System ein. Zunächst stellt sie sich an die Wurzel und blickt nach oben beziehungsweise beim Baum aus Abbildung 1 nach unten.

Abbildung 1: Ein Beispiel für einen Suchbaum, der Sandys Nüsse verwaltet. Die Schlüssel sind die Namen der Sorten im oberen Teil eines jeden Knotens, während der zugeordnete Inhalt im unteren Bereich seinen Platz findet.

Jetzt nimmt sie sich einen der Säcke und packt ihn in den ersten Knoten. Anschließend greift sie sich alle Nusssorten, deren Name im Alphabet vor der gerade eingelagerten Nusssorte stehen. Mit denen bewaffnet biegt sie auf den linken Ast beziehungsweise Teilbaum ab und beginnt das Spiel von neuem. Anschließend wiederholt sie mit den restlichen Nüssen das Vorgehen für den rechten Teilbaum. In ihm findet sie alle Nüsse, deren Namen im Alphabet nach den Nüssen in der Wurzel stehen.

Schlüssel vergleichen

Allgemein gilt somit für jeden Knoten im Baum, dass alle Schlüssel im linken Teilbaum kleiner und alle Schlüssel im rechten Teilbaum größer sind als der Schlüssel in der Wurzel. Das entstehende Gebilde ist ein binärer Suchbaum (Binary Search Tree). Wer ein Element im Suchbaum wiederfinden will, startet an der Wurzel und schaut nach, ob der gesuchte Schlüssel größer oder kleiner als der dort gespeicherte ist. Ist er kleiner, wechselt die Suche zum linken Nachfolger der Wurzel, andernfalls zum rechten. Das wiederholt sich so lange, bis ein Knoten mit dem gesuchten Schlüssel erreicht ist oder es nicht mehr weitergeht. Ist ein passender Knoten gefunden, stehen in ihm die gesuchten Daten (siehe Abbildung 2).

Abbildung 2: Eine Suche nach dem Schlüssel 5 läuft nach diesem Schema ab: Sie startet im binären Baum bei der Wurzel. Da 5 kleiner als 10 ist, wechselt der nächste Schritt zum linken Sohn. Hier steht die 3, die kleiner ist als 5. Also folgt der Wechsel zum rechten Sohn der 3, wo sich schließlich der gesuchte Knoten befindet.

Geringere Suchtiefe

Ist eine große Objekt-Menge zu verwalten und sollen diese möglichst schnell wiederzufinden sein, bringt ein solcher binärer Suchbaum im Vergleich zu einer einfachen Liste Vorteile. Betrachtet man einen Baum mit n Knoten, in dem jeder Knoten genau zwei Kinder hat, führt ein Weg von der Wurzel zu einem Blatt über maximal log2 n Knoten. Diese Weglänge heißt auch Tiefe des Baums. Wie leicht einzusehen ist, entfällt selbst im schlechtesten Fall der Zwang, alle gespeicherten Elemente anzufassen.

Leider hat Sandy ein Problem übersehen: Wenn sie die Nusshaufen in der aufsteigenden Reihenfolge ihrer Namen in den Baum packt, erhält sie wieder eine lange Liste. Denn dann liegt der Name der nächsten Nusssorte im Alphabet immer hinter der gerade abgelegten. Folglich läuft sie immer nur nach rechts. Dem kleinen Eichhörnchen bleibt nichts anderes übrig, als schon beim Einräumen der Nüsse aufzupassen und eine entsprechende Verteilung auf die Knoten zu wählen.

Programmierer haben es dabei glücklicherweise etwas einfacher. Sie können jeden Ast einfach absägen und Knoten an beliebigen Stellen im Baum wieder einkleben. Mit Hilfe dieser Werkzeuge versuchen sie nun nach dem Einfügen eines neuen Elements, diese unerwünschte Kettenbildung zu vermeiden und die Tiefe irgendwie wieder auf den Wert log2 n zu bringen.

An diesem Optimierungsproblem haben sich schon viele schlaue Leute versucht. 1972 probierte schließlich der Informatikprofessor Rudolf Bayer sein Glück. Er nahm einen binären Suchbaum und färbte jeden Knoten rot oder schwarz ein. Ausgeklügelte Optimierungsalgorithmen sollen mit diesen bunten Markierungen die Äste des Baums möglichst im Gleichgewicht halten.

Das Ergebnis ist heute allgemein als Rot-Schwarz-Baum (Red-Black-Tree) bekannt. Ein Knoten im Baum sieht in C wie folgt aus:

typedef struct _knoten{
        int key;
        void *data;
        enum { rot, schwarz } farbe;
        struct _knoten *links;
        struct _knoten *rechts;
        struct _knoten *vater;
} knoten;

Auch der I/O-Scheduler im Linux-Kernel greift für die eingehenden Anfragen auf gleich mehrere Rot-Schwarz-Bäume zurück. Er benutzt sie dabei als Basis für spezielle Warteschlangen, in denen er beispielsweise jeden eingehenden Leseauftrag ablegt. Als Schlüssel dienen unter anderem die angefragten Sektoren. Auf diese Weise kann der Scheduler viel schneller auf die einzelnen Aufträge zugreifen, wovon wiederum der Optimierungsvorgang profitiert.

Auch beim Speichermanagement kommen Red-Black-Trees zum Einsatz. Dort helfen sie beim schnellen Aufspüren von Speicherregionen und somit bei der Verwaltung des virtuellen Adressraums. Dank des Suchbaums kann der Kernel schnell feststellen, welche Bereiche belegt (eine Suche im Red-Black Tree ist erfolgreich) und welche noch frei sind (die Suche war erfolglos).

Bevor die nun folgenden Abschnitte einen genaueren Blick auf die Algorithmen zum Einfügen und Löschen von Elementen geben, eine kleine Vorwarnung: Die Abläufe sind kompliziert und lassen die Hirnwindungen Polka tanzen. Eine Implementierung ist daher nur wirtschaftlich, wenn größere Datenmengen verwaltet und wiedergefunden werden müssen. Wer nur fünf Elemente zu verwalten hat, ist mit einem herkömmlichen binären Suchbaum mit großer Wahrscheinlichkeit etwas schneller, da der gesamte Verwaltungsaufwand entfällt.

Regulierung

Ein Rot-Schwarz-Baum ist ein binärer Suchbaum, bei dem jeder Knoten entweder die Farbe Rot oder Schwarz besitzt. Zusätzlich gelten noch die folgenden Bedingungen:

1. Die Wurzel ist in jedem Fall schwarz.

2. Die Blätter des Baums sind schwarz und leer, sie speichern also weder Nüsse noch sonstige Informationen. Sie markieren lediglich das Ende des Baums. In C realisiert man die Blätter durch einen Null-Zeiger (»links« beziehungsweise »rechts« des Vaters enthält den Wert »NULL«) und nimmt an, dass diese Null-Knoten schwarz sind (Abbildung 3).

Abbildung 3: Ein Beispiel für einen Red-Black-Tree. Die Wurzel ist immer schwarz, die anderen Knoten sind entweder rot oder schwarz.

3. Ein roter Knoten hat nur schwarze Söhne.

4. Für jeden Weg von der Wurzel bis zu einem Blatt ist die Anzahl der durchlaufenen schwarzen Knoten immer gleich.

Abbildung 3 zeigt ein Beispiel für einen Rot-Schwarz-Baum. Er erfüllt alle vier Bedingungen, die selbstverständlich auch die folgenden Algorithmen berücksichtigen müssen. Die wichtigste Bedingung ist die letzte. Sie führt dazu, dass der Baum nicht entartet und zu lange Zweige ausbildet (was sich auch formal beweisen lässt).

Bevor es an das Einfügen und Löschen von Elementen geht, müssen noch ein paar Verwandtschaftsbeziehungen geklärt werden. Nachdem das Verhältnis von Vater und Sohn bereits erwähnt wurde, kommen nun noch der Großvater, der Onkel und der Bruder hinzu. Der Großvater ist wie im wahren Leben der Vater des Vaters (Abbildung 4). In Listing 1 ist zu sehen, wie man Onkel und Bruder eines Knotens ermittelt.

Abbildung 4: Die Verwandtschaftsbeziehungen der Knoten in der grafischen Darstellung. Eingezeichnet sind die Verwandten des Knotens mit der Beschriftung X.

01 knoten* onkel(knoten *n){
02     if (n->vater == n->vater->vater->links) return n->vater->vater->rechts;
03     else return n->vater->vater->links;
04 }
01 knoten* bruder(knoten *n){
02     if (n == n->vater->links) return n->vater->rechts;
03     else return n->vater->links;
04 }

Eine Suche funktioniert exakt so, wie bei den binären Suchbäumen. Die Farben der Knoten spielen hier keine Rolle und können ignoriert werden. Diesen Ablauf gießt Listing 2 in C-Code.

Komplizierter ist allerdings das Einfügen eines neuen Knotens. Als Erstes sucht man für das neue Element einen geeigneten Platz. Hierzu eignet sich der normale Suchalgorithmus. Da das Element noch nicht im Baum enthalten ist, wird er an einem Blatt stoppen. Jetzt erzeugt man einen neuen Knoten und hängt ihn als neuen Sohn an das gefundene Blatt. Anschließend bekommt er noch einen roten Anstrich. Allerdings könnte jetzt eine der vier Bedingungen verletzt sein. Es gilt also, herauszufinden, ob dies der Fall ist, und bei Bedarf entsprechende Gegenmaßnahmen einzuleiten.

01 knoten *suche(knoten *wurzel, int schluessel)
02 {
03      // sucht den Knoten mit dem Schlüssel "schluessel" im Suchbaum mit der Wurzel "wurzel"
04 
05      knoten *aktuell = wurzel;
06      while (aktuell != NULL)
07      {
08          if (schluessel < aktuell->key) aktuell = aktuell->links;
09          else if (schluessel > aktuell->key) aktuell = aktuell->rechts;
10          else if (aktuell->key == schluessel) return aktuell;
11      }
12      return NULL;
13 }

Von Fall zu Fall

Die Überprüfung und nötigenfalls die Wiederherstellung der Bedingungen übernimmt die spezielle Funktion »aufraeumen()«, die den neuen Knoten übergeben bekommt und alle nötigen Korrekturen vornimmt. Insgesamt muss die Funktion dazu fünf mögliche Fälle unterscheiden:

Erster Fall: Der neue Knoten ist gleichzeitig auch die Wurzel. Da es noch keine anderen Knoten im Baum gibt, hat sicherlich auch niemand etwas dagegen einzuwenden, die neue Wurzel einfach schwarz umzufärben.

Zweiter Fall: Der neue Knoten hat einen schwarzen Vater. Da der neue Knoten selbst rot ist, bleiben alle Bedingungen erfüllt, sodass die Bearbeitung hier abbrechen kann.

Dritter Fall: Der neue Knoten hat einen roten Vater und einen roten Onkel und verletzt somit Bedingung 4. In diesem Fall färbt man einfach den Onkel und den Vater schwarz und den Großvater rot. Damit könnte nun aber der Großvater eine der Bedingungen verletzen. Folglich müssen die Tests beim Urahn weitergehen, indem die Funktion »aufraeumen()« nun auf ihn anwendet wird (Abbildung 5). E

Abbildung 5: Einfügen, Fall 3: Onkel und Vater werden schwarz gefärbt, der Großvater rot. Die Aufräum-Funktion stellt sicher, dass die Bedingungen von Red-Black-Trees nicht verletzt werden.

Vierter Fall: (Abbildung 6) Der neue Knoten hat einen roten Vater und einen schwarzen Onkel. Wenn er zudem der rechte Sohn seines Vaters ist, folgt eine so genannte Linksrotation am Vater. Wie diese funktioniert, zeigt Abbildung 7: Die linke Situation wird in die rechte überführt. Dazu genügt es, die entsprechenden Zeiger der beteiligten Knoten umzubiegen. Erfreulicherweise hinterlässt die Rotation einen weiterhin gültigen Suchbaum.

Abbildung 6: Einfügen, Fall 4. Der neue Knoten N besitzt einen roten Vater und einen schwarzen Onkel. Befindet er sich auf der linken Seite des Vaters, ist zusätzlich eine Rechtsrotation um den Vater nötig.

Abbildung 7: Eine Linksrotation überführt den linken Baum in den rechten, eine Rechtsrotation macht aus dem rechten die linke Darstellung.

Falls der Vater des neuen Knotens der rechte Sohn des Großvaters ist, folgt dagegen eine symmetrische Rechtsrotation. In Abbildung 7 entspricht dies der Überführung des rechten Baums in den linken. Egal welche Richtung die Rotation nimmt, anschließend liegt aus Sicht des Vaters der fünfte und gleichzeitig letzte Fall vor, der noch zu überprüfen ist. Listing 3 zeigt die Funktionen für eine Rotation jeweils um den Knoten »n«.

01 void linksrotation(knoten *n) {
02     knoten *x = n;
03     knoten *y = x->rechts;
04     knoten *teilbaum1 = x->links;
05     knoten *teilbaum2 = y->links;
06     knoten *teilbaum3 = y->rechts;
07     knoten *vatervonx = x->vater;
08 
09     if(vatervonx != NULL) {
10         if (n == vatervonx->links) vatervonx->links = y;
11         else vatervonx->rechts = y;
12     }
13 
14     y->vater = vatervonx;
15     y->rechts = teilbaum3;
16     y->links = x;
17 
18     x->vater = y;
19     x->links = teilbaum1;
20     x->rechts = teilbaum2;
21 
22     if(teilbaum1 != NULL) teilbaum1->vater=x;
23     if(teilbaum2 != NULL) teilbaum2->vater=x;
24     if(teilbaum3 != NULL) teilbaum3->vater=y;
25 }
26 void rechtsrotation(knoten *n) {
27      knoten *y = n;
28      knoten *x = y->links;
29      knoten *teilbaum1 = x->links;
30      knoten *teilbaum2 = x->rechts;
31      knoten *teilbaum3 = y->rechts;
32      knoten *vatervony = y->vater;
33 
34      if(vatervony != NULL) {
35          if(n == vatervony->links) vatervony->links = x;
36          else vatervony->rechts = x;
37      }
38 
39      x->vater = vatervony;
40      x->links = teilbaum1;
41      x->rechts = y;
42 
43      y->vater = x;
44      y->links = teilbaum2;
45      y->rechts = teilbaum3;
46 
47      if(teilbaum1 != NULL) teilbaum1->vater = x;
48      if(teilbaum2 != NULL) teilbaum2->vater = y;
49      if(teilbaum3 != NULL) teilbaum3->vater = y;
55 }

Fünfter Fall: Der neue Knoten hat einen roten Vater und einen schwarzen Onkel. Wenn er außerdem der linke Sohn seines Vaters ist, folgt eine Rechtsrotation um den Großvater, entsprechend Abbildung 8. Ist der neue Knoten jedoch der rechte Sohn, erfolgt stattdessen eine Linksrotation. Anschließend vertauscht man die Farben zwischen Vater und Großvater. Listing 4 stellt die Fallunterscheidung noch einmal als C-Programm dar. Listing 5 zeigt den gesamten Einfügen-Algorithmus in C.

Abbildung 8: Einfügen, Fall 5. Der neue Knoten N besitzt einen roten Vater und Onkel. Befindet er sich auf der linken Seite des Vaters, ist zusätzlich eine Rechtsrotation um den Großvater nötig.

01 void aufraeumen(knoten *n)
02 {
03     knoten *deronkel = onkel(n);
04     knoten *grossvater = n->vater->vater;
05     knoten *vater = n->vater;
06 
07     if (n->vater == NULL){
08         // 1. Fall:
09         n->farbe = schwarz; return;
10     }
11     else {
12         // 2. Fall:
13         if (vater->farbe == schwarz) return;
14         else {
15              // 3. Fall:
16              if ((deronkel != NULL) && (deronkel->farbe == rot)){
17                   vater->farbe = schwarz;
18                   deronkel->farbe = schwarz;
19                   grossvater->farbe = rot;
20                   aufraeumen(grossvater);
21               }
22               else {
23                   // 4. Fall:
24                   if( (n == vater->rechts) && (vater == grossvater->links) ) {
25                          linksrotation(vater);
26                          // mache alten Vater zum aktuellen Knoten für 5. Fall
27                             n = n->links;
28                             deronkel = onkel(n);
29                             grossvater = n->vater->vater;
30                             vater = n->vater;
31                         } else if ((n == vater->links) && (vater == grossvater->rechts)){
32                             rechtsrotation(vater);
33                             // mache alten Vater zum aktuellen Knoten für 5. Fall
34                             n = n->rechts;
35                             deronkel = onkel(n);
36                             grossvater = n->vater->vater;
37                             vater = n->vater;
38                         }
39 
40                         // 5. Fall:
41                         vater->farbe = schwarz;
42                         grossvater->farbe = rot;
43                         if((n == vater->links) && (vater == grossvater->links))
44                              rechtsrotation(grossvater);
45                         else linksrotation(grossvater);
46               }
47          }
48     }
49 
50
51 }// Ende Aufräumen

01 void einfuegen(knoten *wurzel, knoten* neuerknoten)
02 {
03         // fügt den Knoten neuerknoten in den Red-Black Tree mit Wurzel "wurzel" ein
04         knoten *aktuell = wurzel;
05         knoten *vorgaenger = wurzel;
06         while(aktuell != NULL)
07         {
08                 vorgaenger = aktuell;
09                 if (neuerknoten->key < aktuell->key) aktuell = aktuell->links;
10                 else if (neuerknoten->key > aktuell->key) aktuell=aktuell->rechts;
11                 else if (aktuell->key ==neuerknoten->key) return;
12         }
13 
14
15         if (neuerknoten->key < vorgaenger->key) vorgaenger->links = neuerknoten;
16         else if (neuerknoten->key > vorgaenger->key) vorgaenger->rechts = neuerknoten;
17         neuerknoten->vater = vorgaenger;
18         neuerknoten->farbe = rot;
19         aufraeumen(neuerknoten);
20 }

Löschen

Knoten aus dem Red-Black-Tree zu löschen ist noch einmal komplizierter als das Einfügen. Zunächst sucht der bereits bekannte Suchalgorithmus nach dem zu löschenden Knoten. Ist er gefunden, startet erneut eine ausschweifende Fallunterscheidung. Der komplette Algorithmus – in C implementiert – ist auf [2] zu finden.

Erster Fall: Wenn der zu löschende Knoten zwei nicht leere Söhne besitzt, ist ein Nachfolger zu bestimmen. Das ist entweder das größte Element im linken Teilbaum oder das kleinste Element im rechten Teilbaum (für Baumexperten: der Inorder-Nachfolger). Jetzt überträgt man die Werte aus dem Nachfolger in den zu eliminierenden Knoten. Damit ist jetzt der Nachfolger überflüssig und kann entfernt werden. Er nimmt somit die Rolle des zu löschenden Knotens ein, für den noch die Fälle 2 und 3 zu durchlaufen sind.

Zweiter Fall: Der zu löschende Knoten hat zwei leere Blätter als Söhne (»links« und »rechts« sind Null-Zeiger). In diesem Fall nominiert man eines der beiden leeren Blätter als Nachfolger. Das andere Blatt ist sowieso leer, kann also ignoriert werden. Damit reduziert sich das Löschproblem auf den dritten Fall.

Dritter Fall: Der zu löschende Knoten hat genau ein Kind, das kein Null-Zeiger ist. In diesem Fall darf man zunächst den zu löschenden Knoten aus dem Baum werfen und sein einziges Kind zu seinem Nachfolger küren. War der zu löschende Knoten schwarz und ist der Nachfolger rot, lässt sich die möglicherweise verletzte Bedingung 3 dadurch erfüllen, indem man den Nachfolger einfach schwarz färbt.

Allerdings können nach dieser Aktion in folgenden Fällen weitere Bedingungen im Baum verletzt sein (diese Fälle lagert das Online-Listing in die Hilfsfunktion »aufraeumen_entfernen()« aus):

a) Der Nachfolger ist die neue Wurzel. Da er schwarz sein muss, ist nichts weiter zu tun.

b) Der neue Bruder des Nachfolgers ist rot. In diesem Fall tauscht man die Farben von Vater und Bruder. Anschließend folgt eine Linksrotation um den Vater, wenn der Nachfolger der linke Sohn seines Vaters ist. Andernfalls folgt eine Rechtsrotation (Abbildung 9). Als Ergebnis liegt eine Situation vor, die einer der Fälle 3d, 3e oder 3f behandelt.

Abbildung 9: Löschen, Fall 3b. Vater und Bruder tauschen die Farben. Anschließend stellt eine Rechtsrotation die Ordnung wieder her.

c) Der Vater, der Bruder und die Söhne des Bruders sind schwarz. In diesem Fall erhält der Bruder die Farbe Rot, womit die Bedingung 3 beim Vater verletzt ist. Für ihn ist die Fallunterscheidung mit »aufrauemen_entfernen()« erneut durchzuführen (Abbildung 10).

Abbildung 10: Löschen, Fall 3c. Der Bruder des neuen Knotens wird rot eingefärbt. Weil das die Red-Black-Tree-Bedingungen des Vaters verletzt, startet die Aufräum-Funktion bei ihm noch einmal.

d) Der Vater ist rot, der Bruder und die Kinder des Bruders sind hingegen schwarz. Dann genügt es, die Farbe zwischen dem Bruder und dem Vater zu tauschen (Abbildung 11).

Abbildung 11: Löschen, Fall 3d. Die einfache Variante: Es genügt, wenn Vater und Bruder des zu löschenden Knotens die Farbe tauschen.

e) Der Bruder und sein linker Sohn sind schwarz, der rechte Sohn des Bruders rot und der Nachfolger selbst ist der linke Sohn seines Vaters. Zunächst tauscht man die Farben zwischen dem Bruder und seinem rechten Sohn. Anschließend rotiert man rechts um den Bruder. Die symmetrische Fassung dieser Situation verläuft analog, nur eben links herum. Unabhängig von der Richtung liegt am Ende der Fall 3f vor (Abbildung 12).

Abbildung 12: Löschen, Fall 3e. Eine Zwischenstation: Am Anfang steht der Farbentausch zwischen Bruder und dem rechten Sohn. Nach einer Rechts- oder Linksrotation ergibt sich Fall 3f.

f) Der rechte Sohn des Bruders ist rot, der Bruder selbst schwarz und der Nachfolger ist der linke Sohn seines Vaters. Auch hier wechseln zunächst wieder die Farben, diesmal zwischen Bruder und Vater. Anschließend rotiert man noch links um den Vater. Der symmetrische Fall verläuft analog (Abbildung 13).

Abbildung 13: Löschen, Fall 3f. Dieses Mal tauschen Bruder und Vater die Farben. Mittelpunkt der darauf folgenden Rotation ist der Vater. Der symmetrische Fall verläuft analog.

Schnell, aber kompliziert

Red-Black-Trees beschleunigen die Suche nach einem in ihm befindlichen Element erheblich, sind aber nicht ganz einfach zu realisieren. Insbesondere bei großen Datenmengen lohnt sich der Implementierungsaufwand jedoch schnell. Wer sich dafür interessiert, warum welche Operation in den einzelnen Fällen durchzuführen ist, sollte zum besseren Verständnis die Algorithmen an einem konkreten Beispiel auf einem Blatt Papier nachvollziehen.

Im Laufe der Jahre wurden mehrere unterschiedliche Ansätze entwickelt, die den Realisierungsaufwand reduzieren und die komplexen Algorithmen vereinfachen sollen. Beispielsweise optimiert das Reiser-Dateisystem den binären Suchbaum erst dann, wenn die in ihm gepufferten Daten auf die Festplatte geschrieben werden.

Wer Red-Black-Trees einfach nur einsetzen will, kann auf einige fertige Implementationen zurückgreifen, zum Beispiel die Libredblack [3]. Ein gewisses Grundverständnis für den verwendeten Algorithmus empfiehlt sich natürlich trotzdem. (ofr)