Robert Sedgewick: Algorithmen

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


15. Ausgeglichene Bäume



Andere Algorithmen

Die im vorangegangenen Abschnitt angegebene Implementation des »Top-Down 2-3-4-Baums« mit Verwendung des Rot-Schwarz-Schemas ist eine von mehreren ähnlichen Strategien, die für die Implementation von ausgeglichenen binären Bäumen vorgeschlagen worden sind. Wie wir oben gesehen haben, sind es in Wirklichkeit die »Rotations«-Operationen, die das Ausgleichen der Bäume bewirken; wir haben eine spezielle Betrachtungsweise des Baums untersucht, die es leicht macht zu entscheiden, wann eine Rotation notwendig ist. Andere Betrachtungsweisen der Bäume führen zu anderen Algorithmen, von denen wir hier einige kurz erwähnen wollen.

Die älteste und bekannteste Datenstruktur für ausgeglichene Bäume ist der AVL-Baum. Diese Bäume haben die Eigenschaft, daß sich die Höhen der beiden Unterbäume jedes Knotens höchstens um eins unterscheiden. Falls diese Bedingung infolge einer Einfügung verletzt wird, so zeigt es sich, daß sie unter Verwendung von Rotationen wiederhergestellt werden kann. Doch dies erfordert eine zusätzliche Schleife; der grundlegende Algorithmus besteht darin, nach dem eingefügten Wert zu suchen und sich danach im Baum längs des soeben benutzten Pfades nach oben zu bewegen, wobei die Höhen der Knoten unter Verwendung von Rotationen korrigiert werden. Außerdem ist es erforderlich, für jeden Knoten zu wissen, ob seine Höhe um eins kleiner, gleich oder um eins größer ist als die Höhe seines »Geschwisters«. Dies erfordert bei Programmierung auf direktem Wege zwei Bits, obwohl es einen Weg gibt, wie man unter Benutzung des Rot-Schwarz-Schemas mit nur einem Bit pro Knoten auskommen kann.

Eine zweite bekannte ausgeglichene Baumstruktur ist der 2-3-Baum, bei dem nur 2-Knoten und 3-Knoten zugelassen sind. Es ist möglich, ein Einfügen (insert) unter Verwendung einer »zusätzlichen Schleife« zu implementieren, wobei Rotationen wie bei AVL-Bäumen erforderlich sind, doch es ist nicht genügend viel Flexibilität vorhanden, um eine zweckmäßige Top-Down-Variante zu erhalten. Auch hier kann die Implementation mit Hilfe des Rot-Schwarz-Schemas vereinfacht werden, doch in Wirklichkeit ist es besser, Bottom-Up 2-3-4-Bäume zu verwenden, bei denen wir bis zur untersten Ebene des Baumes suchen, dort einfügen und uns danach (wenn der Knoten unten ein 4-Knoten war) längs des Suchpfades zurück nach oben bewegen, wobei wir 4-Knoten aufspalten und den mittleren Knoten in den Vorgänger einfügen, so lange, bis wir einen 2-Knoten oder 3-Knoten als Vorgänger vorfinden, wobei an dieser Stelle eine Rotation erforderlich sein könnte, um Fälle wie in Abbildung 15.10 zu behandeln. Diese Methode hat den Vorteil, daß höchstens eine Rotation pro Einfügung benötigt wird, was in manchen Anwendungen von Vorteil sein kann. Die Implementation ist ein wenig komplizierter als für die oben angegebene Top-Down-Methode.

In Kapitel 18 untersuchen wir den wichtigsten Typ eines ausgeglichenen Baumes, eine Verallgemeinerung der 2-3-4-Bäume, die B-Bäume genannt werden. Diese gestatten bis zu M Schlüssel pro Knoten für großes M, und sie werden häufig für Suchanwendungen, bei denen sehr große Dateien auftreten, verwendet.


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