Der Inhalt des Dokuments ist zusätzlich freigegeben unter WTFPL.

Rot-Schwarz-Baum

Ein Rot-Schwarz-Baum ist ein selbstbalancierender binärer Suchbaum.

Eine solide Kenntnis binärer Suchbäume ist für die weitere Lektüre dieses Kapitels erforderlich. Für dieses Kapitel relevante Informationen finden sich im Kapitel binärer Suchbaum.

Definition

Ein Rot-Schwarz-Baum T ist eine Datenstruktur mit den folgenden Eigenschaften:

(T1) T ist ein binärer Suchbaum
(T2) Jeder Knoten n besitzt ein zusätzliches Attribut color(n), das stets einen der Werte rot, bzw. schwarz besitzt.
(T3) Die Färbung der Knoten von T erfüllt die folgenden Bedingungen
- (a) Die Wurzel von T ist schwarz
- (b) Alle (externen) Blätter sind schwarz
- (c) Jeder rote Knoten besitzt stets zwei schwarze Kinder
- (d) Jeder Pfad von einem Knoten n zu einem Blatt enthält die selbe Anzahl schwarzer Knoten.
(T4) T unterstützt die folgenden Operationen:
- (a) insert(key) : Füge den Schlüssel key in T ein
- (b) delete(key) : Entferne den Schlüssel key aus T
- (c) lookup(key) : Finde den Knoten n mit Schlüssel key und liefere ihn zurück

Die Anzahl schwarzer Knoten auf dem Pfad von einem Knotens n zu den Blättern wird auch als die Schwarz-Höhe des Knotens n bezeichnet.

Höhe eines Rot-Schwarz-Baums

Die Höhe eines Rot-Schwarz-Baums mit n Knoten ist von der Größenordnung θ(log n).

Die untere Schranke für die Höhe eines Rot-Schwarz Baums ist durch die Höhe eines vollständigen binären Baums gegeben.

Sie beträgt Ω(log n) wie behauptet.

Bei der Abschätzung der oberen Schranke helfen die Färbungs-Eigenschaften T3 eines Rot-Schwarz-Baums.

Die Knoten auf einem längsten Pfad von der Wurzel eines Rot-Schwarz-Baumes der Höhe h zu einem Blatt können wegen T3.c schlimmstenfalls abwechselnd schwarz und rot gefärbt sein.
Jeder Pfad von der Wurzel zu einem Blatt muss wegen T3.d die selbe Anzahl schwarzer Knoten enthalten.
Mindestens bis zur Tiefe h/2 muss ein Rot-Schwarz-Baum somit vollständig besetzt sein.
Ein vollständiger binärer Baum der Höhe h/2 besitzt 2^h/2-1 Knoten.
In der Tiefe h/2 benötigen wir mindestens h/2 weitere Knoten, um die Höhe h des Rot-Schwarz-Baums zu erreichen. Die Zahl n der Knoten in einem Rot-Schwarz-Baum der Höhe h kann daher mit n ≥ 2^h/2 abgeschätzt werden.
Logarithmieren und Umformen liefert die Abschätzung h ≤ 2 log n für die Höhe h eines Rot-Schwarz-Baums mit n Knoten.
Sie ist somit von der Größenordnung O(log n) wie behauptet.