In einem Binärbaum hat jeder Knoten genau ein Datenelement und maximal zwei Kinder. Es gibt auch Bäume, die mehr Datenelemente und mehr Kinder erlauben. Diese heißen dann Multiway-Bäume. Ein Vertreter ist der 2-3-4-Baum, bei dessen Knoten bis zu drei Datenelemente und maximal vier Kinder haben können.
Was sind 2-3-4-Bäume?
Die Zahlen im Namen beziehen sich auf die Anzahl der Kinder, die ein Knoten haben kann. Folgende Kombinationen können vorkommen (und nur diese!):
- Ein Knoten mit einem Datenelement hat zwei Kinder
- Ein Knoten mit zwei Datenelementen hat drei Kinder
- Ein Knoten mit drei Datenelementen hat vier Kinder
Die Regel lautet folglich, dass ein Knoten immer ein Kind mehr als Datenelemente hat. Ein Knoten mit zwei Datenelementen kann niemals vier oder zwei Kinder haben, während ein Knoten mit drei Elementen nie nur zwei Kinder haben kann. Jeder Knoten hat mindestens zwei Kinder; die Möglichkeit eines Knotens mit nur einem Kind wie in einem Binärbaum kann in einem 2-3-4-Baum nicht vorkommen, wie Sie noch sehen werden.
Diese Regel gilt nur für Knoten, die keine Blätter sind. Blätter haben keine Kinder, aber sie können bis zu drei Datenelemente beinhalten. An dieser Regel sehen Sie auch, warum der Baum nicht 1-2-3-4-Baum heißen kann, da der Fall mit einem einzigen Kind niemals auftreten kann. Das ist auch logisch, denn ein Knoten mit einem Element muss nach der obigen Regel zwei Kinder haben. Ein Kind könnte folglich nur ein leerer Knoten besitzen; leere Knoten sind jedoch nicht erlaubt. Ein 2-3-4-Baum ist ein Baum vierter Ordnung, da die Knoten bis zu vier Kinder haben können. Ein Binärbaum wäre also ein Baum zweiter Ordnung.
Warum verwendet man 2-3-4-Bäume?
2-3-4-Bäume sind aus mehreren Gründen sehr interessant. Zum Einen handelt es sich um balancierte Bäume. Da die oben beschriebenen Regeln eingehalten werden müssen, befinden sich die Blätter immer auf derselben Ebene. Da keine so großen Struktur-Änderungen notwendig sind wie bei Rot-Schwarz-Bäumen, um die Balance zu halten, sind 2-3-4-Bäume wesentlich leichter zu programmieren, sind allerdings weniger effizient.
Der wichtigste Punkt jedoch ist, dass 2-3-4-Bäume als eine leicht verständliche Einführung in die sog. B-Bäume dienen können. In B-Bäumen können Knoten Duzende oder sogar Hunderte von Kindern haben. Es handelt sich dabei also um wesentlich komplexere Multiway-Bäume und daher bilden 2-3-4-Bäume eine ganz gute Möglichkeit, das Grundprinzip an einem nicht so komplexen Baum kennenzulernen.
Organisation eines 2-3-4-Baums
Wie in der Informatik gewohnt, müssen Kinder und Datenelemente mit einem eindeutigen Index benannt werden. In beiden Fällen beginnt der Index bei 0. Datenelemente werden also von 0 bis 2 nummeriert, Kinder von 0 bis 3. Die Datenelemente in einem Knoten sind nach ihrem Schlüssel aufsteigend sortiert.
Nun müssen wir uns anschauen, wie die Kinder organisiert sind. Beginnen wir damit, dass wir die Beziehung zwischen Eltern und Kindern im einfacher verständlichen Binärbaum wiederholen. Dort sind alle Datenelemente, deren Schlüssel kleiner sind der des Elternelements im linken Teilbaum einsortiert, alle größeren im rechten Teilbaum. Wenn wir von der 20 ausgehen, befindet sich die 10 links, die 25 ist das rechte Kind. Im Prinzip sieht es im 2-3-4-Baum nicht wesentlich anders aus, aber es steckt noch ein bisschen mehr drin:
- Die Elemente im ersten Kind haben einen kleineren Schlüssel als das erste Datenelement im Elternknoten.
- Die Schlüssel der Elemente des zweiten Kind liegen zwischen dem ersten und dem zweiten Element im Elternknoten.
- Im dritten Kind liegen die Schlüssel zwischen dem zweiten und dem dritten Element des Elternknotens.
- Und die Schlüssel des vierten Kindes sind größer als die im dritten Element des Elternknotens.
Die Logik in dieser Ordnung ist also nicht komplizierter als im Binärbaum; man muss nur zwei Kinder und zwei Datenelemente mehr bedenken. Doppelte Schlüssel sind normalerweise in einem 2-3-4-Baum nicht erlaubt. Knoten, die keine Blätter sind, sind oft nicht voll, haben also weniger als drei Datenelemente. Dass der Baum immer balanciert ist, liegt an der Art des Einfügens neuer Daten, wie Sie gleich sehen werden. Zuerst wollen wir aber noch kurz über die Suche nach Daten nachdenken.