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.
