|
. 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 Aufspalten.
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 Element zusammengezogen und bildet mit diesem einen 3-Knoten, ein Element wird nach oben geschoben, wobei die hier angeführten 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.
Aufspalten von Wurzelknoten:
1. I als mittlerer Wert bleibt als Wurzel in einem 2-Knoten bestehen.
2. E & R werden eine Ebene tiefer als zwei seperate 2-Knoten eingefügt.
Einfügen von D:
1. Suche von Pos. Erg. rechts von C.
2. Da C in 4-Knoten, Aufspaltung von EIR.
3. Erneute Suche von Pos. zw. CE
4. Einfügen des neuen 2-Knoten.
Der oben skizzierte Algorithmus zeigt, 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, daß 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 nach sich 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 gegen 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.
|
