Home

Vorlesung Informatik 2 - Teil B: Theorie

4.11 2-3-4 Bäume

Ein AVL Baum ist ein Binärbaum, d.h. jeder Knoten hat maximal zwei Kinder. Solche Knoten werden auch als 2-Knoten bezeichnet. 

Um den Verwaltungsaufwand zu reduzieren, kann man höherwertige Knoten einführen, die auch als 3-Knoten bzw. 4-Knoten bezeichnet werden. Dabei gilt:

  • 2-Knoten speichern einen Schlüssel und haben zwei Kinder. Das linke Kind ist kleiner, das rechte größer als der Vaterknoten.
  • 3-Knoten speichern zwei Schlüssel und haben drei Kinder. Das linke Kind ist kleiner als der erste Schlüssel, das rechte Kind größer als der zweite Schlüssel und das mittlere Kind liegt zwischen den beiden Schlüsseln.
  • 4-Knoten speichern drei Schlüssel und haben vier Kinder. Die beiden mittleren Kinder liegen in der Reihenfolge jeweils zwischen dem ersten und zweiten bzw. dem zweiten und dritten Schlüssel.

Beispiel:

  2-Knoten                3-Knoten                    4-Knoten
     K                      H|K                         H|K|P
    / \                   /  |  \                     /  | |  \
   B   R                 B   J   R                   B  J   L  R

Ein Suchbaum, der aus solchen Knoten besteht und dessen Blätter alle auf der gleichen Ebene sind wird als 2-3-4-Baum bezeichnet. 

Obwohl die Komplexität gleich ist wie beim AVL Baum spart er Aufwand sowohl beim Speicherplatz als auch bei der Höhe, somit sind 2-3-4-Bäume in der Praxis bis zu zweimal schneller als AVL Bäume. 

Die Suche im 2-3-4-Baum erfolgt prinzipiell wie bei binären Suchbäumen, wobei natürlich mit allen Schlüsseln eines Knotens verglichen werden muss.

Beim Einfügen wird ein Knoten zunächst aufgefüllt, bis er drei Einträge enthält. Kommt ein vierter hinzu, muss der Knoten in zwei 2-Knoten aufgeteilt werden (Split).

Beispiel: der links gezeigte AVL Baum hat als 2-3-4-Baum nur zwei Ebenen:

                 L                                       E|J|N
               /   \                                   /  | |   \
             I       N                                /   /  \   \
           /  \     / \                              /   /    \   \ 
         E     J   M   P                            /    |     |   \
       /   \    \     / \                       A|B|C  F|G|I  K|L|M  O|P|R
      B     G    K   O   R
     / \   /
    A   C  F

Der rechts gezeigte 2-3-4-Baum ist voll, um noch ein Element, z.B. D einzufügen, muss ein Split durchgeführt werden:

  • Suche den Knoten, der D enthalten müsste (A|B|C)
  • schiebe ein Element nach oben, z .B. C 
  • in E|J|N ist auch kein Platz für C werden, deshalb entsteht eine neue Ebene

                            J
                         /      \
                        /         \
                       C|E          N
                      / |  \       /  \ 
                     /  |   \     /    \
                   A|B  D F|G|I  K|L|M  O|P|R
   

Die 2-3-4 Bäume sind etwas komplexer zu implementieren, bieten aber mehrere Vorteile:

  • Da sie weniger Ebenen enthalten ist die Suche effizienter
  • Ein Knoten enthält mehrere Schlüssel/Werte Paare, d.h. der Speicherbedarf und Verwaltungsaufwand ist geringer.

Lehrvideo (YouTube)