Rot-Schwarz-Boum

Rot-Schwarz-Boum
	Komplexität bi $n$ Element
Platz	${\mathcal {O}}(n)$
Operation	im Mittu, amortisiert	im schlimmschte Fau
Sueche	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$
Querschritt	${\mathcal {O}}(1)$	${\mathcal {O}}(\log n)$
Min, Max	${\mathcal {O}}(\log n)$	${\mathcal {O}}(\log n)$
Iifüege	${\mathcal {O}}(1)$†	${\mathcal {O}}(\log n)$
Lösche	${\mathcal {O}}(1)$†	${\mathcal {O}}(\log n)$
† ohni Navigation (nume Rebalancierig)
Platz- u Ziit-Komplexitäte

E Rot-Schwarz-Boum, ou RS-Boum oder RB-Boum, (änglisch red–black tree oder RB tree) isch i dr Informatik e Datestruktur vom Typ binäre Suchboum, wo en „sehr schnäue“ Zuegriff uf d Schlüssu garantiert wo dinne gspiicheret sii. Rot-Schwarz-Böim sii zersch 1972 vo Rudolf Bayer bschribe wurde, wo ihre de symmetric binary B-trees het gseit. Dr Name hüt geit uf Leonidas J. Guibas u Robert Sedgewick zrugg, wo 1978 d rot-schwarzi Farbkonvention hei iigführt. D schnäueri Zuegriffsziite uf d einzelne im Rot-Schwarz-Boum gspiicherte Element (normalerwiise es Paar (Schlüssu, Wert)) cha mr dur zwo Forderungen erreiche, wo d Balance vomne Baums so feschtlegge, dass d Höchi vomne $n$-elementige Boum nie größer aus $2\log _{2}(n\!+\!2)\!-\!2$ cha sii. Wäge dem chöi mr die wichtigscht Operatione imne Suchboum – Suechen, Iifüege u Lösche – uf jede Fau inere Ziit vo ${\mathcal {O}}(\log n)$ (lueg emou Landau-Symbou) usführe.

En Knote imne Rot-Schwarz-Boum het nid nume d Eigeschafte vomne binäre Suechboum, jeder Knote het drzue no es wiiteres Attribut (mir säge dem "Farb") wo zwe Wert cha aanäh: »rot« (RED) u »schwarz« (BLACK). E söttigi Färbig muess immer die beidne Forderige erfüue:

Forderig !RR (»Nid Rot-Rot«):	En Chindknote vomne rote Knote isch schwarz.
Forderig S#= (»Schwarz-Zahl Gliich«):	Jedr Pfad vomne Knoten zu emne Nachfahre mit emne Usgangsgrad ≤1, auso zumne Blatt oder Haubblatt (mr tue dem itz Pfadändi säge,) het immer d gliichviu schwarzi Knote wie en angerer.

Rot-Schwarz-Boum

mit Boumhöchi 4 u Schwarzhöchi 2

E direkti Fougerig vo dene Forderige isch das: Es Haubblatt (zum Biispiu dr Knote ${\mathsf {1}}$ im Biispiuboum obe) isch schwarz u sis einzigs Chind (dr Knote ${\mathsf {6}}$) muess rot sii, wiu beidi es Pfadändi sii, u dr Pfad zum Pfadende ${\mathsf {1}}$_links het genau dr Knote ${\mathsf {6}}$ nid dinne.

Us dene Forderige zäme tuet de ou no fouge, dass en schwarzer Knote wo nid d Wurzu isch, immer es Gschwöscherti het.