Rot-Schwarz-Baum

Ein Rot-Schwarz-Baum ist ein spezieller binärer Suchbaum, der automatisch ausbalanciert ist. Dadurch wird gewährleistet, dass er bei n Elementen maximal Höhe ld(n) hat. Dies wird erreicht, in dem die Struktur Binärbaum um folgende Eigenschaften beziehungsweise Regel erweitert wird:

  1. Jeder Knoten ist rot oder schwarz gefärbt.
  2. Die Wurzel ist immer schwarz gefärbt.
  3. Alle 'NIL'-Blätter sind schwarz.
  4. Ist ein Knoten rot, so sind seine Kinder stets schwarz.
  5. Für alle Knoten im Rot-Schwarz-Baum gilt, dass auf allen Pfaden (von diesem Knoten aus) zu den NIL-Blättern die Anzahl schwarzer Knoten gleich ist.

Die Anzahl der schwarzen Knoten auf jedem Pfad von der Wurzel zu jedem NIL-Blatt ist damit gleich und wird Schwarzhöhe genannt.

Bemerkung: In einem Rot-Schwarz-Baum haben traditionell alle Knoten Kinder. Die Kinder der untersten Ebene werden NIL-Blätter genannt und besitzen keine Kinder.

Beispiel: [1]

Im folgenden verwenden wir node.uncle für den Onkel (Bruder des Vaters).

Operationen

Auf Rot-Schwarz-Bäumen werden üblicherweise folgende Operationen ausgeführt:

  • insert(tree, node)
  • delete(tree, node)

Zusätzlich kann in Rot-Schwarz-Bäumen effizient gesucht werden. Der Algorithmus dazu ist identisch zur Suche in binären Suchbäumen und bedarf keiner zusätzlichen Erörterung. Durch die Garantie, dass ein Rot-Schwarz-Baum maximal Höhe ld(n) hat, kann somit stets in O(ld n) gesucht werden.

Knoten einfügen

Zunächst wird der Knoten eingefügt, wie es von binären Suchbäumen bekannt ist. Anschließend muss die eventuell verletzte Rot-Schwarz-Eigenschaft wiederhergestellt werden. Die Korrektheit des folgenden Algorithmus wird hier nicht näher erläutert (sry^^).

function insert(tree, node):
    Füge node in tree "normal" ein
    // "repariere" RB-Tree
    Solange node.parent ist rot:
        Wenn node.uncle ist rot:
            // 1. Fall
            node.parent wird schwarz
            node.uncle wird schwarz
            node.parent.parent wird rot
            // prüfen weiter für den Opa
            node = node.parent.parent
        Sonst // d.h. schwarzer Onkel
            Wenn node rechtes Kind ist:
                // 2. Fall
                node = node.parent
                Links-Rotation um node
            // 3. Fall (und Teil von Fall 2)
            node.parent wird schwarz
            node.parent.parent wird rot
            Rechts-Rotation um node.parent

Knoten löschen

TODO !

Verweise