8  Rot-schwarz-Bäume

Literatur: Kapitel 13 aus [CLR90]. Die Rot/Schwarz-Bäume wurden von [Bay72] eingeführt.

Inhalt Rot/Schwarz-Bäume ·Rotation ·Erhalt der Rot-Schwarzeigenschaft bei Einfügen und Löschen

• Hauptproblem der Suchbäume: Effizienz hängt von der Höhe ab
• Þ je balanzierter desto "`besser"' der Baum
• für die Suche: ja; andererseits
  • dauerndes Rebalanzieren kostet auch Zeit Þ Balanciertheitsanforderungen am besten nicht zu strikt (vor allem bei vielen Lösch- und Einfügeoperationen
  • Wie stellt man fest ob ein Baum balanciert ist? (Laufzeit!)
  • speichert man Zusatzinformationen darüber ab? (Speicherplatz!)

• zwei Arten von Knoten: Schwarze werden strikt balanciert, rote dienen als Schlupf.
• Anteil des Schlupfes muß beschränkt sein

• Bild
• Schwarzhöhe bh(x) eines Knotens: die Anzahl der schwarzen Knoten auf den Pfaden (ausschließlich x) zu den Blättern

• Þ die Operationen Suchen, Minimum, Maximum, Successor, Predecessor: O(lgn).
• Einfügen und Löschen?

• Rotation
• Erhalt der In-Ordnung der Schlüssel
• Komplexität O(1)
• Bild

Rotate-l(t,x) =                   // t = Baum, x = Knoten
  if    (x = nil) or (right(x) = nil)
  then  raise error "illegal rotation"
  else  y := right(x);          // rette y
        p(y) := p(x);              // ver"andere y's Verwandschaft
        if   y != nil              
        then right(x) := left(y);  // beta
        if   (left(y)) != nil
        then p(left(y)) := x;
 
        if   root(t) = x           // Spezialfall
        then root(t) := y
        else if   x = left(p(x))  // p(x) definiert
             then  left(p(x)) := y
             else right(p(x)) := y

        left(y) := x;             // zum Schluss: x als Kind von y
        p(x)    := y;               

• Zunächst Einfügen wie im gewöhnlichen binären Suchbaum
• Þ neues rotes Blatt.
  • keine Schwarz-Verletzung, aber u. U.
  • Rot-Verletzung
• Bei rot-Verletzung:
  • Reparieren durch Umfärben und Rotation
  • keine Neueinführung von Schwarzverletzungen

insert(T,x) 
  tree_insert(T,x);                          // normal einfuegen 
  color(x)  := red                           // am Anfang rot
 
  while x != root(t) and color(p(x)) = red   // Rot-verletzung
  do
    if  p(x) = left(p(p(x));                 // Vater ist linker Sohn
       then  y := right(p(p(x))              // y = Onkel, d.h.
                                             // rechter Sohn des Opas
             if  color(y) = red              // Onkel rot
                then  color(p(x))  := black; // => umfaerben
                      color(y)     := black;
                     color(p(p(x)) := red;
                                 x := p(p(x))
                else if x = right(p(x))      // Onkel schwarz
                        then x := p(x);      // x ist rechtes Kind
                             left_rotate(T,x) 

                     color(p(x)) := black;   // Vater <- schwarz
                     color(p(p(x)) := red;   // Opa   <- rot
                    right_rotate(T,p(p(x))); // Ausgleich
        else ....... // analog
  done;
  color(root(T)) := black;