Ausgeglichene Bäume

bei binären Bäumen tritt ungünstigster Fall relativ häufig ein. (geordnete Dateien, umgekehrter Reihenfolge, abwecheselnd großer, kleiner Schlüssel, usw.)

Ausgleichen verhindert das Eintreten des ungünstigsten Falls.

Ausgleichen dient als Grundlage für ausgeglichene Bäume.

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

mehr Flexibilität gegenüber herkömmlichen binären Suchbäumen durch 3-Knoten und 4-Knoten.

2-Knoten enthalten 1 Schlüssel

3-Knoten enthalten 2 Schlüssel

4-Knoten enthalten 3 Schlüssel

Suchen, Einfügen und Aufspaleten.

Suche nach G:

mittlere Verzweigung, da G zw. E und R

links, da G nicht vorhanden und Suche von links beginnt.

Einfügen von G:

Zuerst erfolglose Suche durchführen, dann G anhängen.

drei Möglichkeiten:

2-Knoten: G wird angehängt. aus 2 wird 3.

3-Knoten: G wird ebenfalls angehängt. aus 3 wird 4.

4-Knoten: G wird mit dem ihm am nächsten Elemten zusammengezogen und bildet mit diesem einen 3-Knoten, ein Elemtent wird nach oben geschoben, wobei die hier angeführeten Regel zu berücksichtigen sind. Aus dem vierten Element wird ein 2-Knoten gebildet.

Aufspaltung eines 4-Knotens, wenn Vorgänger ebenfalls 4-Knoten:

Es besteht die Möglichkeit beim Einfügen eines neuen Knotens, den ganzen Baum (wenn notwendig) nach oben hin aufzuspalten. Nur wenn in der Wurzel ein 4-Knoten steht und dieser aufgespalten werden muß, wird der Baum um eine Stufe tiefer.

Auspalten von Wurzelknoten:

I als mittlerer Wert bleibt als Wurzel in einem 2-Knoten bestehen.

E & R werden eine Ebene tiefer als zwei seperate 2-Knoten eingefügt.

Einfügen von D:

Suche von Pos. Erg. rechts von C.

Da C in 4-Knoten aufspaltung von EIR.

Erneute Suche von Pos. zw. CE

Einfügen des neuen 2-Knoten.

Der oben skizzierte Algorithmus 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 aufgespalten werden, werden diese Bäume TOP-DOWN 2-3-4 Bäume genannt. Interessant ist hier, das diese Bäume vollkommen ausgeglichen sind, obwohl wir keinerlei Vorkehrungen dafür getroffen haben.

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

Die Entfernung zur Wurzel ist immer gleich. Der Abstand ändert sich nur, wenn wir die Wurzel aufspalten, dann allerdings generell um eins.

(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 in einem 2-3-4 Baum ist, wenn auf dem gesammten Weg von oben nach unten 4-Knoten vorhanden sind. Dies ist allerdings äußerst unwahrscheinich. 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.

Den oben Beschriebenen Algorithmus könnte man schon jetzt implementieren, aber er würde einen ziemlichen Wulst an Routinen nachsich ziehen. Bei komplexeren Baumstrukturen würde der 2-3-4-Baum langsamer werden als ein simpler binärer Suchbaum. Der Hauptzweck eines 2-3-4-Baumes ist die Versicherung gegeben den ungünstigsten Fall. Es sollte allerdings nicht so sein, daß bei jedem Durchlauf dies auf Kosten der Geschwindigkeit geht. Darum wurden die Rot-Schwarz-Bäume entwickelt.

Rot-Schwarz-Bäume

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 Impementierung 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, wenn der 4-Knoten siche 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 doppelte 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ähigkeitmit 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.

Kurzgesagt:

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.

Andere Algorithmen

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. Dieser Algorithmus hat den Nachteil, daß erstens eine zusätzliche Schleife für die Rotation benötigt wird, und daß für jeden Knoten auch noch die Länge seiner jeweiligen Unterbäume gespeichert werden muß.

Eine zweite ausgeglichene Baumstruktur ist der 2-3-Baum, bei dem nur 2-Knoten und 3-Knoten zugelassen sind. Es ist möglich, ein Einfügen 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 ist es möglich eine Vereinfachung unter Zuhilfenahme des Rot-Schwarz-Schemas erreicht werden kann.

Es gibt auch noch einen anderen wichtigen 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, und ssie werden häufig für Suchanwendungen, bei denen sehr große Dateien auftreten, verwendet.