Prof. Uwe Schulz

Vorlesung Informatik 2 - Teil B: Theorie

4.12 Rot-Schwarz Bäume

Der Münchner Informatiker Rudolf Bayer hat 1972 eine Verbesserung vorgeschlagen, welche die Vorteile von 2-3-4-Bäumen und AVL-Bäumen vereint.

Die Verwaltung von mehreren Kindern in einem Knoten bei den 2-3-4 Bäumen ist recht umständlich. Diesen Nachteil gleichen die Rot-Schwarz Bäume (kurz: RS Bäume) aus.

Ein 4-Knoten kann leicht als Binärbaum dargestellt werden:

      (  G |  K |  P )                                  K                      
      /     |     |     \      -->                    /    \
     A    H     L    S                            G         P 
                                                    /  \       /  \
                                                   A   H    L    S

Er vereint die Vorteile eines 2-3-4- Baumes mit der einfacheren Struktur von Binärbäumen. Für einen RS Baum gilt:

• jeder Knoten ist entweder Rot oder Schwarz
• Die Kinder eines roten Knotens sind schwarz.
• Für jeden Knoten k gilt: jeder Pfad zu einem Blatt enthält die gleiche Anzahl schwarzer Knoten.

Da es ein Binärbaum ist, kann man die Grundoperationen für das Suchen und Traversieren direkt übernehmen.

Beim Einfügen wird jeder rot-schwarze Teilbaum als 3- oder 4-Knoten betrachten, d.h. es wird nach dem Einfügen wenn nötig ein Split gemacht und eine neue Ebene eingeführt. Dabei werden auch Rotationen wie beim AVL Baum notwendig.

Nach dem Einfügen muss auf dem Weg zur Wurzel geprüft werden, ob ein 4-Knoten gesplittet werden muss. Für diesen Algorithmus gib es zwei Varianten:

1.  bottom-up, also vom neu eingefügten Knoten zur Wurzel 
2. top-down, also von der Wurzel zum neu eingefügten Knoten.  

Variante 2 ist etwas einfacher zu erklären, deshalb folgendes Beispiel:

        AVL-Baum                                     entsprechender 2-3-4 Baum

                N                                                     ( I | N ) 
              /    \                                                 /    |      \
            I        P                                             /      |       \
          /   \                                                   H   (J K L)   P 
        H    K 
              /  \    
            J      L  

Um M in diesen Baum einzufügen führen wir folgende Schritte durch:

1. Auf dem Weg von der Wurzel zu M suchen wir 4-Knoten  (im Beispiel: K)
2. Umfärben des 4-Knotens und seiner Kinder
3. Rotation oberhalb des 4-Knotens wie beim AVL Baum
4. Umfärben des rotierten Knotens und seiner Kinder
5. Einfügen des neuen Knotens

Am Beispiel sehen diese Schritte wie folgt aus:

     nach Schritt 1+2             nach Schritt 3a: Linksrotation von L           nach 3b: Rechtsrot. von N

                N                                                   N                                               K                                                 K
               /    \                                              /     \                                          /     \             4+5                         /   \
            I        P             3a: LR_I                   K       P         3b: RR_N                 I        N           -------->                I      N
          /   \                  ------->                 /    \               --------->           /   \     /   \                                     /  \    /  \
        H     K                                            I        L                                      H    J   L     P                                  H   J   L    P
              /  \                                         /   \                                                                                                              \
            J      L                                     H      J                                                                                                            M

Im Mittel haben RS-Bäume die Komplexität O(log N) für das Suchen, Einfügen und Löschen.

In der Praxis werde Rot-Schwarz Bäume häufig als Suchbäume eingesetzt. Ein Beispiel ist die Map-Implementierung TreeMap in der Java API.

Lehrvideo (YouTube)