Rot-Schwarz-Baum

Rot-Schwarz-Baum
	Komplexität bei ${\displaystyle n}$ Elementen
Platz	${\displaystyle {\mathcal {O}}(n)}$
Operation	im Mittel, amortisiert	Worst Case
Suchen	${\displaystyle {\mathcal {O}}(\log n)}$	${\displaystyle {\mathcal {O}}(\log n)}$
Querschritt	${\displaystyle {\mathcal {O}}(1)}$	${\displaystyle {\mathcal {O}}(\log n)}$
Min, Max	${\displaystyle {\mathcal {O}}(\log n)}$	${\displaystyle {\mathcal {O}}(\log n)}$
Einfügen	${\displaystyle {\mathcal {O}}(1)}$ †	${\displaystyle {\mathcal {O}}(\log n)}$
Löschen	${\displaystyle {\mathcal {O}}(1)}$ †	${\displaystyle {\mathcal {O}}(\log n)}$
†  ohne Navigation (nur Rebalancierung)
Platz- und Zeit-Komplexitäten

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 ${\displaystyle n}$ Elementen nie größer als ${\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 ${\displaystyle {\mathcal {O}}(\log n)}$ (s. Landau-Symbole) ausgeführt werden.

1. ↑ Rudolf Bayer: Symmetric Binary B-Trees. Data Structure and Maintenance Algorithms. In: Acta Informatica. 1. Jahrgang, 1972, S. 290–306, doi:10.1007/BF00289509 (englisch). 
2. ↑ Leo J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. In: Proceedings of the 19th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 1978, S. 8–21 (englisch). 

1. ↑ Diese Abschätzung ist scharf (s. Abschnitt Höhenbeweis) und für ${\displaystyle n>0}$ wegen

   ${\displaystyle 2\log _{2}(n+2)-2=2\log _{2}(n/2+1)<2\log _{2}(n+1)}$

   marginal genauer als das vielzitierte

   ${\displaystyle 2\log _{2}(n+1)}$.