Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


15. Ausgeglichene Bäume



Rot-Schwarz-Bäume

Bemerkenswert ist, daß es möglich ist, 2-3-4-Bäume als gewöhnliche binäre Bäume (nur mit 2-Knoten) darzustellen, wobei nur ein zusätzliches Bit pro Knoten verwendet wird. Die Idee besteht darin, 3-Knoten und 4-Knoten als kleine binäre Bäume darzustellen, die durch »rote« Verkettungen miteinander verbunden sind, im Gegensatz zu den »schwarzen« Verkettungen, die den 2-3-4-Baum zusammenhalten. Die Darstellung ist einfach: Wie Abbildung 15.6 zeigt, werden 4-Knoten als drei 2-Knoten dargestellt, die mittels roter Verkettungen verbunden sind, und 3-Knoten werden als zwei 2-Knoten dargestellt, die mittels einer roten Verkettung verbunden sind (rote Verkettungen sind als dicke Linien gezeichnet). (Für einen 3-Knoten ist jede der beiden Orientierungen zulässig.)

Abbildung 15.6
Abbildung 15.6 Rot-schwarze Darstellung von 3- und 4-Knoten.

Abbildung 15.7 zeigt eine Möglichkeit, wie der letzte Baum aus Abbildung 15.3 dargestellt werden kann. Wenn wir die roten Verkettungen beseitigen und die Knoten, die sie verbinden, zusammenfassen, ist das Ergebnis der 2-3-4-Baum aus Abbildung 15.3. Das zusätzliche Bit pro Knoten wird benutzt, um die Farbe der auf den betreffenden Knoten zeigenden Verkettung zu speichern; 2-3-4-Bäume, die in dieser Weise dargestellt sind, wollen wir als Rot-Schwarz-Bäume bezeichnen.

Abbildung 15.7
Abbildung 15.7 Ein Rot-Schwarz-Baum.

Die »Neigung« jedes 3-Knotens wird durch die Dynamik des noch beschriebenen Algorithmus bestimmt. Zu jedem 2-3-4-Baum gibt es viele ihm entsprechende Rot-Schwarz-Bäume. Es wäre möglich, eine Regel einzuführen, nach der alle 3-Knoten in der gleichen Weise geneigt sein müssen, doch es gibt keinen Grund dafür.

Diese Bäume haben viele strukturelle Eigenschaften, die sich unmittelbar aus ihrer Definition ergeben. Zum Beispiel treten längs eines jeden beliebigen Pfades von der Wurzel zu einem äußeren Knoten niemals zwei rote Verkettungen nacheinander auf, und alle Pfade besitzen die gleiche Anzahl schwarzer Verkettungen. Zwar ist es möglich, daß ein Pfad (schwarz-rot im Wechsel) doppelt so lang ist wie ein anderer (nur schwarz), jedoch sind alle Pfadlängen nach wie vor proportional zu log N.

Ein auffälliges Merkmal von Abbildung 15.7 ist die Anordnung von mehrfach auftretenden Schlüsseln. Man kann sich leicht überlegen, daß jeder Algorithmus auf ausgeglichenen Bäumen es ermöglichen muß, daß Datensätze mit Schlüsseln, die mit einem gegebenen Knoten übereinstimmen, beiderseits dieses Knotens angeordnet werden; andernfalls könnten lange Ketten von gleichen Schlüsseln zu einem großen Ungleichgewicht führen. Dies hat zur Folge, daß wir nicht wie im vorangegangenen Kapitel durch wiederholte Aufrufe der Suchprozedur alle Knoten mit einem gegebenen Schlüssel finden können. Das stellt jedoch kein echtes Problem dar, da alle Knoten in dem durch einen gegebenen Wurzelknoten spezifizierten Unterbaum, die den gleichen Schlüssel wie dieser Knoten haben, mit Hilfe einer einfachen rekursiven Prozedur von der Art der Prozedur treeprint aus dem vorigen Kapitel aufgefunden werden können. Eine Alternative dazu wäre, unterschiedliche Schlüssel in der Datenstruktur zu fordern (mit verketteten Listen von Datensätzen mit mehrfach auftretenden Schlüsseln).

Eine sehr schöne Eigenschaft von Rot-Schwarz-Bäumen ist, daß die Prozedur treesearch für die gewöhnliche Suche im Binärbaum ohne Veränderung abläuft (abgesehen von der Frage mehrfach auftretender Schlüssel, die im vorangegangenen Absatz erörtert wurde). Wir werden die Farben der Verkettungen implementieren, indem wir zu jedem Knoten ein boolesches Speicherfeld red hinzufügen, welches wahr ist, wenn die auf den Knoten zeigende Verkettung rot ist, und falsch, wenn sie schwarz ist; die Prozedur treesearch untersucht dieses Feld einfach nie. Folglich wird durch den ausgleichenden Mechanismus kein »Ballast« zu der von der grundlegenden Suchprozedur benötigten Zeit hinzugefügt. Da jeder Schlüssel nur einmal eingefügt wird, aber in typischen Anwendungsfällen viele Male gesucht werden kann, erhalten wir im Endergebnis verkürzte Suchzeiten (da die Bäume ausgeglichen sind) bei relativ geringen Kosten (da während der Suchvorgänge keine Operationen für das Ausgleichen ausgeführt werden).

Darüber hinaus ist der zusätzliche Aufwand für das Einfügen sehr gering: Wir haben nur dann etwas anderes zu tun, wenn wir 4-Knoten antreffen, und es gibt nicht viele 4-Knoten im Baum, da wir sie immer aufspalten. Die innere Schleife benötigt nur einen zusätzlichen Test (falls ein Knoten zwei rote Nachfolger hat, ist er Teil eines 4-Knotens), wie die folgende Implementation der Prozedur insert (Einfügen) zeigt:

    function rbtreeinsert(v: integer; x:link): link;
      var gg,g,p: link;
      begin
      p:=x; g:=x;
      repeat
        gg:=g; g:=p; p:=x;
        if v<x^.key then x:=x^.l else x:=x^.r;
        if x^.l^.red and x^.r^.red then x:=split(v,gg,g,p,x);
      until x=z;
      new(x); x^.key:=v; x^.l:=z; x^.r:=z;
      if v<p^.key then p^.l:=x else p^.r:=x;
      rbtreeinsert:=x;
      x:=split(v,gg,g,p,x);
    end;

In diesem Programm bewegt sich x im Baum abwärts wie zuvor, und gg, g und p zeigen ständig auf den drittletzten, vorletzten und unmittelbaren Vorgänger von x im Baum. Um zu sehen, warum alle diese Verkettungen benötigt werden, betrachten wir das Hinzufügen von Y zu dem obigen Baum. Wenn der äußere Knoten auf der rechten Seite des S und X enthaltenden 3-Knotens erreicht ist, ist gg R, g ist S und p ist X. Nun muß Y hinzugefügt werden, damit ein 4-Knoten entsteht, der S, X und Y enthält, wobei der in Abbildung 15.8 dargestellte Baum erzeugt wird.

Abbildung 15.8
Abbildung 15.8 Einfügen (von Y) in einen Rot-Schwarz-Baum.

Wir brauchen einen Zeiger, der auf R (gg) weist, da die rechte Verkettung von R so geändert werden muß, daß sie auf X und nicht auf S zeigt. Um genau zu sehen, wie dies vor sich geht, müssen wir die Arbeitsweise der Prozedur split (Aufspalten) untersuchen. Betrachten wir die Rot-Schwarz-Darstellung für die zwei Transformationen, die wir ausführen müssen: Falls wir einen 2-Knoten haben, der mit einem 4-Knoten verbunden ist, so müssen wir diese in einen 3-Knoten verwandeln, der mit zwei 2-Knoten verbunden ist; falls wir einen 3-Knoten haben, der mit einem 4-Knoten verbunden ist, so müssen wir diese in einen 4-Knoten verwandeln, der mit zwei 2-Knoten verbunden ist. Wenn ein neuer Knoten auf der untersten Ebene hinzugefügt wird, so wird er als der mittlere Knoten eines imaginären 4-Knotens betrachtet (das heißt, man stellt sich vor, daß z rot ist, obwohl dies nie explizit getestet wird).

Die Transformation, die erforderlich ist, wenn wir einen mit einem 4-Knoten verbundenen 2-Knoten vorfinden, ist leicht, und die gleiche Transformation läßt sich ausführen, wenn wir einen 3-Knoten haben, der mit einem 4-Knoten auf dem »rechten« Weg verbunden ist, wie die Abbildung 15.9 zeigt. Demzufolge beginnt split damit, daß x als rot und die Nachfolger von x als schwarz markiert wird.

Abbildung 15.9
Abbildung 15.9 Aufspaltung von 4-Knoten mit Wechsel der Farbe.

Damit bleiben die beiden anderen in Abbildung 15.10 dargestellten Situationen übrig, die vorliegen können, wenn wir einen 3-Knoten vorfinden, der mit einem 4-Knoten verbunden ist. (In Wirklichkeit gibt es vier Situationen, da für 3-Knoten mit der entgegengesetzten Orientierung auch die hierzu spiegelbildlichen Situationen eintreten können.) In diesen Fällen sind im Zuge des Aufspaltens des 4-Knotens zwei rote Verkettungen nacheinander entstanden, eine unzulässige Situation, die korrigiert werden muß. Dies kann im Programm leicht getestet werden: Wir haben soeben x rot markiert, daher müssen, wenn der Vorgänger p von x auch rot ist, weitere Schritte unternommen werden. Die Situation ist nicht zu ungünstig, da wir drei Knoten haben, die durch rote Verkettungen verbunden sind; alles, was wir tun müssen, ist, den Baum so zu transformieren, daß die roten Verkettungen vom gleichen Knoten ausgehen.

Abbildung 15.10
Abbildung 15.10 Aufspaltung von 4-Knoten mit Wechsel der Farbe:
Notwendigkeit der Rotation.

Zum Glück gibt es eine einfache Operation, mit der der gewünschte Effekt erzielt wird. Beginnen wir mit dem leichteren der beiden Fälle, dem oberen in Abbildung 15.10, wo die roten Verkettungen die gleiche Orientierung haben. Das Problem besteht darin, daß der 3-Knoten nicht die richtige Orientierung besaß; demzufolge strukturieren wir den Baum so um, daß sich die Orientierung des 3-Knotens ändert, wodurch dieser Fall auf den zweiten Fall von der Abbildung 15.9 zurückgeführt wird, wo die Änderung der Farbe von x und von dessen Nachfolgern genügte. Das Umstrukturieren des Baumes zur Änderung der Orientierung eines 3-Knotens erfordert die Änderung von drei Verkettungen, wie in Abbildung 15.11 gezeigt ist; wir bemerken, daß Abbildung 15.11 mit Abbildung 15.8 übereinstimmt, wobei jedoch der 3-Knoten, der N und R enthält, »rotiert« ist. Die linke Verkettung von R wurde so geändert, daß sie auf P zeigt, die rechte Verkettung von N wurde so geändert, daß sie auf R zeigt, und die rechte Verkettung von I wurde so geändert, daß sie auf N zeigt. Man achte auch sorgfältig darauf, daß die Farben der zwei Knoten gewechselt haben.

Abbildung 15.11
Abbildung 15.11 Rotation eines 3-Knotens in Abbildung 15.8.

Diese Operation der einfachen Rotation (single rotation) ist für jeden binären Suchbaum definiert (wenn wir von Operationen absehen, die die Farben betreffen). Sie bildet die Grundlage für verschiedene Algorithmen auf ausgeglichenen Bäumen, da sie den wesentlichen Charakter des Suchbaums unverändert läßt und eine lokale Modifikation ist, die nur drei Änderungen von Verkettungen erfordert. Es ist jedoch wichtig anzumerken, daß die Ausführung einer einfachen Rotation nicht unbedingt die Ausgeglichenheit des Baums verbessert. In Abbildung 15.11 bringt die Rotation alle Knoten links von N einen Schritt näher zur Wurzel, doch alle Knoten rechts von R werden um einen Schritt nach unten verschoben; in diesem Falle bewirkt die Rotation, daß der Baum weniger statt mehr ausgeglichen ist. Top-Down 2-3-4-Bäume können einfach als eine zweckmäßige Methode zur Identifizierung von einfachen Rotationen betrachtet werden, von denen erwartet werden kann, daß sie die Ausgeglichenheit verbessern.

Die Ausführung einer einfachen Rotation bedeutet eine Veränderung der Struktur des Baumes, wobei mit großer Sorgfalt vorgegangen werden muß. Wie wir bei der Betrachtung des Algorithmus zum Löschen in Kapitel 14 gesehen haben, ist das Programm komplizierter, als es notwendig zu sein scheint, da es eine Anzahl ähnlicher Fälle mit Symmetrien bezüglich links und rechts gibt. Nehmen wir zum Beispiel an, daß in Abbildung 15.8 die Verkettungen y, c und gc auf I, R bzw. N zeigen. Dann wird die Transformation, die Abbildung 15.11 ergibt, mit Hilfe der Änderungen c.l:=gc^.r; gc^.r:=c; y^.r:=gc ausgeführt. Es gibt drei weitere analoge Fälle: Der 3-Knoten könnte anders orientiert sein, oder er könnte sich links von y befinden (so oder so orientiert). Eine zweckmäßige Methode zur Behandlung dieser vier verschiedenen Fälle besteht darin, den Suchschlüssel v zu verwenden, um den betreffenden Nachfolger (c) und Nachfolger des Nachfolgers (gc) des Knotens y »wiederzuentdecken«. (Wir wissen, daß wir einen 3-Knoten nur dann umorientieren, wenn die Suche uns bis zu seinem unteren Knoten geführt hat.) Dies ergibt ein etwas einfacheres Programm als die Alternative, sich während der Suche nicht nur die beiden c und gc entsprechenden Verkettungen zu merken, sondern auch, ob es sich um rechte oder linke Verkettungen handelt. Wir erhalten die folgende Funktion für das Umorientieren eines 3-Knotens mit Vorgänger y längs des Suchpfades für v:

    function rotate(v: integer; y: link): link;
      var c,gc: link;
      begin
      if v<y^.key then c:=y^.l else c:=y^.r;
      if v<c^.key
        then begin gc:=c^.l; c^.l:=gc^.r; gc^.r:=c end
        else begin gc:=c^.r; c^.r:=gc^.l; gc^.l:=c end;
      if v<y^.key then y^.l:=gc else y^.r:=gc;
      rotate:=gc
      end;

Falls y auf die Wurzel zeigt, c die rechte Verkettung von y und gc die linke Verkettung von c ist, ergibt dies genau die Transformationen der Verkettungen, die notwendig sind, um aus Abbildung 15.8 den Baum in Abbildung 15.11 zu erzeugen. Der Leser kann die anderen Fälle leicht nachprüfen. Diese Funktion gibt die Verkettung zurück, die zum oberen Teil des 3-Knotens zeigt, realisiert jedoch nicht die Änderung der Farbe selbst.

Folglich können wir, um den dritten Fall für split zu behandeln (siehe Abbildung 15.10), g rot färben, danach x gleich rotate (v, gg) setzen und dann x schwarz färben. Dadurch wird der 3-Knoten umorientiert, der aus den zwei Knoten besteht, auf die g und p zeigen, und dieser Fall wird damit auf den zweiten Fall zurückgeführt, wo der 3-Knoten die richtige Orientierung besaß.

Um schließlich den Fall zu behandeln, daß die beiden roten Verkettungen verschieden orientiert sind (siehe Abbildung 15.10), setzen wir einfach p gleich rotate (v, g). Dadurch wird der »unzulässige« 3-Knoten umorientiert, der aus den zwei Knoten besteht, auf die p und x zeigen. Diese Knoten haben die gleiche Farbe, so daß keine Farbänderung notwendig ist, und dieser Fall ist damit unmittelbar auf den dritten Fall zurückgeführt. Die Kombination dieses Vorgehens mit der Rotation für den dritten Fall wird aus offensichtlichen Gründen eine Doppelrotation genannt.

Abbildung 15.12 zeigt das Aufspalten (split), das in unserem Beispiel auftritt, wenn G hinzugefügt wird. Zuerst erfolgt eine Farbänderung, um den 4-Knoten aufzuspalten, der H, I und N enthält. Danach ist eine Doppelrotation erforderlich: der erste Teil um die Kante zwischen I und R und der zweite Teil um die Kante zwischen E und I. Nach diesen Modifikationen kann G links von H eingefügt werden, wie im ersten Baum in Abbildung 15.13 dargestellt ist.

Abbildung 15.12
Abbildung 15.12 Aufspalten eines Knotens in einem Rot-Schwarz-Baum.

Abbildung 15.13
Abbildung 15.13 Konstruktion eines Rot-Schwarz-Baumes.

Damit sind die Operationen, die von der Funktion split ausgeführt werden müssen, vollständig beschrieben. Sie muß die Farbe von x und von dessen Nachfolgern ändern, danach, falls erforderlich, den unteren Teil einer Doppelrotation ausführen und dann, falls erforderlich, die einfache Rotation ausführen:

    function split(v: integer; gg,g,p,x: link): link;
      begin
      x^.red:=true; x^.l^.red:=false; x^.r^.red:=false;
      if p^.red then
        begin
        g^.red:=true;
        if (v<g^.key)<>(v<p^.key) then p:=rotate(v,g);
        x:=rotate(v,gg);
        x^.red:=false
        end;
      head^.r^.red:=false;
      split:=x
      end;

Diese Prozedur legt die Farben nach einer Rotation fest und startet auch x genügend weit oben im Baum neu, um abzusichern, daß die Suche nicht infolge all der Änderungen von Verkettungen in die Irre führt. Die lange Argumentenliste wurde der Klarheit wegen verwendet; richtiger wäre es, diese Prozedur lokal zu der Funktion rbtreeinsert zu deklarieren, damit sie Zugriff auf deren Variablen hat.

Falls die Wurzel ein 4-Knoten ist, färbt die Prozedur split die Wurzel rot; dies entspricht ihrer Umwandlung, zusammen mit dem Pseudoknoten über ihr, in einen 3-Knoten. Es gibt natürlich keinen Grund, dies zu tun, weshalb am Ende von split eine Anweisung steht, die bewirkt, daß die Wurzel schwarz bleibt. Zu Beginn des Prozesses ist es erforderlich, die Pseudoknoten sorgfältig zu initialisieren:

    type link=^node;
         node=record key,info: integer; l,r: link; red: boolean end;
    var head,z: link;
    procedure rbtreeinitialize;
      begin
      new(z); z^.l:z; z^.r:=z; z^.red:=false;
      new(head); head^.key:=0; head^.r:=z;
      end;

Wenn man die obenstehenden Programmabschnitte zusammenfügt, ergibt sich ein sehr effizienter und relativ einfacher Algorithmus für das Einfügen bei Verwendung einer binären Baumstruktur, der für alle Operationen des Suchens und Einfügens garantiert eine logarithmische Anzahl von Schritten benötigt. Dies ist einer der wenigen Suchalgorithmen mit dieser Eigenschaft, und seine Anwendung ist immer dann gerechtfertigt, wenn ein schlechtes Verhalten im ungünstigsten Fall einfach nicht zugelassen werden kann.

Abbildung 15.13 zeigt, wie dieser Algorithmus den Rot-Schwarz-Baum für unser Beispiel einer Schlüsselmenge aufbaut. Hierbei erhalten wir als Ergebnis nur weniger Rotationen einen Baum, der weit ausgeglichener ist als der Baum für die gleichen Schlüssel, der in Kapitel 14 aufgebaut wurde.

Eigenschaft 15.3 Eine Suche in einem Rot-Schwarz-Baum mit N Knoten, der aus zufälligen Schlüsseln aufgebaut wurde, scheint ungefähr lg N Vergleiche zu erfordern, und ein Einfügen scheint im Durchschnitt weniger als eine Rotation zu erfordern.

Eine exakte Analyse des durchschnittlichen Falles steht für diesen Algorithmus noch aus, doch es liegen überzeugende Ergebnisse von Teilanalysen und Simulationen vor. Abbildung 15.14 zeigt einen Baum, der für das bereits betrachtete umfangreichere Beispiel aufgebaut wurde. Die durchschnittliche Anzahl der Knoten, die während der Suche nach einem zufälligen Schlüssel in diesem Baum besucht werden, beträgt nur 5,81, im Vergleich zu 7,00 für den Baum, der aus den gleichen Schlüsseln in Kapitel 14 aufgebaut wurde, und zu 5,74, dem besten möglichen Wert für einen vollständig ausgeglichenen Baum. w.z.b.w.

Abbildung 15.14
Abbildung 15.14 Ein umfangreicher Rot-Schwarz-Baum.

Doch die eigentliche Bedeutung von Rot-Schwarz-Bäumen liegt in ihrem Verhalten im ungünstigsten Fall sowie in der Tatsache, daß diese Leistungsfähigkeit mit sehr geringem Aufwand erreicht werden kann. Abbildung 15.15 zeigt den erzeugten Baum, wenn die Zahlen 1 bis 95 der Reihe nach in einen ursprünglich leeren Baum eingefügt werden; sogar dieser Baum ist gut ausgeglichen. Die Kosten der Suche pro Knoten sind genau so niedrig, als wenn der ausgeglichene Baum mit Hilfe des elementaren Algorithmus konstruiert worden wäre, und das Einfügen erfordert nur einen zusätzlichen Bit-Test und ein gelegentliches Aufspalten.

Abbildung 15.15
Abbildung 15.15 Ein Rot-Schwarz-Baum für einen entarteten Fall.

Eigenschaft 15.4 Eine Suche in einem Rot-Schwarz-Baum mit N Knoten erfordert weniger als 2 lg N + 2 Vergleiche, und die Zahl der Einfügungen liegt unter einem Viertel der Zahl der Vergleiche.

Nur »Aufspaltungen«, die einem mit einem 4-Knoten verbundenen 3-Knoten in einem 2-3-4-Baum entsprechen, erfordern in dem entsprechenden Rot-Schwarz-Baum eine Rotation, so daß diese Eigenschaft aus Eigenschaft 15.2 folgt. Der ungünstigste Fall liegt vor, wenn der Pfad zum Ort des Einfügens aus sich abwechselnden 3- und 4-Knoten besteht. w.z.b.w.

Kurz gesagt: Bei Anwendung dieses Verfahrens kann ein Schlüssel in einer Datei mit beispielsweise einer halben Million Datensätze gefunden werden, indem er mit nur ungefähr zwanzig anderen Schlüsseln verglichen wird. In einem ungünstigen Fall könnten vielleicht doppelt so viele Vergleiche notwendig sein, aber auch nicht mehr. Außerdem ist jeder Vergleich mit sehr wenig zusätzlichem Aufwand verbunden, so daß eine sehr schnelle Suche gewährleistet ist.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]