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:
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.
Im folgenden verwenden wir node.uncle
für den Onkel (Bruder des Vaters).
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.
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
TODO !