Fügen Sie Schlüssel ein oder löschen Sie sie, und verfolgen Sie jeden Teilschritt der Reparatur einzeln: Umfärben, Rotationen, die Fälle A–C beim Einfügen und die Fälle 1–4 beim Löschen. Die Sedgewick-Ansicht zeigt rote Kanten horizontal und macht die Verbindung zum 2-3-4-Baum sichtbar.
Das Prinzip
Ein Rot-Schwarz-Baum ist ein binärer Suchbaum mit fünf Regeln:
- Jeder Knoten ist rot oder schwarz.
- Die Wurzel ist schwarz.
- Die NIL-Blätter (leere Kinder) sind schwarz.
- Ein roter Knoten hat nur schwarze Kinder.
- Auf jedem Pfad von einem Knoten zu den NIL-Blättern liegen gleich viele schwarze Knoten.
Der längste Pfad ist damit höchstens doppelt so lang wie der kürzeste. Der Baum ist weniger streng ausgeglichen als ein AVL-Baum, braucht dafür aber weniger Rotationen pro Änderung (obere Schranke).
Einfügen
Der neue Knoten N ist rot und verletzt höchstens Regel 4 (rot unter rot). Entscheidend ist der Onkel O, also das Geschwister des Vaters V:
| Fall | Onkel O | Massnahme |
|---|---|---|
| A | rot | V und O schwarz, G rot. Das Problem wandert zum Grossvater G nach oben. |
| B | schwarz, N und V bilden eine Linie | V schwarz, G rot, eine Rotation an G. Fertig. |
| C | schwarz, N und V bilden einen Knick | Rotation an V macht aus dem Knick eine Linie, danach Fall B. |
Die Fälle B und C gibt es je spiegelbildlich. Beim Löschen kommen vier weitere Fälle hinzu (Bruder rot, Bruder schwarz mit schwarzen Kindern, Knick, Linie). Die Simulation zeigt sie Schritt für Schritt.
Python-Code (Einfügen)
RED, BLACK = True, False
class Node:
def __init__(self, key, parent=None):
self.key, self.color = key, RED # ein neuer Knoten ist immer rot
self.left = self.right = None # None = schwarzes NIL-Blatt
self.parent = parent
def is_red(n):
return n is not None and n.color == RED
class RedBlackTree:
def __init__(self):
self.root = None
def _replace(self, old, new):
new.parent = old.parent
if old.parent is None:
self.root = new
elif old is old.parent.left:
old.parent.left = new
else:
old.parent.right = new
def _rotate_left(self, x):
y = x.right
x.right = y.left
if y.left:
y.left.parent = x
self._replace(x, y)
y.left, x.parent = x, y
def _rotate_right(self, y):
x = y.left
y.left = x.right
if x.right:
x.right.parent = y
self._replace(y, x)
x.right, y.parent = y, x
def insert(self, key):
parent, cur = None, self.root
while cur: # wie im gewöhnlichen binären Suchbaum
if key == cur.key:
return
parent, cur = cur, (cur.left if key < cur.key else cur.right)
n = Node(key, parent)
if parent is None:
self.root = n
elif key < parent.key:
parent.left = n
else:
parent.right = n
self._fix_insert(n)
def _fix_insert(self, n):
while is_red(n.parent): # Regel 4 verletzt: rot unter rot
p = n.parent
g = p.parent # Grossvater (die Wurzel ist schwarz)
p_is_left = p is g.left
uncle = g.right if p_is_left else g.left
if is_red(uncle): # Fall A: umfärben, Problem wandert hoch
p.color = uncle.color = BLACK
g.color = RED
n = g
continue
if n is (p.right if p_is_left else p.left): # Fall C: Knick -> Linie
(self._rotate_left if p_is_left else self._rotate_right)(p)
n, p = p, n
p.color, g.color = BLACK, RED # Fall B: eine Rotation an G
(self._rotate_right if p_is_left else self._rotate_left)(g)
self.root.color = BLACK # Regel 2
Verwendung: tree = RedBlackTree(), dann tree.insert(10) für jeden Schlüssel.