Robert Sedgewick: Algorithmen

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


15. Ausgeglichene Bäume



Top-Down 2-3-4-Bäume

Um bei binären Suchbäumen den ungünstigsten Fall auszuschließen, benötigen wir eine gewisse Flexibilität in den verwendeten Datenstrukturen. Um diese Flexibilität zu erreichen, wollen wir annehmen, daß die Knoten in unseren Bäumen mehr als einen Schlüssel enthalten können. Insbesondere lassen wir 3-Knoten und 4-Knoten zu, welche zwei bzw. drei Schlüssel enthalten können. Ein 3-Knoten besitzt drei von ihm ausgehende Verkettungen: eine für alle Datensätze mit Schlüsseln, die kleiner sind als seine beiden Schlüssel, eine für alle Datensätze, die zwischen seinen beiden Schlüsseln liegen, und eine für alle Datensätze mit Schlüsseln, die größer sind als seine beiden Schlüssel. Analog besitzt ein 4-Knoten vier von ihm ausgehende Verkettungen, nämlich eine für jedes der Intervalle, die durch seine drei Schlüssel definiert werden. (Die Knoten in einem gewöhnlichen binären Suchbaum könnten demnach 2-Knoten genannt werden: ein Schlüssel, zwei Verkettungen.) Später lernen wir einige effiziente Methoden zur Definition und Implementation grundlegenden Operationen auf diesen erweiterten Knoten kennen; einstweilen wollen wir annehmen, daß wir in geeigneter Weise mit ihnen operieren können, und sehen, wie sie zu Bäumen zusammengesetzt werden können.

Abbildung 15.1 zeigt als Beispiel einen 2-3-4-Baum, der die Schlüssel A S E A R C H I N enthält. Es ist leicht zu sehen, wie in einem solchen Baum gesucht werden muß. Um zum Beispiel in dem Baum in Abbildung 15.1 ein G zu suchen, würden wir von der Wurzel aus der mittleren Verkettung folgen, da G zwischen E und R liegt, und würden dann die erfolglose Suche bei der linken Verkettung beenden, die von dem H, I und N enthaltenden Knoten ausgeht.

Abbildung 15.1
Abbildung 15.1 Ein 2-3-4-Baum.

Um einen neuen Knoten in einen 2-3-4-Baum einzufügen, würden wir wie zuvor eine erfolglose Suche durchführen und dann den Knoten anhängen. Es ist leicht zu sehen, was zu tun ist, wenn der Knoten, bei dem die Suche abbricht, ein 2-Knoten ist: Er wird einfach in einen 3-Knoten verwandelt. Zum Beispiel könnte ein X zu dem Baum in Abbildung 15.1 hinzugefügt werden, indem es (zusammen mit einer weiteren Verkettung) dem Knoten zugefügt wird, der S enthält. In ähnlicher Weise kann ein 3-Knoten leicht in einen 4-Knoten verwandelt werden. Doch was sollen wir tun, wenn wir einen neuen Knoten in einen 4-Knoten einfügen müssen? Wie soll das zum Beispiel realisiert werden, wenn wir in den Baum in Abbildung 15.1 ein G einfügen? Eine Möglichkeit wäre, es als neuen, ganz links befindlichen Nachfolger des 4-Knotens anzuhängen, der H, I und N enthält, doch Abbildung 15.2 zeigt eine bessere Lösung: Spalte zuerst den 4-Knoten in zwei 2-Knoten auf und übergebe einen seiner Schlüssel nach oben an seinen Vorgänger. Zuerst wird der 4-Knoten, der H, I und N enthält, in zwei 2-Knoten aufgespalten (wobei der eine H und der andere N enthält), und der »mittlere Schlüssel« I wird nach oben an den 3-Knoten übergeben, der E und R enthält, wodurch dieser in einen 4-Knoten verwandelt wird. Danach ist in dem 2-Knoten, der H enthält, Platz für ein G.

Abbildung 15.2
Abbildung 15.2 Einfügen (von G) in einen 2-3-4-Baum.

Doch wie ist vorzugehen, wenn wir einen 4-Knoten spalten müssen, dessen Vorgänger gleichfalls ein 4-Knoten ist? Eine Möglichkeit wäre, den Vorgänger ebenfalls zu spalten, doch es könnte der Fall eintreten, daß wir das dann entlang des gesamten Weges im Baum nach oben tun müssen. Ein einfacher Weg ist, auf dem Weg im Baum nach unten jeden angetroffenen 4-Knoten aufzuspalten und dadurch zu gewährleisten, daß kein angetroffener Knoten mehr einen 4-Knoten als Vorgänger hat. Abbildung 15.3 zeigt die Vollendung der Konstruktion eines 2-3-4-Baumes für unsere vollständige Schlüsselmenge A S E A R C H I N G E X A M P L E. In der obersten Reihe sehen wir, daß der Wurzelknoten während des Einfügens des zweiten E aufgespalten wird; weitere Aufspaltungen erfolgen, wenn das zweite A, das L und das dritte E eingefügt werden.

Abbildung 15.3
Abbildung 15.3 Konstruktion eines 2-3-4-Baumes.

Das obige Beispiel zeigt, daß wir neue Knoten leicht in 2-3-4-Bäume einfügen können, indem wir eine Suche durchführen und 4-Knoten auf dem Weg im Baum abwärts aufspalten. Insbesondere sollten wir jedesmal, wenn wir einen 2-Knoten vorfinden, der mit einem 4-Knoten verbunden ist, diesen in einen 3-Knoten umwandeln, der mit zwei 2-Knoten verbunden ist, und jedesmal, wenn wir einen 3-Knoten antreffen, der mit einem 4-Knoten verbunden ist, diesen in einen 4-Knoten umwandeln, der mit zwei 2-Knoten verbunden ist, wie es Abbildung 15.4 zeigt.

Abbildung 15.4
Abbildung 15.4 Aufspalten von 4-Knoten.

Diese Operation des »Aufspaltens« ist aufgrund der Art und Weise möglich, wie nicht nur die Schlüssel, sondern auch die Zeiger bewegt werden können. Zwei 2-Knoten haben die gleiche Anzahl von Zeigern (vier) wie ein 4-Knoten, so daß das Aufspalten ausgeführt werden kann, ohne unterhalb des aufgespaltenen Knotens irgend etwas zu verändern. Und ein 3-Knoten kann nicht einfach in einen 4-Knoten verwandelt werden, indem nur ein weiterer Schlüssel hinzugefügt wird; ein weiterer Zeiger wird gleichfalls benötigt (in diesem Falle der zusätzliche Zeiger, der durch das Aufspalten entsteht). Die entscheidende Tatsache besteht darin, daß diese Transformationen rein »lokal« sind: Kein Teil des Baumes außer dem in Abbildung 15.4 gezeigten muß untersucht oder verändert werden. Bei jeder der Transformationen wird einer der Schlüssel aus einem 4-Knoten nach oben an dessen Vorgänger im Baum übergeben, und die Verkettungen werden entsprechend umstrukturiert. Beachten Sie, daß wir uns nicht darum kümmern müssen, ob der Vorgänger ein 4-Knoten ist. Unsere Transformationen sorgen dafür, daß wir - nachdem wir jeden Knoten im Baum durchlaufen haben - an einen Knoten gelangen, der kein 4-Knoten ist. Insbesondere dann, wenn wir die unterste Ebene des Baumes erreichen, befinden wir uns nicht bei einem 4-Knoten, und wir können den neuen Knoten unmittelbar einfügen, indem wir entweder einen 2-Knoten in einen 3-Knoten oder einen 3-Knoten in einen 4-Knoten verwandeln. In Wirklichkeit ist es zweckmäßig, das Einfügen als ein Aufspalten eines imaginären 4-Knotens in der untersten Ebene zu behandeln, welcher den einzufügenden neuen Knoten nach oben übergibt. Jedesmal, wenn die Wurzel des Baumes zu einem 4-Knoten wird, spalten wir sie in drei 2-Knoten auf, wie wir es bei unserem ersten aufgespaltenen Knoten im obigen Beispiel getan haben. Das (und nur das) bewirkt, daß der Baum um eine Ebene »höher« wird.

Der oben skizzierte Algorithmus gibt einen Weg an, wie Suchvorgänge und Einfügungen in 2-3-4-Bäumen ausgeführt werden können; da die 4-Knoten auf dem Weg von oben nach unten (top down) aufgespalten werden, werden die Bäume Top-Down 2-3-4-Bäume genannt. Das Interessante hierbei ist, daß, obwohl wir uns über das Ausgleichen überhaupt keine Gedanken gemacht haben, die entstehenden Bäume vollkommen ausgeglichen sind!

Eigenschaft 15.1 Beim Suchen in 2-3-4-Bäumen mit N Knoten werden niemals mehr als lg N + 1 Knoten besucht.

Die Entfernung von der Wurzel zu jedem äußeren Knoten ist die gleiche; die Transformationen, die wir ausführen, haben keinen Einfluß auf die Entfernung irgendeines Knotens zur Wurzel, außer wenn wir die Wurzel aufspalten, und in diesem Falle erhöht sich die Entfernung von allen Knoten zur Wurzel um eins. Falls alle Knoten 2-Knoten sind, gilt die Behauptung, da der Baum einem vollen binären Baum gleicht; falls 3-Knoten und 4-Knoten vorhanden sind, kann die Höhe nur kleiner sein. w.z.b.w.

Eigenschaft 15.2 Einfügungen in 2-3-4-Bäume mit N Knoten erfordern im ungünstigsten Fall weniger als lg N + 1 Aufspaltungen von Knoten und scheinen im Durchschnitt weniger als eine Aufspaltung eines Knotens zu erfordern.

Der ungünstigste Fall, der eintreten könnte, wäre, daß alle Knoten auf dem Pfad zum Ort des Einfügens 4-Knoten sind, die alle aufgespalten würden. Doch in einem Baum, der aus einer zufälligen Permutation von N Elementen aufgebaut wird, ist nicht nur die Wahrscheinlichkeit des Eintretens dieses ungünstigsten Falls gering, sondern es scheinen auch im Durchschnitt wenige Aufspaltungen erforderlich zu sein, da es nicht viele 4-Knoten gibt. Abbildung 15.5 zeigt einen Baum, der aus einer zufälligen Permutation von 95 Elementen aufgebaut wurde; es gibt neun 4-Knoten, von denen sich nur einer nicht auf der untersten Ebene befindet. Analytische Ergebnisse hinsichtlich des durchschnittlichen Verhaltens von 2-3-4-Bäumen konnten die Experten bisher noch nicht erzielen, doch empirische Untersuchungen zeigen übereinstimmend, daß sehr wenige Aufspaltungen durchgeführt werden. w.z.b.w.

Abbildung 15.5
Abbildung 15.5 Ein umfangreicher 2-3-4-Baum.

Die oben angegebene Beschreibung ist ausreichend, um einen Algorithmus für die Suche unter Verwendung von 2-3-4-Bäumen zu definieren, der im ungünstigsten Fall garantiert eine gute Leistungsfähigkeit besitzt. Jedoch befinden wir uns erst auf halbem Wege zu einer tatsächlichen Implementation. Während es möglich wäre, Algorithmen zu schreiben, die Transformationen für bestimmte Datentypen, die 2-, 3- und 4-Knoten darstellen, wirklich ausführen, sind die meisten zu realisierenden Dinge in dieser direkten Darstellung sehr schwer ausführbar. (Man kann sich hiervon überzeugen, indem man versucht, wenigstens die einfachere der beiden Knoten-Transformationen zu implementieren.) Hinzu kommt, daß der bei der Behandlung der komplexeren Knotenstrukturen entstehende Ballast wahrscheinlich dazu führen würde, daß die Algorithmen langsamer sind als die gewöhnliche Suche in einem Binärbaum. Der Hauptzweck des Ausgleichens besteht darin, eine »Versicherung« gegen einen schlechten ungünstigsten Fall zu schaffen, doch es wäre verhängnisvoll, wenn man bei jedem Durchlauf des Algorithmus die Gesamtkosten für diese Versicherung zahlen müßte. Wie wir noch sehen werden, gibt es zum Glück eine relativ einfache Möglichkeit der Darstellung von 2-, 3- und 4-Knoten, die es gestattet, die Transformationen in einer einheitlichen Weise durchzuführen, mit sehr geringem zusätzlichem Aufwand im Vergleich zu den Kosten, die bei der gewöhnlichen Suche in einem Binärbaum entstehen.


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