2-3-4-Baum
2-3-4 Baum

Ein 2-3-4-Baum ist in der Informatik eine Datenstruktur, genauer ein B-Baum des Verzweigungsgrades 2, das heißt, er ist ein Baum, in dem jeder 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 balancierten Suchbaum dar.

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

Inhaltsverzeichnis

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.
    • Wenn ja, Suche beendet.
    • Wenn nein, gehe zu 2.
  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 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 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 (Split-Operation). 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 ein Mal 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 Nachbarknoten (Knoten mit gleichem Vorgänger) gibt es aber mindestens zwei Elemente. Es kann ein Element vom Nachbarknoten ausgeliehen werden. Der Schlüssel wird in den Vorgängerknoten verschoben, wobei das Vorgängerelement des zu löschenden Elements an dessen Position verschoben wird und dieses ersetzt.
  • Das Blatt hat nur ein Element. Auch die Nachbarknoten haben nur ein Element. Das Element wird entfernt und sein Vorgängerelement wird mit einem Nachbarelement zusammengelegt. Falls der Vorgängerknoten selbst nur ein einziges Element besitzt, wird dieselbe Operation auf höherer Ebene durchgeführt.

Varianten

2-3-4-Bäume werden beispielsweise durch 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

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 2-4-Baum — 2 3 4 Baum Ein 2 3 4 Baum ist in der Informatik eine Datenstruktur, genauer ein B Baum der Ordnung 4, das heißt, er ist ein Baum, in dem jeder Knoten zwei, drei oder maximal vier Kinder besitzt und entsprechend ein, zwei oder maximal drei… …   Deutsch Wikipedia

  • 1,1,1-Trichlor-2,2-bis-(4-chlorphenyl)ethan — Dieser Artikel beschäftigt sich mit dem Insektizid Dichlordiphenyltrichlorethan. Informationen über die russische Rockmusikgruppe findet man unter DDT (Band). Strukturformel …   Deutsch Wikipedia

  • 2. Bundesliga (Eishockey) 2008/09 — 2. Eishockey Bundesliga ◄ vorherige Saison 2008/09 nächste ► Meister …   Deutsch Wikipedia

  • 2. Eishockey-Bundesliga 2008/09 — 2. Eishockey Bundesliga ◄ vorherige Saison 2008/09 nächste ► Meister …   Deutsch Wikipedia

  • 4. Zusatzartikel zur Verfassung der Vereinigten Staaten — Der 4. Zusatzartikel zur Verfassung der Vereinigten Staaten, das Fourth Amendment, gehört zur Bill of Rights, den ersten 10 Verfassungszusätzen. Er beinhaltet das verbriefte Recht des amerikanischen Bürgers, das ihn vor staatlichen Übergriffen… …   Deutsch Wikipedia

  • Baum-Strelitzie — (Strelitzia nicolai) Systematik Monokotyledonen …   Deutsch Wikipedia

  • Baum — Ein Riesenmammutbaum (Sequoiadendron giganteum) Als Baum wird im allgemeinen Sprachgebrauch eine holzige Pflanze verstanden, die aus einer Wurzel, einem daraus emporsteigenden, hochgewachsenen Stamm und einer belaubten Krone besteht. Inhaltsve …   Deutsch Wikipedia

  • Baum-Topologie — Topologien: Ring, Mesh, Stern, vollvermascht; Linie/Reihe, Baum, Bus Die Topologie bezeichnet bei einem Computernetz die Struktur der Verbindungen mehrerer Geräte untereinander, um einen gemeinsamen Datenaustausch zu gewährleisten. Die Topologie… …   Deutsch Wikipedia

  • Baum der Erkenntnis — Michelangelo: Sündenfall und Vertreibung aus dem Paradies (Deckenfresko in der Sixtinischen Kapelle) Als Baum der Erkenntnis von Gut und Böse (hebr. עץ הדעת טוב ורע °ez had da°at tôb wâ râ, griech. τὸ ξύλον τοῦ εἰδέναι γνωστὸν καλοῦ καὶ πονηροῦ,… …   Deutsch Wikipedia

  • Baum — 1. Alte Bäum lassen sich nicht (oder: eher brechen als) biegen. – Lehmann, 8, 27. 2. Alte Bäum leiden s nicht, dass sie die jungen wollen überschatten. – Lehmann, 57, 13. 3. Alte Bäume ersticken mit jhrem überschatten die jungen auffschösslinge.… …   Deutsches Sprichwörter-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”