2-3-4-Baum

Stichpunkte

Allgemein
	genauer ein B-Baum der Ordnung 4
	das heißt
	3 oder maximal 4 Kinder besitzt und entsprechend 1
	die nach dem gewählten Ordnungskriterium aufsteigend sortiert sind
	er ist ein Baum
	in dem jeder Knoten 2
	Ein 2-3-4-Baum ist in der Informatik eine Datenstruktur
	2 oder maximal 3 Datenelemente speichert
	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
	wird ein einfacher Algorithmus angewendet
	Um in einem B-Baum und damit auch in einem 2-3-4-Baum zu suchen
	Suche beendet. Wenn nein
	ob der gesuchte Schlüssel kleiner ist als das aktive Elemente im aktiven Knoten
	ob der gesuchte Schlüssel gleich dem aktiven Element ist. Wenn ja
	gehe zu 2. Vergleiche
	Beginnend beim kleinsten (linkesten) Element des Wurzelknotens: Vergleiche
	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
	Wenn ja
	Wenn nein
	markiere das nächstgrößere Element im aktiven Knoten als aktives Element und gehe zu 1. zurück
	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
	bis er 3 Elemente enthält (vgl
	Ein Knoten wird mit Elementen aufgefüllt
	einen Knoten mit einem Element (M im Beispiel) und ein mittleres Element (L im Beispiel)
	B im Beispiel) Wenn ein viertes Element aufgenommen werden soll
	das in den Elternknoten aufgenommen wird. (vgl
	wird der Knoten gespalten in einen Knoten mit zwei Elementen (J K im Beispiel)
	wird das Element im Baum weiter nach oben gereicht
	Schritt 2 im Beispiel). Ist der Elternknoten voll besetzt
	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). [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.