|
. 2-3-4 Bäume können als gewöhnliche binäre Bäume dargestellt werden, wobei nur ein zusätzliches Bit pro Knoten verwendet wird.
. 3-Knoten und 4-Knoten werden als kleine binäre Bäume dargestellt, die durch eine "rote" Verkettung gekennzeichnet sind.
. Alle anderen Verbindungen sind "schwarz".
. Es dürfen niemals zwei rote Verkettungen hintereinander auftreten.
. 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, werden als Rot-Schwarz-Bäume bezeichnet.
. Der Unterschied in der Implementierung ist nur, daß wir ein zusätzliches bool´sche Feld namens "red" erstellen müssen.
. Dieses bool´sche Feld wird von der Funktion, die den Baum durchläuft, ignoriert. Dies bedeutet, daß für das Suchen keine Änderungen zum binären Baum notwendig sind.
. Beim Aufspalten in einem Rot-Schwarz-Baum gibt es dieselben Möglichkeiten wie in einem 2-3-4-Baum (aus 4-Knoten mache drei 2-Knoten).
. Es treten Probleme auf, wenn ein 3-Knoten mit einem 4-Knoten verbunden ist und der 4-Knoten sich in der Mitte oder Links befindet:
. Lösung: Rotation! Kann leicht veranschaulicht werden (durch 2-3-4-Bäume), wie vorgegangen werden muß
.
. Es gibt die einfache Rotation (single Rotation) und die doppelte Rotation. Bei der einfachen Rotation sind die beiden roten Verbindungen in einer Richtung, bei der doppelten sind sie in entgegengesetzter Richtung. (siehe oben)
. (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.)
. Die eigentliche Bedeutung von Rot-Schwarz-Bäumen liegt in ihrem Verhalten im ungünstigen Fall, sowie in der Tatsache, daß diese Leistungsfähigkeit mit sehr geringem Aufwand erreicht werden kann.
. (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.)
. Der ungünstigste Fall liegt vor, wenn der Pfad zum Ort des Einfügens aus sich abwechselnden 3- und 4-Knoten besteht.
kurz gesagt:
Bei Anwendung dieses Verfahrens kann ein Schlüssel in einer Datei, mit beispielsweise einer halben Million Datensätze, mit nur ungefähr zwanzig Vergleichen, mit anderen Schlüsseln gefunden werden.
|
