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 ämou 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,^[1]) het immer d gliichviu schwarzi Knote wie en angerer.

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.

Schwarzhöchi, Boumhöchi

Dr Nummere $s$ vo schwarze Knote (wo bi allne Pfad ou gliich isch) tue mr »Schwarzhöchi« (änglisch black height)^[2]^[3] säge. Das säge mr für ganzi Böim, aber ou für Wurzuknote. Zum Bispiu tuet us dem fouge, dass e Knote vo Schwarzhöchi 0 es rots Blatt isch (de isch siini Boumhöchi 1) wie ou d Knotn ${\mathsf {6,22,27}}$ ii üsem Bispiuboum – oder en unechter (und leerer) Knote wo Boumhöchi 0 het. I dem Artikel da si schwarz Knote immer ächt (u trage Schlüssu) u hei Schwarzhöchi u Boumhöchi ≥ 1. D rote Knote ${\mathsf {8,17}},$ aber ou d schwarze Knote ${\mathsf {1,11,15,25}},$ hei Schwarzhöchi 1. D schwarze Knote ${\mathsf {1,25}}$ hei Baumhöchi 2, d Knote ${\mathsf {11,15}}$ Baumhöchi 1, u ${\mathsf {1}}$ isch dr einzigscht Knote mit emne Usgangsgrad 1, es angeres Haubblatt gits nid.

Dur d zwo Forderige wird die wichtigscht Eigeschaft von Rot-Schwarz-Böim garantiert:

We $s$ d Schwarzhöchi vomne Boum isch, de gits wäge dr Forderig S#= uf emne Pfad vor Wurzu zum Ändi genau $s$ schwarze Knote, aber wäge dr Forderig !RR maximau ei Knote meh aus schwarze, auso aues zäme maximau $2s\!+\!1$ Knote. Auso wüsse mr für d Zahl $n$ vo allne Knote im Boum $2^{s}\!\!-\!\!1\leq n\leq 2^{2s+1}\!\!-\!\!1$ , so isch üser Boum mmer tiptop balanciert. – uf jede Fau so guet dass für ds Vrhäutnis zwüsche Baumhöchi $h,$ (wo mr $s\leq h\leq 2s\!+\!1$ wüsse), u dem Logarithmus vor Anzahl $n$ vo Knote immer bschränkt isch. Die Bschränkig , wo mir da formau bewiise, isch aber immer ou ds Optimum wo mir informationstheoretisch chöi erreiche, s git auso ke Binärboum mitere chliinere maximale Pfadlängi aus $h\!\!-\!\!1\in {\mathcal {O}}(\log n).$

Bi dene drü Operatione Sueche, Iifüege u Lösche isch dr Ufwand konstant für aui Knote uf dr gliiche Ebeni. Auso isch d Laufziit höchstens proportional zur Anzahl Knote imne Pfad, wo ja ou wider maximau d Höchi isch, wo limitiert isch dur d Logaritmus vor Knotezahl.

NIL-Knote

Zur Erklärig vo tue mr e Sichtwiise aanäh wo aui Knote wo Schlüssel hei interni Knote sii, aber mr tue em Boum zuesätzlech no »NIL-Knoten« aahänge, wo wie externe Blätter funktioniere. Die tue mr überau da häre wo Knote fähle.

Mr wüsse de:

NIL-Knote si immer schwarz.
Aui Ching vomne rote Knote si schwarz.
S si immer gliich viui schwarze Knote imne Pfad vomne Knote zu emne NIL-Knote.

S isch gliich aber besser we mr das aus Nullpointer implementiere, schüsch hei mr binere naive Implementierig när vilech es Problem.

Datestruktur

Mi hei da en Biispiucode, wo i dr Programmiersproch C isch gschribe:

 struct RBnode  // Knotefäud
 {
   struct RBnode* child[2]; // Pointer uf sini ≤2 Chindknote
                // oder NIL: kes Chind
   byte color;  // RED oder BLACK
   ...          // Benutzer-Date (z. B. Schlüssu, Wert)
 } ;

 #define LEFT  0
 #define RIGHT 1
 #define left  child[LEFT]  // -> linker  Chindknote
 #define right child[RIGHT] // -> rechter Chindknote
 #define RED   0
 #define BLACK 1

We mr NIL anere Stäu im Boum finge, wo mr en Pointer ufene Knote würd erwarte, de bedütet das, dass e Knote fäut (dr Knoten isch unächt). Das bedütet: dr Teilboum mit NIL-Knote aus Wurzu isch leer u het Schwarz- u Baumhöchi 0.

Sin Pointerwert X == NIL isch nid äso wichtig wie dr Ort, wo dr Wert steit wiu dr Wort d Beziehige zu angeren Element aagit:

En NIL-Knote cha es Chind vonerem angere Knote sii, ou we dr Knote nid würkli en Knote repräsentiert. Auso cha er ou es Gschwöschterti oder e Götti ha, aber nie säuber Ching.

Siini Boumhöchi u Schwarzhöchi tue mr beidi 0 setze u er het ou ke Farb. Er het en Elternknote, aber nie en Pointer druf.

Mou aagno e Datestruktur tuet Operatione vomne Rot-Schwarz-Boum nutze (egau ob Zuegriff oder Vrwautig), de müesse die d Forderige vo obe erhaute.Das bedütet, sie müesse dr ganze Boum nachere Operation no einisch prüefe u (we öppis nid ganz tiptop isch) repariere. So tue mr üsi Datestruktur zu emneAbstrakte Datetyp (ADT) mache. Bi Suechböim hei mr im Änglische ou d Charakterisierig self-balancing tree.

Navigationsoperatione

D Navigationsoperatione si d verschiednige Suechoperatione, auso ds Traversiere, Sueche und so wiiter, löh d Boum eifach äso la sii, tue auso nüt vürändere (eifach nume läse) u funktioniere uf aune binäre Suechboum. Mir chöi auso d Algorithme vo dene Suechböim nutze u ihri Komplexität übernäh. Zur Erinnerig: d Höchi vomne Rot-Schwart-Boum isch immer logarithmisch zur Anzahl Knote. Dasch ganz gäbig.

Ds Sueche vomne Element (oder e Lücke) mit emne Schlüssu isch d wischtigscht Navigationsoperation. D Balancierig vomne Rot-Schwarz-Boum wott genau die Operation tiptop optimiere. Sie tuet en direkte Zuegriff ungerstütze (im Gägesatz zu emne sequentielle Zuegriff vor Traversierig). Sueche bruuche mr geng vorere Modifikationsoperation (IIifüege oder Lösche), so chöi mr d richtigi Stäu drzue finge.

Sueche chöi mr aber nume we mr e totali Quasiordnig uf dr Schlüssumängi hei, wo mr am beschte mitere Vergliichsfunktion realisiere. We mr Duplikate wei erlaube, de bruuche mr e Suechfunktion wo es birebitzeli abgwandlet isch.

Fuessnote

↑ bei Ben Pfaff non-branching node
↑ Bei Ben Pfaff ist die Schwarzhöhe eines Knotens die einheitliche Anzahl schwarzer Knoten auf allen Pfaden zu den Pfadenden im von ihm gewurzelten Teilbaum.
↑ Mehlhorn 2008 S. 155 färbt die Kanten rot/schwarz und zählt als Schwarztiefe (änglisch black depth) eines Knotens die Zahl der schwarzen Kanten von ihm zur Wurzel.

[1] Ben Pfaff non-branching node

[2] Bei Ben Pfaff ist die Schwarzhöhe eines Knotens die einheitliche Anzahl schwarzer Knoten auf allen Pfaden zu den Pfadenden im von ihm gewurzelten Teilbaum.

[3] Mehlhorn 2008 S. 155 färbt die Kanten rot/schwarz und zählt als Schwarztiefe (änglisch black depth) eines Knotens die Zahl der schwarzen Kanten von ihm zur Wurzel.

[1]

[2]

[3]