_Photo_by_Giles_Laurent.jpg)
Ein Rot-Schwarz-Baum, auch RS-Baum oder RB-Baum, (englisch red–black tree oder RB tree) ist eine Datenstruktur vom Typ binärer Suchbaum, die „sehr schnellen“ Zugriff auf die in ihr gespeicherten Schlüssel garantiert. Rot-Schwarz-Bäume wurden zuerst 1972 von Rudolf Bayer beschrieben, welcher sie symmetric binary B-trees nannte. Der heutige Name geht auf Leonidas J. Guibas und Robert Sedgewick zurück, die 1978 die rot-schwarze Farbkonvention einführten. Die schnellen Zugriffszeiten auf die einzelnen im Rot-Schwarz-Baum gespeicherten Elemente (meist Paare vom Typ (Schlüssel,Wert)) werden durch zwei Forderungen erreicht, die die Balance des Baums in einer Weise festlegen, dass die Höhe eines Baums mit
n
{\displaystyle n}
Elementen nie größer als
2
log
2
(
n
+
2
)
−
2
{\displaystyle 2\log _{2}(n\!+\!2)\!-\!2}
sein kann. Somit können die wichtigsten Operationen in Suchbäumen – Suchen, Einfügen und Löschen – garantiert in
O
(
log
n
)
{\displaystyle {\mathcal {O}}(\log n)}
ausgeführt werden. – Mehr erfahren …
Elementen nie größer als
2
log
2
(
n
+
2
)
−
2
{\displaystyle 2\log _{2}(n\!+\!2)\!-\!2}
sein kann. Somit können die wichtigsten Operationen in Suchbäumen – Suchen, Einfügen und Löschen – garantiert in
O
(
log
n
)
{\displaystyle {\mathcal {O}}(\log n)}
ausgeführt werden. –