imported>일성김: ??? Die letzte Textänderung von 147.142.150.164 wurde verworfen und die Version 209522251 von Aka wiederhergestellt.

2023-06-23T14:53:59Z

??? Die letzte Textänderung von 147.142.150.164 wurde verworfen und die Version 209522251 von Aka wiederhergestellt.

Neue Seite

[[Datei:2-3-4 tree example.png|mini|2-3-4 Baum]]

Ein '''2-3-4-Baum''' (auch '''(2,4)-Baum''') ist in der [[Informatik]] eine [[Datenstruktur]], genauer ein [[B-Baum]] des minimalen Verzweigungsgrades ''2'', das heißt, er ist ein [[Baum (Graphentheorie)|Baum]], in dem jeder ''[[Knoten (Graphentheorie)|Knoten]]'' zwei, drei oder maximal vier ''Kinder'' besitzt und entsprechend ein, zwei oder maximal drei Datenelemente speichert, die nach dem gewählten Ordnungskriterium aufsteigend sortiert sind. Er stellt damit zugleich einen speziellen [[Balancierter Baum|balancierten]] [[Suchbaum]] dar.

[[Datei:234Baum.PNG|mini|Beispiel eines 2-3-4-Baums]]

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 [[Asymptotische Laufzeit|Laufzeit]] von [[Landau-Symbole|O(log n)]] möglich. Durch geschicktes Einfügen wird der 2-3-4-Baum stets balanciert gehalten.

== 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'':

# Vergleiche, ob der gesuchte Schlüssel gleich dem aktiven Element ist.
#* Wenn ja, Suche beendet.
#* Wenn nein, gehe zu 2.
# Vergleiche, ob der gesuchte Schlüssel kleiner ist als das aktive Element im ''aktiven Knoten''.
#* Wenn ja, verzweige zum Kindknoten, der links vom gerade überprüften Element angehängt ist, setze dessen kleinstes Element als aktives Element und gehe zu 1. zurück.
#* 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 setze dessen kleinstes Element als aktives Element und gehe zurück zu 1.

== Einfügen ==
* Ein Knoten wird mit Elementen aufgefüllt, bis er drei Elemente enthält (vgl. B im Beispiel).
* Wenn ein viertes Element aufgenommen werden soll, wird der Knoten gespalten (engl. ''split'') 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 ''[[Elterknoten]]'' aufgenommen wird (vgl. Schritt 2 im Beispiel).
* Ist der Elterknoten voll besetzt, wird das Element im Baum weiter nach oben gereicht. Erreicht das Element die Wurzel des Baumes und ist dieser schon mit drei Elementen besetzt, wird eine neue Wurzel nach gleicher Aufteilungsregel erzeugt (vgl. Schritt 4 des Beispiels).

Es gibt eine weitere Möglichkeit, neue Elemente einzufügen, die sich von obiger Methode darin unterscheidet, zu welchem Zeitpunkt ein ''4-Knoten'' aufgespalten wird.
Bei dieser Methode wird während des ''Traversierens'' des Baums jeder gefundene 4-Knoten aufgespalten, es wird also das mittlere Element nach oben gereicht. Die Split-Operation wird also im schlimmsten Fall gerade einmal durchgeführt, während die erstgenannte Methode im schlimmsten Fall log(n) Split-Operationen durchführen muss.

== Löschen ==
Das Löschen eines beliebigen Elements kann immer auf das Löschen eines Elements in einem ''Blatt'' zurückgeführt werden. Dazu merkt man sich die Position des Elements innerhalb des Knotens. Ist die Position ''i'', so wird im ''Unterbaum i'' des Knotens das Blatt gesucht, das sich am weitesten rechts befindet, dort vertauscht man das größte Element mit dem zu löschenden Element.
Nun braucht nur noch das Element aus dem Blatt gelöscht zu werden, wobei drei Fälle unterschieden werden müssen:
* Das Blatt besitzt mehr als ein Element. In diesem Fall kann das Element einfach entfernt werden.
* Das Blatt enthält nur ein Element. In einem ''Geschwisterknoten'' (Knoten mit gleichem ''Elter'') gibt es aber mindestens zwei Elemente. Es kann ein Element beim Geschwisterknoten ''ausgeliehen'' (''gestohlen'' in [[#Mehlhorn1|Mehlhorn 1998]]) werden.
* Das Blatt hat nur ein Element. Es sind wenigstens drei Geschwister beim gleichen Elter (zwei Elemente). Alle haben nur ein Element. Zwei Geschwister werden verschmolzen (engl. ''fuse'').
* Das Blatt hat nur ein Element. Es gibt nur einen Geschwisterknoten, der auch nur ein Element hat. Die Operation wird rekursiv auf höherer Ebene fortgesetzt.

== Varianten ==
2-3-4-Bäume werden beispielsweise durch [[Rot-Schwarz-Baum|Rot-Schwarz-Bäume]] implementiert.

== Literatur ==
* D. Maier, S. C. Salveter: ''Hysterical B-trees''. In: ''Information Processing Letters 12'', 1981, S. 199–202
* S. Huddleston, K. Mehlhorn: ''A New Data Structure for Representing Sorted Lists''. In ''Acta Informatica 17'', 1982, S. 157–184
* {{Anker|Mehlhorn1}}Kurt Mehlhorn: ''Datenstrukturen und effiziente Algorithmen.'' Teubner Stuttgart 1988, ISBN 3-519-12255-3.

== Weblinks ==
* [https://www.cs.unm.edu/~rlpm/499/ttft.html Arbeitsweise eines 2-3-4-Baumes] (englisch, [[Java-Applet]])

[[Kategorie:Suchbaum]]

2-3-4-Baum - Versionsgeschichte

imported>일성김: ??? Die letzte Textänderung von 147.142.150.164 wurde verworfen und die Version 209522251 von Aka wiederhergestellt.