Kurs:Algorithmen und Datenstrukturen/Vorlesung/2-3-4-Bäume

Startseite

Vorlesung

1.Einleitung

2. Theoretische Grundlagen

2.1 Programmierparadigmen

2.2. Laufzeitanalysen

2.3. Entwurfsmuster

3. Suchen

3.1 Suchen in sortierten Folgen

3.2 Suchen in Texten

4. Sortieren

4.1 Algorithmen für vergleichsbasiertes Sortieren

4.2 Weitere Sortierprobleme

5. Dynamische Datenstrukturen

5.1 Binäre Suchbäume

5.2 AVL Bäume

5.3 2-3-4-Bäume und Rot-Schwarz Bäume

5.4 Heaps

5.5 Hashtabellen

6. Graphen

6.1 Einführung

6.2 Breitensuche

6.3 Tiefensuche

6.4 Topologisches Sortieren

6.5 Berechnung kürzester Wege

6.6 Berechnung maximaler Flüsse

6.7 Spannbäume

7. Optimierung

7.1 Grundlagen

7.2 Kombinatorische Optimierung

7.4 Lineare Optimierung

7.5 Simplex Verfahren

2-3-4-Bäume

Auf dieser Seite werden die 2-3-4-Bäume behandelt. Die Idee ist ein ausgeglichener Baum mit variablem Verzweigungsgrad. Die Ausgeglichenheit wird bei der Einfügeoperation gewährleistet und die Implementierung erfolgt durch Binärbäume.

Neben binären Knoten (2-Knoten) haben wir nun auch 3-Knoten und 4-Knoten.

Operationen

Die Suche in 2-3-4 Bäumen erfolgt analog zu binären Suchbäumen. Beim Einfügen liefert eine erfolglose Suche den Blattknoten b. Ist b ein 2- oder 3-Knoten wird eingefügt. Aber ist b ein 4-Knoten dann wird aufgeteilt (split) und das mittlere Element nach oben gezogen. Das Splitten kann sich bis zur Wurzel fortpflanzen (bottom-up).

Literatur

Da die Vorlesungsinhalte auf dem Buch Algorithmen und Datenstrukturen: Eine Einführung mit Java von Gunter Saake und Kai-Uwe Sattler aufbauen, empfiehlt sich dieses Buch um das hier vorgestellte Wissen zu vertiefen. Die auf dieser Seite behandelten Inhalte sind in Kapitel 14.4.1 zu finden.