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



2-3-4-Bäume

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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.