2-3-4-Baum

Aufbau und Bedeutung

Ein 2-3-4-Baum, auch (2,4)-Baum, ist eine Datenstruktur der Informatik. Er ist ein B-Baum mit minimalem Verzweigungsgrad 2 und zugleich ein spezieller balancierter Suchbaum.

Jeder Knoten hat zwei, drei oder höchstens vier Kinder. Entsprechend speichert er ein, zwei oder höchstens drei Datenelemente. Diese Elemente sind nach dem gewählten Ordnungskriterium aufsteigend sortiert. 2-3-4-Bäume dienen häufig zur Speicherung großer Datenmengen. Das Suchen benötigt O(log n) Zeit; durch geeignetes Einfügen bleibt der Baum balanciert.

Suchen nach einem Schlüssel

Die Suche beginnt beim kleinsten, also linkesten, Element des Wurzelknotens. Der gesuchte Schlüssel wird mit dem gerade aktiven Element verglichen.

Ist er gleich, ist die Suche beendet. Ist er kleiner, folgt man dem Kindknoten links von diesem Element und setzt dort das kleinste Element als aktiv. Ist er größer, wird das nächstgrößere Element desselben Knotens geprüft. Gibt es kein größeres Element mehr, folgt man dem Kindknoten rechts des aktiven Elements. Dieser Vorgang wird wiederholt.

Einfügen und Aufspalten

Ein Knoten wird zunächst aufgefüllt, bis er drei Elemente enthält. Soll ein viertes Element aufgenommen werden, wird der Knoten gespalten (Split): Das mittlere Element wird in den Elterknoten übernommen; die übrigen Elemente bilden die entstehenden Knoten.

Ist auch der Elterknoten voll, wird das Element weiter nach oben gereicht. Ist die Wurzel bereits mit drei Elementen besetzt, entsteht nach derselben Aufteilungsregel eine neue Wurzel.

Bei einer weiteren Einfügemethode wird beim Durchlaufen des Baums jeder gefundene 4-Knoten sofort gespalten und sein mittleres Element nach oben gereicht. Dabei wird die Split-Operation im schlimmsten Fall gerade einmal durchgeführt; bei der zuerst beschriebenen Methode können im schlimmsten Fall log(n) Split-Operationen nötig sein.

Löschen

Das Löschen eines Elements wird auf das Löschen eines Elements in einem Blatt zurückgeführt. Liegt das Element an Position i eines Knotens, wird im Unterbaum i das am weitesten rechts liegende Blatt gesucht. Dessen größtes Element wird mit dem zu löschenden Element vertauscht. Danach wird das Element im Blatt entfernt.

Hat das Blatt mehr als ein Element, wird es einfach entfernt. Hat es nur ein Element, kann bei einem Geschwisterknoten mit mindestens zwei Elementen eines ausgeliehen werden. Haben bei wenigstens drei Geschwistern alle nur ein Element, werden zwei Geschwister verschmolzen (Fuse). Gibt es nur einen Geschwisterknoten, der ebenfalls nur ein Element hat, wird die Operation rekursiv auf höherer Ebene fortgesetzt.

Beispiel und Variante

Beim Einfügen von 25 beginnt man in der Wurzel (10, 20). Da 25 größer als 20 ist, geht man zum rechten Kindknoten (22, 24, 29). Weil dieser ein viertes Element aufnehmen müsste, wird er gespalten: 24 wird in den Elterknoten verschoben, und aus (22, 29) entstehen die Knoten (22) und (29).

25 ist größer als 24 in der Wurzel und kleiner als 29 im Kindknoten. Da (29) keinen linken Kindknoten hat, wird 25 diesem Knoten hinzugefügt. 2-3-4-Bäume werden beispielsweise durch Rot-Schwarz-Bäume implementiert.