Anpassen der Rot-Schwarz-Labels nach einer Löschoperation

Wie aus den Aufgaben des 7. Übungsblattes zur Coma 2 hervorgeht, ist die Höhe eines Rot-Schwarz-Baumes mit n Knoten beschränkt durch THETA(n). Und im Gegensatz zu AVL-Bäumen konnten wir sehen, dass in Rot-Schwarz-Bäumen auch beim Löschen eine konstante Anzahl an Rotationen genügt, um alle Strukturen in einem konsistenten Zustand zu hinterlassen.

In der Großen Übung vom 30.05.2001 wurde das Vorgehen beim Löschen eines Knotens skizziert. Auf dieser Seite findet ihr nun den entsprechenden Quellcode nach Cormen, Leiserson und Rivest, sowie Skizzen, welche die verschiedenen Fälle veranschaulichen sollen.

Quellcode

/*******************************************************************\
 * Fixes the red-black values in a tree, from that one node has
 * just been extracted.
 * Taken from Cormen, Leiserson, Rivest 1990.
 * @param T the tree
 * @param x the (unique) child of the deleted node, could be an
 *          artificial leaf, but must have one extra black count
\*******************************************************************/
public static void RB_Delete_Fixup(RB_tree T, RB_Node x) {
  while (x!=T.getRoot() && x.getColor()==BLACK) {
    if (x==x.getParent().getLeft()) {
      RB_Node w=x.getBrother(); RB_Node p=x.getParent();
      if (w.getColor()==RED) {
        // --- CASE 1 ---
        w.setColor(BLACK);
        p.setColor(RED);
        p.rotateLeft();                     // rotation
        w=x.getBrother();
      }
      if (w.getLeft().getColor()==BLACK && w.getRight().getColor()=BLACK) {
        // --- CASE 2 ---
        w.setColor(RED);
        x=p;                                // imagine extra black pushed up
      } else {
        if (w.getRight().getColor()==BLACK) {
          // --- CASE 3 ---
          w.getLeft().setColor(BLACK);
          w.setColor(RED);
          w.rotateRight();                  // rotation
          w=x.getBrother();
        }
        // --- CASE 4 ---
        w.setColor(p.getColor());
        p.setColor(BLACK);
        w.getRight().setColor(BLACK);
        p.rotateLeft();                     // rotation
        x=T.getRoot();                      // finish loop
      }
    } else {
      // completely symmetric case!
    }
  }
  x.setColor(BLACK);
}

Diesen Quellcode gibt es auch als Textdatei.

Skizzen

Die nicht eingezeichneten Teilbäume werden bei Rotationen derart umgesetzt, dass sich der Inorder-Durchlauf (LWR) nicht ändert. Der Knoten x mit seinem extra Schwarzwert ist zu Beginn jeweils der linkeste Knoten. Bei grauen Knoten spielt es keine Rolle, ob sie zuvor rot oder schwarz waren, solange am Ende der Knoten mit dem selben Grauton den selben Rot-Schwarz-Wert erhält.

Fall zu Beginn am Ende

CASE 1

CASE 2

CASE 3

CASE 4

Insbesondere findet Fall 4 auch dann Anwendung, wenn der Bruder w des doppelt schwarzen Knotens x zwei rote Kinder besitzt.

Autor: Christian Liebchen
erstellt am 30.05.2001