TIN066 Červeno-černé stromy
Definice: BVS nazveme červeno-černý, je-li každý vrchol obarven červenou / černou barvou a platí:
- listy jsou černé
- otec červeného vrcholu je černý
- všechny cesty kořen - list mají stejný počet černých vrcholů
Z definice lze vidět, že kořen může mít libovolnou barvu. Je zvykem barvit ho černě.
Nechť červeno-černý strom T má k černých vrcholů na cestě kořen-list. Nejmenší takový strom má samé černé vrcholy. Největší takový strom má "střídavě" černou / červenou hladinu. Tedy $ k \leq výška(T) \leq 2k $. Tedy počet vrcholů #T takového stromu je $ 2^k-1 \leq \#T \leq 2^{2k}-1 $. Z toho je vidět, že výška stromu je O(log n) vůči počtu vrcholů.
Obsah
Algoritmy
Operace Vyhledej a MEMBER jsou stejné, jako u BVS. Při vkládání a mazání bude třeba strom vyvažovat pomoci Rotace a Dvojita-rotace.
Definice: dvojici (T, v) nazveme 2-parciální červeno-černý strom, když navíc povolíme vrcholu v červeného předka.
2-parciální strom (červený předek červeného v) je třeba vyvážit, což provede procedura Vyvaz-INSERT(T, v).
Vyvaz-INSERT v :
- pokud (v kořen) NEBO (v.otec BLACK) končím;
- pokud (v.otec kořen) v.otec BLACK; končím;
- pokud (strýc RED) otec BLACK; strýc BLACK; děda RED; Vyvaz-INSERT(děda); končím;
- pokud (otec i děda oba praví / oba leví synové) děda RED; otec BLACK; Rotace(děda, otec);
- jinak děda RED; v BLACK, Dvojita-rotace(děda, otec, v)
INSERT x: Vytvoříme červený vrchol v s hodnotou x, přidáme dva černé listy, připojíme v do vhodného listu T, Vyvaz-INSERT(v);
Definice: dvojici (T, v) nazveme 3-parciální červeno-černý strom, když:
- listy a v jsou černé
- otec červeného listu je černý
- cesty z kořene do listů mimo v mají k černých vrcholů, cesty z kořene do listů přes v mají k-1 černých vrcholů.
Vyvaz-DELETE v : převede 3-parciální červeno-černý strom na červeno-černý strom
- u = bratr v
- pokud (u RED) Rotace(otec, u); u = nový bratr v; // nyní u BLACK, otec RED
- w1 je syn u "ve směru v" (w1 levý <=> v levý); w2 bratr w1;
- pokud (w1 BLACK, w2 BLACK) u RED;
- pokud (otec RED) otec BLACK; jinak Vyvaz-DELETE(otec);
- pokud (w1 BLACK, w2 RED) Rotace(otec, u), w2 BLACK, barva u = barva otce, otec BLACK;
- jinak Dvojita-rotace(otec, u, w1) barva w1 = barva otce, otec BLACK;
Left-leaning Red-Black Trees (LLRB)
Varianta červeno-černých stromů s podobnými vlastnostmi, ovšem odvozená z binární reprezentace 2-3 resp. 2-3-4 stromů, tedy s velmi přímočaře odvoditelnými rotacemi. Samozřejmě není jisté, jestli na zkoušku stačí umět jen LLRB...
Stručný nástin struktury
2-3-4 stromy jsou takové stromy, které v každém uzlu mají jednu až tři hodnoty a dva až čtyři děti; v případě více hodnot fungují jako B-stromy, tzn. "mezi" každými dvěma hodnotami může vést další hrana k potomkům v daném rozsahu (listy jsou virtuální uzly). Při vkládání do 2-3-4 stromů se vždy do skorolistu přidá další hodnota a štěpí se rekurzivně nahoru - vyváženost se udržuje tak, že všechny listy jsou na stejné úrovni a další úroveň se přidá jen při přeplnění kořene.
2-3-4 stromy lze snadno rozdrobit do klasického binárního stromu, a to přesně uděláme - jen musíme umět simulovat v rámci binárního stromu štěpení. Uděláme tedy to, že hrany spojující prvky v rámci jednoho 2-3-4 uzlu obarvíme červeně! Abychom měli jednoznačnou korespondenci, zároveň přikážeme, že pokud z uzlu vede pouze jedna červená hrana, musí to být ta levá, a má-li uzel všechny tři hodnoty, musejí dělat véčko, místo aby byly za sebou. Udržení správné korespondence pak zařídíme snadno dvěma jednoduchými rotacemi (vlevo a vpravo), samotné rozštěpení je pak realizováno pouhým přepnutím barev (uzlu se dvěma červenými hranami dolů obarvíme hranu nahoru červeně a hrany dolů černě)!
Zachován u LLRB je klasický invariant, že nikdy nemáme dvě červené hrany za sebou a že počet černých hran ve všech cestách k listům je stejný.
Vkládání do stromu pak uděláme trochu jinak než u 2-3-4 stromů. Budeme opět chtít hodnotu vložit do stávajícího uzlu 2-3-4 stromu, tedy budeme vkládat červený vrchol. Ovšem abychom měli jistotu, že se nám do uzlu vrchol vejde, už při sestupování budeme preventivně štěpit všechny trojhodnotové vrcholy, které potkáme! (Tedy přepneme barvy u každého vrcholu véčka, tedy vrcholu se dvěmi červenými hranami dolů.) Rekurzi si dále zjednodušíme tím, že zatímco štěpení budeme provádět už při sestupu k listům, opravu struktury (rotace pro left-leaning a véčkování) budeme dělat až po cestě zpět.
Lepší je podívat se na obrázky ve slajdech.
Mazání
Složitější vymyslet je u RB stromů mazání. Hrubá idea je taková, že si už při sestupu k uzlu upravujeme strukturu tak, že samotným utrhnutím už nic nezkazíme; při cestě zpátky pak budeme dělat to samé, jako při insertu, takže nemusíme při úpravě struktury brát velké ohledy.
Kdy nezkazíme nic utrhnutím? Když nezmenšíme počet černých hran, tedy buď hrana do uzlu nebo z uzlu musí být červená. Vždy se díváme o uzel dopředu, jestli tuto podmínku splňuje; pokud ne, uděláme sekvenci rotací takovou, abychom hranu od nás k synovi na červeno obarvili. Můžete ji zkusit vymyslet, nebo se podívat na obrázek do článku níže.
Studijní materiály
- Slajdy (konec ignorujte; bez mazání): http://www.cs.princeton.edu/~rs/talks/LLRB/08Penn.pdf
- Článek: http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
