Stichpunkte

Allgemein
	Ein 2-3-4-Baum ist in der Informatik eine Datenstruktur
	die nach dem gewählten Ordnungskriterium aufsteigend sortiert sind
	das heißt
	2 oder maximal 3 Datenelemente speichert
	genauer ein B-Baum der Ordnung 4
	er ist ein Baum
	3 oder maximal 4 Kinder besitzt und entsprechend 1
	in dem jeder Knoten 2
	Er stellt damit zugleich einen speziellen balancierten Suchbaum dar. Wie alle B-Bäume wird auch der 2-3-4-Baum häufig zur Speicherung großer Datenmengen verwendet
	Das Suchen in diesen Bäumen ist mit einer Laufzeit von O(log n) möglich
	Durch geschicktes Einfügen wird der 2-3-4-Baum stets balanciert gehalten
	Man betrachte dazu das Beispiel.Bild nicht gefunden Beispiel eines 2-3-4-Baum [Bearbeiten]
Suchen
	Um in einem B-Baum und damit auch in einem 2-3-4-Baum zu suchen
	wird ein einfacher Algorithmus angewendet
	ob der gesuchte Schlüssel gleich dem aktiven Element ist. Wenn ja
	ob der gesuchte Schlüssel kleiner ist als das aktive Elemente im aktiven Knoten
	Beginnend beim kleinsten (linkesten) Element des Wurzelknotens: Vergleiche
	gehe zu 2. Vergleiche
	Suche beendet. Wenn nein
	Wenn ja
	der links vom gerade überprüften Element angehängt ist
	verzweige zum Kindknoten
	setze dessen kleinstes Element als aktives Elements und gehe zu 1. zurück
	markiere das nächstgrößere Element im aktiven Knoten als aktives Element und gehe zu 1. zurück
	Wenn nein
	verzweige zum Kindknoten rechts des aktiven Element und setzes dessen kleinstes Element als aktives Element und gehe zurück zu 1. [Bearbeiten]
	Gibt es kein größeres Element mehr im aktiven Knoten
Einfügen
	Ein Knoten wird mit Elementen aufgefüllt
	bis er 3 Elemente enthält (vgl
	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
	B im Beispiel) Wenn ein viertes Element aufgenommen werden soll
	Schritt 2 im Beispiel). Ist der Elternknoten voll besetzt
	wird das Element im Baum weiter nach oben gereicht
	wird eine neue Wurzel nach gleicher Aufteilungsregel erzeugt. (vgl
	Erreicht das Element die Wurzel des Baumes und ist dieser schon mit 3 Elementen besetzt
	Schritt 4 des Beispiels). [Bearbeiten]
Varianten
	2-3-4-Bäume werden beispielsweise durch Rot-Schwarz-Bäume implementiert.

Dieser Artikel basiert auf dem Artikel 2-3-4-Baum aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.