Rot-Schwarz-Baum

E **Rot-Schwarz-Boum**, ou **RS-Boum** oder **RB-Boum**, ( 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:

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  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« () 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  
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  uf emne Pfad vor Wurzu zum Ändi genau s schwarze Knote, aber wäge dr  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  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 \le h \le 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 *intern*i 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:

```c
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  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