2-3-4-Baum

Der 2-3-4-Baum beschreibt in der Informatik einen B-Baum der Ordnung 4 und damit einen speziellen Balancierten Baum.

Der 2-3-4-Baum ist deshalb ein Baum, in dem jeder Knoten 2, 3 oder maximal 4 Kindknoten besitzt und entsprechend 1,2 oder maximal 3 Datenelemente speichert, die nach dem gewählten Ordnungskriterium aufsteigend sortiert sind.

Wie alle B-Bäume wird auch der 2-3-4-Baum häufig zur Speicherung großer Datenmengen verwendet , da das Suchen in diesen Bäumen mit dem Aufwand O(log n) möglich ist. Durch geschicktes Einfügen wird der 2-3-4-Baum stets balanciert gehalten. Man betrachte dazu das Beispiel.

Suchen

Um in einem B-Baum und damit auch in einem 2-3-4-Baum zu suchen, wird ein einfacher Algorithmus angewendet. Beginnend beim kleinsten (linkesten) Element des Wurzelknotens:

• 1. Vergleiche, ob der gesuchte Schlüssel gleich dem aktiven Element ist.
• • 1. Wenn ja, Suche beendet.
  • 2. Wenn nein, gehe zu 2.
• 2. Vergleiche , ob der gesuchte Schlüssel kleiner ist als das aktive Elemente im aktiven Knoten.
• • 1. Wenn ja, verzweige zum Kindknoten, der links vom gerade überprüften Element angehängt ist, setze dessen kleinstes Element als aktives Elements und gehe zu 1. zurück.
  • 2. Wenn nein, markiere das nächstgrößere Element im aktiven Knoten als aktives Element und gehe zu 1. zurück. Gibt es kein größeres Element mehr im aktiven Knoten, verzweige zum Kindknoten rechts des aktiven Element und setzes dessen kleinstes Element als aktives Element und gehe zurück zu 1.

Einfügen

• Ein Knoten wird mit Elementen aufgefüllt, bis er 3 Elemente enthält (vgl. B im Beispiel)
• Wenn ein viertes Element aufgenommen werden soll, wird der Knoten gespalten in einen Knoten mit zwei Elementen (J K im Beispiel), einen Knoten mit einem Element (M im Beispiel) und ein mittleres Element (L im Beispiel), das in den Elternknoten aufgenommen wird. (vgl. Schritt 2 im Beispiel).
• Ist der Elternknoten voll besetzt, wird das Element im Baum weiter nach oben gereicht. Erreicht das Element die Wurzel des Baumes und ist dieser schon mit 3 Elementen besetzt, wird eine neue Wurzel nach gleicher Aufteilungsregel erzeugt. (vgl. Schritt 4 des Beispiels).

Varianten

Eine Implementierung von 2-3-4-Bäumen sind RB-Bäume.