Benutzer:SweetQuaternion/Rot-Schwarz-Boum

Schwarzhöchi, Boumhöchi

Dr Nummere $s$ vo schwarze Knote (wo bi allne Pfad ou gliich isch) tue mr »Schwarzhöchi« (änglisch black height)^[1]^[2] 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 direkten Zugriff ungerstütze (im Gägesatz zum sequentiellen Zugriff vor Traversierung). Sueche bruuche mr geng vorere Modifikationsoperation (IIifüege oder Lösche), so chöi mr d richtige 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.

↑ 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] 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.

[2] 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]