Červeno-černý strom

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 2. listopadu 2019; kontroly vyžadují 32 úprav .

Červeno-černý strom

Typ

vyhledávací strom

Rok vynálezu

1972

Autor

Rudolf Bayer

Složitost v O-symbolech

	Průměrný	Při nejhorším
Spotřeba paměti	Na)	Na)
Vyhledávání	O(log n)	O(log n)
Vložit	O(log n)	O(log n)
Odstranění	O(log n)	O(log n)

Mediální soubory na Wikimedia Commons

Red-black tree ( ang. red-black tree , RB tree ) je jeden z typů samovyvažovacích binárních vyhledávacích stromů , který zaručuje logaritmický růst výšky stromu od počtu uzlů a umožňuje rychle provést základní vyhledávací strom . operace: přidání, odstranění a nalezení uzlu. Rovnováhy je dosaženo zavedením dalšího atributu uzlu stromu - "barvy". Tento atribut může nabývat jedné ze dvou možných hodnot – „černá“ nebo „červená“.

Za vynálezce červeno-černého stromu je považován německý vynálezce Rudolf Bayer . Název „červeno-černý strom“ byl datové struktuře dán v článku L. Gimbase a R. Sedgwicka (1978). Podle Gimbase používali dvoubarevná pera [1] . Podle Sedgwicka červená vypadala nejlépe na laserové tiskárně [1] [2] .

Červeno-černý strom se používá k uspořádání srovnatelných dat, jako jsou části textu nebo čísla. Listové uzly červeno-černých stromů neobsahují data, nevyžadují tedy alokaci paměti – stačí zapsat nulový ukazatel jako ukazatel na potomka v uzlu předka. V některých implementacích však mohou být pro zjednodušení algoritmu použity explicitní koncové uzly.

Princip organizace

Červeno-černý strom je binární vyhledávací strom , ve kterém má každý uzel atribut color . kde:

Uzel může být červený nebo černý a má dvě děti;
Kořen je obvykle černý. Toto pravidlo má malý vliv na výkon modelu, protože barvu kořene lze vždy změnit z červené na černou;
Všechny listy, které neobsahují data, jsou černé.
Oba potomci každého červeného uzlu jsou černé.
Jakákoli jednoduchá cesta z uzlu předka k uzlu podřízeného listu obsahuje stejný počet černých uzlů.

Díky těmto omezením je cesta od kořene k nejvzdálenějšímu listu maximálně dvakrát delší než k nejbližšímu a strom je přibližně vyrovnaný. Operace vkládání, mazání a vyhledávání vyžadují v nejhorším případě čas úměrný délce stromu, což umožňuje, aby červeno-černé stromy byly v nejhorším případě efektivnější než běžné binární vyhledávací stromy.

Abychom pochopili, jak to funguje, stačí vzít v úvahu vliv vlastností 4 a 5 společně. Nechť počet černých uzlů od kořene k listu je B pro červeno-černý strom T. Pak nejkratší možná cesta k libovolnému listu obsahuje B uzlů a všechny jsou černé. Zahrnutím červených uzlů lze vybudovat delší možnou cestu. Kvůli klauzuli 4 však strom nemůže mít dva červené uzly za sebou a podle klauzulí 2 a 3, cesta začíná a končí černým uzlem. Nejdelší možnou cestu tedy tvoří 2B-1 uzly, střídavě červené a černé.

Pokud povolíte, aby nelistový uzel měl méně než dva potomky a listový uzel obsahoval data, strom si zachová základní vlastnosti, ale algoritmy pro práci s ním se zkomplikují. Článek se proto zabývá pouze „dummy leaf nodes“, které neobsahují žádná data a slouží pouze k označení toho, kde strom končí. Tyto uzly mohou být na některých ilustracích vynechány. Z položky 5 také vyplývá, že potomky červeného uzlu mohou být buď dva černé mezilehlé uzly, nebo dva černé listy, a s přihlédnutím k položkám 3 a 4 - že pokud je jedním z potomků černého uzlu listový uzel , pak by měl být druhý buď také list, nebo výše popsané provedení jednoho červeného a dvou listů.

Také v literatuře existuje interpretace, ve které nejsou samotné uzly, ale okraje vedoucí k nim, natřeny červenou / černou barvou - to však nemá velký význam pro pochopení principu jeho fungování.

Analogie B-stromu s parametrem 4

Červeno-černý strom má podobnou strukturu jako B-strom s parametrem 4, ve kterém každý uzel může obsahovat 1 až 3 hodnoty, a tedy 2 až 4 ukazatele na děti. V takovém B-stromu bude každý uzel obsahovat pouze jednu hodnotu, odpovídající hodnotě černého uzlu červeno-černého stromu, s volitelnými hodnotami před a/nebo za ním ve stejném uzlu, které obě odpovídají na ekvivalentní červené uzly červeno-černého stromu.

Jedním ze způsobů, jak vidět tuto ekvivalenci, je „zvýšit“ červené uzly v grafické reprezentaci červeno-černého stromu tak, aby byly vodorovně zarovnány se svými černými předchůdci uzlů a vytvořily stránku. V B-stromu nebo upraveném grafickém znázornění červeno-černého stromu mají všechny uzly listů stejnou hloubku.

Tento typ B-stromu je obecnější než červeno-černý strom, i když, jak vidíte, z jednoho takového B-stromu s parametrem 2 lze získat několik červeno-černých stromů. Pokud stránka B-stromu obsahuje pouze jednu hodnotu, uzel je černý a má dva potomky. Pokud stránka obsahuje tři hodnoty, pak je centrální uzel černý a každý z jeho sousedů je červený. Pokud však stránka obsahuje dvě hodnoty, může být kterýkoli uzel v červeno-černém stromě černý (v tom případě bude druhý uzel červený).

Práce s červeno-černými stromy

Červeno-černé stromy jsou v praxi jedním z nejpoužívanějších samovyvažovacích vyhledávacích stromů. Zejména sady a mapové kontejnery ve většině implementací knihovny C++ STL [3] , třídy Java TreeMap [4] a také mnoha dalších implementací asociativních polí v různých knihovnách jsou založeny na červeno-černých stromech.

Červeno-černé stromy jsou oblíbenější než dokonale vyvážené stromy. v druhém případě může být vynaloženo příliš mnoho prostředků na mazání ze stromu a udržování potřebné rovnováhy. Po vložení nebo vymazání je nutná operace přebarvení, která vyžaduje (O(log n ) nebo O(1)) změny barvy (což je v praxi poměrně rychlé) a ne více než tři otočení stromu (ne více než dvě pro vložení ). Ačkoli inzerce a delece jsou složité, stále jsou náročné na O(log n ).

Vložit

Na místo jednoho z listů je přidán nový uzel v červeno-černém stromě, zbarvený červeně a jsou k němu připojeny dva listy (jelikož listy jsou abstrakcí, která neobsahuje data, jejich přidání nevyžaduje další operaci) . Co se stane dále, závisí na barvě blízkých uzlů. Všimněte si, že:

Vlastnost 3 (Všechny listy jsou černé) je vždy pravdivá.
Vlastnost 4 (Oba potomci libovolného červeného uzlu jsou černé) lze narušit pouze přidáním červeného uzlu, přebarvením černého uzlu na červený nebo jeho otočením.
Vlastnost 5 (Všechny cesty z libovolného uzlu do listových uzlů obsahují stejný počet černých uzlů) lze narušit pouze přidáním černého uzlu, přebarvením červeného uzlu na černý (nebo naopak) nebo otočením.

Poznámka : Písmeno N bude označovat aktuální uzel (vybarveno červeně). Za prvé je to nový uzel, který se vkládá, ale tento postup lze použít rekurzivně na jiné uzly (viz případ 3). P bude označovat předka N , G bude označovat dědečka N a U strýce (uzel, který má společného rodiče s uzlem P ). Všimněte si, že v některých případech se role uzlů mohou změnit, ale v každém případě bude každé označení představovat stejný uzel jako na začátku. Jakákoli barva zobrazená na obrázku je v tomto případě buď předpokládána, nebo získána z jiných úvah.

Každý případ je pokryt příklady kódu C. Definice struktury uzlu může vypadat takto:

enum barvy_uzlu { ČERVENÁ , ČERNÁ }; struct node { struct node * parent , * left , * right ; enum barvy_uzlu barva ; intkey ; _ };

Strýce a dědečka aktuálního uzlu lze najít pomocí funkcí:

struct uzel * prarodič ( struct node * n ) { if (( n != NULL ) && ( n -> rodič != NULL )) return n -> parent -> parent ; jiný vrátit NULL ; } struct uzel * strýc ( struct node * n ) { uzel struktury * g = prarodič ( n ); if ( g == NULL ) vrátit NULL ; // Žádný prarodič znamená žádný strýc if ( n -> rodič == g -> vlevo ) return g -> vpravo ; jiný return g -> vlevo ; }

Otočení stromu doleva a doprava lze provést takto:

prázdnota otočit_doleva ( struct node * n ) { struct uzel * pivot = n -> vpravo ; pivot -> rodič = n -> rodič ; /* možná udělá pivot kořenem stromu */ if ( n -> rodič != NULL ) { if ( n -> rodič -> vlevo == n ) n -> rodič -> vlevo = pivot ; jiný n -> rodič -> pravý = pivot ; } n -> vpravo = pivot -> vlevo ; if ( pivot -> left != NULL ) pivot -> vlevo -> rodič = n ; n -> rodič = pivot ; pivot -> vlevo = n ; } prázdnota rotovat_vpravo ( struct node * n ) { struct node * pivot = n -> left ; pivot -> rodič = n -> rodič ; /* možná udělá pivot kořenem stromu */ if ( n -> rodič != NULL ) { if ( n -> rodič -> vlevo == n ) n -> rodič -> vlevo = pivot ; jiný n -> rodič -> pravý = pivot ; } n -> vlevo = pivot -> vpravo ; if ( pivot -> vpravo != NULL ) pivot -> vpravo -> rodič = n ; n -> rodič = pivot ; pivot -> vpravo = n ; }

Případ 1: Aktuální uzel N je u kořene stromu. V tomto případě se přebarví na černo, aby vlastnost 2 (kořen je černý) zůstala pravdivá. Protože tato akce přidá ke každé cestě jeden černý uzel, vlastnost 5 (Všechny cesty z libovolného daného uzlu do koncových uzlů obsahují stejný počet černých uzlů) není narušena.

prázdnota insert_case1 ( struct node * n ) { if ( n -> rodič == NULL ) n -> barva = ČERNÁ ; jiný vložit_případ2 ( n ); }

Případ 2: Rodič P aktuálního uzlu je černý, tj. vlastnost 4 (oba potomci každého červeného uzlu jsou černé) není porušena. V tomto případě strom zůstává správný. Vlastnost 5 (Všechny cesty z libovolného daného uzlu do listových uzlů obsahují stejný počet černých uzlů) není porušena, protože aktuální uzel N má dva černé listové potomky, ale protože N je červené, cesta ke každému z těchto potomků obsahuje stejné počet černých uzlů, což je cesta k černému listu, který byl nahrazen aktuálním uzlem, takže vlastnost zůstává true.

prázdnota insert_case2 ( struct node * n ) { if ( n -> rodič -> barva == ČERNÁ ) vrátit se ; /* Strom je stále platný */ jiný vložit_případ3 ( n ); } Poznámka: V následujících případech se předpokládá, že N má prarodič G , protože jeho rodič P je červený, a pokud by to byl kořen, byl by zbarven černě. N má tedy také strýčka U , i když to může být listový uzel v případech 4 a 5.

Případ 3: Pokud jsou oba rodiče P a strýc U červení, pak mohou být oba přebarveni černě a prarodič G zčervená (aby se zachovala vlastnost 5 (Všechny cesty z libovolného daného uzlu k uzlu listu obsahují stejný počet černých uzlů)) . Nyní má aktuální červený uzel N černého rodiče. Protože jakákoli cesta přes rodiče nebo strýce musí projít přes prarodiče, počet černých uzlů v těchto cestách se nezmění. Avšak prarodič G nyní může porušit vlastnosti 2 (kořen je černý) nebo 4 (oba potomci každého červeného uzlu jsou černé) (vlastnost 4 může být narušena, protože rodič G může být červený). Abychom to napravili, celý postup se provádí rekurzivně na G z případu 1.

prázdnota insert_case3 ( struct node * n ) { uzel struktury * u = strýc ( n ), * g ; if (( u != NULL ) && ( u -> barva == ČERVENÁ )) { // && (n->parent->color == RED) Druhá podmínka je testována v insert_case2, tj. rodič je již červený. n -> rodič -> barva = ČERNÁ ; u -> barva = ČERNÁ ; g = prarodič ( n ); g -> barva = ČERVENÁ ; insert_case1 ( g ); } jinak { vložit_případ4 ( n ); } } Poznámka: Ve zbývajících případech se předpokládá, že rodič P je levým potomkem svého předka. Pokud tomu tak není, musíte prohodit levou a pravou . O to se postarají příklady kódu.

Případ 4: Rodič P je červený, ale strýc U je černý. Také aktuální uzel N je pravým potomkem P a P je zase levým potomkem svého předka G . V tomto případě lze provést rotaci stromu, která změní role aktuálního uzlu N a jeho předka P . Potom pro bývalý nadřazený uzel P v aktualizované struktuře použijte případ použití 5, protože vlastnost 4 (oba potomci libovolného červeného uzlu jsou černé) je stále porušena. Rotace způsobí, že některé cesty (v podstromu označeném v diagramu "1") procházejí uzlem N , což dříve nebylo. To také způsobuje, že některé cesty (v podstromu označeném „3“) neprocházejí přes uzel P . Oba tyto uzly jsou však červené, takže vlastnost 5 (Všechny cesty z libovolného daného uzlu do koncových uzlů obsahují stejný počet černých uzlů) není rotací narušena. Vlastnost 4 je však stále porušována, ale nyní je problém omezen na Případ 5.

prázdnota insert_case4 ( struct node * n ) { uzel struktury * g = prarodič ( n ); if (( n == n -> rodič -> vpravo ) && ( n -> rodič == g -> vlevo )) { otočit_doleva ( n -> rodič ); n = n -> vlevo ; /* * rotation_left lze provést následovně, za předpokladu, že již existuje *g = grandparent(n) * * struct node *saved_p=g->left, *saved_left_n=n->left; * g->levý=n; * n->left=ulozeny_p; * uloženo_p->vpravo=uloženo_vlevo_n; * */ } else if (( n == n -> rodič -> vlevo ) && ( n -> rodič == g -> vpravo )) { otočit_vpravo ( n -> rodič ); n = n -> vpravo ; /* * otočit_vpravo lze provést následovně, za předpokladu, že již existuje *g = prarodič(n) * * uzel struktury *saved_p=g->vpravo, *uložené_vpravo_n=n->vpravo; *g->vpravo=n; * n->vpravo=ulozeno_p; * uloženo_p->vlevo=uloženo_vpravo_n; * */ } vložit_případ5 ( n ); }

Případ 5: Rodič P je červený, ale strýc U je černý, aktuální uzel N je levým potomkem P a P je levým potomkem G . V tomto případě je strom otočen o G . Výsledkem je strom, kde bývalý rodič P je nyní rodičem současného uzlu N i bývalého prarodiče G . Je známo, že G je černá, protože její bývalý potomek P by jinak nemohl být červený (aniž by porušil vlastnost 4). Poté se změní barvy P a G a v důsledku toho strom splňuje vlastnost 4 (oba potomci libovolného červeného uzlu jsou černé). Vlastnost 5 (Všechny cesty z libovolného daného uzlu do koncových uzlů obsahují stejný počet černých uzlů) také zůstává pravdivá, protože všechny cesty, které procházejí kterýmkoli z těchto tří uzlů, dříve procházely přes G , takže nyní všechny procházejí přes P . V každém případě z těchto tří uzlů je pouze jeden zbarven černě.

prázdnota insert_case5 ( struct node * n ) { uzel struktury * g = prarodič ( n ); n -> rodič -> barva = ČERNÁ ; g -> barva = ČERVENÁ ; if (( n == n -> rodič -> vlevo ) && ( n -> rodič == g -> vlevo )) { otočit_vpravo ( g ); } jinak { otočit_doleva ( g ); } }

Odstranění

Při mazání uzlu se dvěma nelistovými potomky v normálním binárním vyhledávacím stromu hledáme buď největší prvek v jeho levém podstromu, nebo nejmenší prvek v jeho pravém podstromu a přesuneme jeho hodnotu do uzlu, který má být odstraněn. Poté odstraníme uzel, ze kterého jsme hodnotu zkopírovali. Kopírování hodnoty z jednoho uzlu do druhého nenarušuje vlastnosti červeno-černého stromu, protože struktura stromu a barvy uzlů se nemění. Stojí za zmínku, že nový uzel, který se odstraňuje, nemůže mít dva nelistové podřízené uzly najednou, jinak nebude největším/nejmenším prvkem. Ukazuje se tedy, že případ smazání uzlu, který má dva nelistové podřízené položky, se redukuje na případ smazání uzlu, který obsahuje nejvýše jeden nelistový podřízený uzel. Proto bude další popis vycházet z předpokladu, že uzel, který má být odstraněn, má nejvýše jednoho nelistového potomka.

Pro uzel, který má být odstraněn, použijeme označení M ; označujeme C potomka M , kterému budeme také jednoduše říkat "jeho potomek". Pokud má M dítě bez listů, berte to jako C . Jinak pro C vezmeme kteréhokoli z potomků listů.

Pokud je M červený uzel, nahraďte jej naším potomkem C , který podle definice musí být černý. (To se může stát pouze v případě, že M má dva listové potomky, protože pokud má červený uzel M černé nelistové dítě na jedné straně a listové dítě na druhé straně, pak bude počet černých uzlů na obou stranách jiný, tím se strom stane neplatným červeno-černý strom kvůli porušení vlastnosti 5.) Všechny cesty přes uzel, který má být odstraněn, budou obsahovat o jeden červený uzel méně, rodič a potomek uzlu, který má být odstraněn, musí být černý, takže Vlastnost 3 („Všechny listy jsou černé“) a Vlastnost 4 („Oba potomci červeného uzlu jsou černé“) stále platí.

Dalším jednoduchým případem je, když M je černé a C je červené. Pouhým odstraněním černého uzlu by došlo k porušení vlastnosti 4 („Oba potomci červeného uzlu jsou černé“) a vlastnosti 5 („Jakákoli jednoduchá cesta z daného uzlu k libovolnému listovému uzlu obsahuje stejný počet černých uzlů“), ale pokud bychom recolor C černá, obě tyto vlastnosti zůstanou zachovány.

Obtížný případ je, když jsou M i C černé. (To se může stát pouze tehdy, když je odstraněn černý uzel, který má dva listové potomky, protože pokud černý uzel M má černé nelistové potomky na jedné straně a listové potomky na druhé straně, pak počet černých uzlů na obou stranách bude jiný a strom se stane neplatným červeno-černým stromem, protože je porušena vlastnost 5.) Začneme nahrazením uzlu M jeho potomkem C . Tomuto potomkovi (v jeho nové pozici) budeme říkat N a jeho „bratr“ (další potomek jeho nového předka) – S. (Předtím byl S "bratrem" M .) Na obrázcích níže budeme také používat označení P pro nového předka N (starý předek M ), S L pro levé dítě S , a S R pro pravého potomka S ( S nemůže být listový uzel , protože pokud je N podle našeho předpokladu černé, pak podstrom P , který obsahuje N , má výšku dvě černé, a proto druhý podstrom P , který obsahuje S , musí také být černý s výškou dva, což nemůže být případ, kdy S je list) .

Poznámka : V některých případech měníme role a označení uzlů, ale v každém případě jakékoli označení nadále znamená stejný uzel jako na začátku případu. Jakékoli barvy zobrazené na obrázku jsou buď předpokládané náhodou, nebo získané z jiných předpokladů. Bílá znamená neznámou barvu (buď červenou nebo černou).

Budeme hledat „bratra“ pomocí této funkce:

struct uzel * sourozenec ( struct node * n ) { if ( n == n -> rodič -> vlevo ) return n -> parent -> right ; jiný return n -> parent -> left ; } Poznámka : Aby strom zůstal správně definovaný, potřebujeme, aby každý list zůstal po všech transformacích listem (aby neměl žádné potomky). Pokud má uzel, který odstraňujeme, nelistový potomek N , je snadné vidět, že vlastnost platí. Na druhou stranu, pokud N je list, pak, jak můžete vidět z obrázků nebo kódu, vlastnost také platí.

Výše uvedené kroky můžeme provést pomocí následujícího kódu, kde funkce replace_nodenahrazuje childuzel nve stromu. Pro usnadnění kód v této části předpokládá, že listy null jsou reprezentovány skutečnými objekty uzlu, nikoli NULL (kód vložení by měl fungovat se stejnou reprezentací).

void nahradit_uzel ( uzel * n , uzel * potomek ) { dítě -> rodič = n -> rodič ; if ( n == n -> rodič -> vlevo ) { n -> rodič -> vlevo = dítě ; } jinak { n -> rodič -> pravý = dítě ; } } prázdnota delete_one_child ( struct node * n ) { /* * Podmínka: n má nejvýše jednoho nenulového potomka. */ struct node * child = is_leaf ( n -> right ) ? n -> vlevo : n -> vpravo ; nahradit_uzel ( n , dítě ); if ( n -> barva == ČERNÁ ) { if ( dítě -> barva == ČERVENÁ ) dítě -> barva = ČERNÁ ; jiný odstranit_případ1 ( dítě ); } volný ( n ); } Poznámka : Pokud N je prázdný list a nechceme reprezentovat prázdné listy jako skutečné objekty, můžeme algoritmus upravit tak, že nejprve zavoláme delete_case1() na jeho rodiči (uzel, který jsme odstranili nv kódu výše) a poté jej smažeme že. Můžeme to udělat, protože otec je černý, a proto se chová jako nulový list (a někdy se mu říká 'fantómový' list). Můžeme jej bezpečně odstranit, protože npo všech operacích, jak je uvedeno výše, zůstane listem.

Pokud jsou N a jeho aktuální otec černé, pak odstranění otce způsobí, že cesty, které procházejí skrz N , budou mít o jeden černý uzel méně než cesty, které jím neprocházejí. Protože to porušuje vlastnost 5 (všechny cesty z libovolného uzlu do jeho listových uzlů obsahují stejný počet černých uzlů), musí být strom znovu vyvážen. Je třeba zvážit několik případů:

Případ 1: N je nový kořen. V tomto případě je vše hotovo. Z každé cesty jsme odstranili jeden černý uzel a nový kořen je černý uzel, takže vlastnosti zůstanou zachovány.

prázdnota delete_case1 ( struct node * n ) { if ( n -> rodič != NULL ) delete_case2 ( n ); } Poznámka : V případech 2, 5 a 6 předpokládáme, že N je levým potomkem svého předka P . Pokud se jedná o pravé dítě, musí být ve všech třech případech zaměněny levé a pravé . Příklady kódu to opět berou v úvahu.

Případ 2: S je červené. V tomto případě vyměníme barvy P a S a poté provedeme rotaci doleva kolem P , čímž se S stane prarodičem N . Všimněte si, že P musí být černé, pokud má červené dítě. Výsledný podstrom má stále o jeden černý uzel méně, takže s tím ještě nekončíme. Nyní má N černého sourozence a červeného otce, takže můžeme přejít na kroky 4, 5 nebo 6. (Jeho nový sourozenec je černý, protože byl potomkem červeného S .)

V následujícím bude S označovat nového bratra N .

void delete_case2 ( struct node * n ) { struct node * s = sourozenec ( n ); if ( s -> barva == ČERVENÁ ) { n -> rodič -> barva = ČERVENÁ ; s -> barva = ČERNÁ ; if ( n == n -> rodič -> vlevo ) otočit_doleva ( n -> rodič ); jiný otočit_vpravo ( n -> rodič ); } odstranit_případ3 ( n ); }

Případ 3: Děti P , S a S jsou černé. V tomto případě jednoduše přebarvíme S na červenou. Výsledkem je, že všechny cesty přes S , ale ne přes N mají o jeden černý uzel méně. Protože odstranění otce N způsobí, že všechny cesty procházející skrz N obsahují o jeden černý uzel méně, takové akce vyrovnají rovnováhu. Všechny cesty skrz P však nyní obsahují o jeden černý uzel méně než cesty, které neprocházejí P , takže vlastnost 5 (všechny cesty z libovolného vrcholu do jeho listových uzlů obsahují stejný počet černých uzlů) je stále porušena. Abychom to napravili, použijeme postup opětovného vyvažování na P počínaje případem 1.

void delete_case3 ( struct node * n ) { struct node * s = sourozenec ( n ); pokud ( ( n -> rodič -> barva == ČERNÁ ) && ( s -> barva == ČERNÁ ) && ( s -> vlevo -> barva == ČERNÁ ) && ( s -> vpravo -> barva == ČERNÁ ) ) { s -> barva = ČERVENÁ ; delete_case1 ( n -> parent ); } jinak delete_case4 ( n ); }

Případ 4: S a jeho děti jsou černé, ale P je červené. V tomto případě jednoduše změníme barvy S a P . Toto neovlivní počet černých uzlů na cestách přes S , ale přidá jeden k počtu černých uzlů na cestách přes N , čímž se obnoví vliv odstraněného černého uzlu.

void delete_case4 ( struct node * n ) { struct node * s = sourozenec ( n ); pokud ( ( n -> rodič -> barva == ČERVENÁ ) && ( s -> barva == ČERNÁ ) && ( s -> vlevo -> barva == ČERNÁ ) && ( s -> vpravo -> barva == ČERNÁ ) ) { s -> barva = ČERVENÁ ; n -> rodič -> barva = ČERNÁ ; } jinak delete_case5 ( n ); }

Případ 5: S je černá, levé dítě S je červené, pravé dítě S je černé a N je levé dítě svého otce. V tomto případě otočíme strom doprava kolem S . Levé dítě S se tak stane jeho otcem a Novým novým bratrem . Poté změníme barvy S a jeho nového otce. Všechny cesty stále obsahují stejný počet černých uzlů, ale nyní má N černého sourozence s červeným pravým dítětem a přejdeme k případu 6. Ani N , ani jeho otec tuto transformaci neovlivňují. (Pro případ 6 označujeme S nového bratra N .)

void delete_case5 ( struct node * n ) { struct node * s = sourozenec ( n ); if ( s -> color == BLACK ) { /* tento příkaz if je triviální kvůli případu 2 (i když případ 2 změnil sourozence na dítě sourozence, dítě sourozence nemůže být červené, protože žádný červený rodič nemůže mít červené dítě). */ /* následující příkazy pouze vynutí, aby byla červená nalevo od levého rodiče nebo napravo od pravého, takže případ šest se otočí správně. */ pokud ( ( n == n -> rodič -> vlevo ) && ( s -> vpravo -> barva == ČERNÁ ) && ( s -> vlevo -> barva == ČERVENÁ ) ) { /* tento poslední test je také triviální kvůli případům 2-4. */ s -> barva = ČERVENÁ ; s -> vlevo -> barva = ČERNÁ ; otočit_vpravo ( s ); } jinak pokud ( ( n == n -> rodič -> vpravo ) && ( s -> vlevo -> barva == ČERNÁ ) && ( s -> vpravo -> barva == ČERVENÁ ) ) { /* tento poslední test je také triviální kvůli případům 2-4. */ s -> barva = ČERVENÁ ; s -> vpravo -> barva = ČERNÁ ; otočit_doleva ( s ); } } delete_case6 ( n ); }

Případ 6: S je černá, pravé dítě S je červené a N je levé dítě svého otce P . V tomto případě otočíme strom doleva kolem P , načež se S stane rodičem P a jeho pravým potomkem. Dále vyměníme barvy P a S ( P převezme barvu S , S barvu P ) a uděláme ze správného potomka S černou. Podstrom má stále stejnou kořenovou barvu, takže vlastnosti 4 (Oba potomci každého červeného uzlu jsou černé) a 5 (všechny cesty z libovolného vrcholu do jeho listových uzlů obsahují stejný počet černých uzlů) nejsou narušeny. Nicméně N má nyní dalšího černého předka: buď se P stal černým, nebo byl černý a S byl přidán jako černý prarodič. Cesty procházející přes N tedy procházejí jedním dalším černým uzlem.

Mezitím, pokud cesta neprochází přes N , existují 2 možné možnosti:

Prochází novým bratrem N. Pak musí projít S a P , které jen změnily barvy a místa. Cesta tedy obsahuje stejný počet černých uzlů.
Prochází novým strýcem N , pravým dítětem S . Kdysi prošel přes S , otce S a pravé dítě S (které bylo červené), ale nyní prochází pouze S , které na sebe vzalo barvu svého bývalého rodiče, a pravé dítě S , které má přelakován z červené na černou (předpokládáme, že barva S : černá). Výsledkem je, že tato cesta prochází stejným počtem černých uzlů.

V každém případě se počet černých uzlů na těchto cestách nezmění. Proto jsme obnovili vlastnosti 4 (Oba potomci každého červeného uzlu jsou černé) a 5 (všechny cesty z libovolného vrcholu do jeho listových uzlů obsahují stejný počet černých uzlů). Bílý uzel v diagramu může být červený nebo černý, ale musí označovat stejnou barvu na začátku i na konci transformace.

void delete_case6 ( struct node * n ) { struct node * s = sourozenec ( n ); s -> barva = n -> rodič -> barva ; n -> rodič -> barva = ČERNÁ ; if ( n == n -> rodič -> vlevo ) { s -> vpravo -> barva = ČERNÁ ; otočit_doleva ( n -> rodič ); } jinak { s -> vlevo -> barva = ČERNÁ ; otočit_vpravo ( n -> rodič ); } }

Všechna volání rekurzivních funkcí jsou sledována a převedena na smyčky, takže algoritmus vyžaduje paměť O(1) . Ve výše uvedeném algoritmu jsou všechny případy propojeny postupně, kromě případu 3, kde může dojít k návratu k případu 1, což platí pro předchůdce uzlu: toto je jediný případ, kdy sekvenční implementace bude efektivní smyčkou (po jednom rotace v případě 3).

Také koncová rekurze se nikdy nevyskytuje na podřízených uzlech, takže koncová rekurzní smyčka se může přesunout pouze z podřízených uzlů k jejich následným rodičům. K případu 1 (kde n je celkový počet uzlů ve stromu před smazáním) nebude existovat více než O(log n ) zpátečních cest . Pokud dojde k rotaci v případě 2 (jediné možné v cyklu případů 1-3), pak otec uzlu N po rotaci zčervená a cyklus opustíme. Během tohoto cyklu tedy nebude provedeno více než jedno otočení. Po opuštění smyčky proběhnou maximálně dvě další rotace. Obecně nedojde k více než třem otočením stromu.

Porovnání s vyváženým stromem AVL

Výška stromu

Nechť výška stromu je h, minimální počet vrcholů N. Potom:

pro AVL strom . Protože , , N(h) roste jako Fibonacciho posloupnost , tedy , kde $N(h)=N(h-l)+N(h-2)+l$ $N(0)=0$ $N(1)=1$ $N(h)=\Theta (\lambda ^{h})$ $\lambda =({\sqrt {5}}+1)/2\cca 1,62$
pro červeno-černé dřevo $N(h)\geq 2^{{(h-1)/2}}=\Theta ({\sqrt {2}}^{h})$

Proto při stejném počtu listů může být červeno-černý strom vyšší než strom AVL, ale ne více než faktor 1. [5] $\log \lambda /\log {\sqrt {2}}\cca 1,388$

Hledat

Vzhledem k tomu, že červeno-černý strom je v nejhorším případě vyšší, je v něm hledání pomalejší, ale ztráta v čase nepřesahuje 39 %.

Vložit

Vložení vyžaduje až 2 otáčky v obou typech stromů. Vzhledem k větší výšce červeno-černého stromu však může vkládání trvat déle.

Odstranění

Odstranění z červeno-černého stromu vyžaduje až 3 otočení, ve stromu AVL může vyžadovat počet otočení až do hloubky stromu (ke kořenu). Proto je odstranění z červeno-černého stromu rychlejší než odstranění ze stromu AVL. Testy však ukazují, že AVL stromy jsou ve všech operacích rychlejší než červeno-černé stromy [6] [7] , autor posledního testu naznačuje, že červeno-černé stromy mohou být výkonnější s velkým množstvím paměti [8] .

Paměť

Strom AVL v každém uzlu ukládá výškový rozdíl (celé číslo od -1 do +1, pro kódování jsou potřeba 2 bity). Červeno-černý strom v každém uzlu ukládá barvu (1 bit). Červeno-černý strom tak může být ekonomičtější. (Pravda, vzhledem k tomu, že v moderních počítačových systémech je paměť alokována v násobcích bajtů, pak jsou stromy úplně stejné)

V praxi však oba typy stromů používají celá čísla, protože práce s bity vyžaduje dodatečné výpočty procesoru (jedna instrukce assembleru a %al 0x10000000). Existují však implementace červeno-černého stromu, které ukládají hodnotu barvy v bitech. Příkladem je Boost Multiindex . Účelem uložení barvy v bitu je snížit spotřebu paměti červeno-černého stromu ( komprese uzlu uspořádaných indexů ). Barevný bit v této implementaci není uložen v samostatné proměnné, ale v jednom z ukazatelů uzlu stromu, čímž se změní na označený ukazatel .

Důkaz asymptotických hranic

Červeno-černý strom, který obsahuje n vnitřních uzlů, má výšku . $O(log(n))$

Označení:

$h(v)$ je výška kořenového podstromu $proti$
$bh(v)$ je počet černých uzlů (nepočítá -li se, pokud je černý) od libovolného listu v podstromu (tzv. černá výška) $proti$ $proti$

Lemma: Podstrom zakořeněný v uzlu má alespoň vnitřní uzly. $proti$ $2^{bh(v)}-1$

Důkaz lemmatu (indukcí na výšku):

Základ indukce: . $h(v)=0$

Pokud má podstrom nulovou výšku, pak musí být null , takže . $proti$ $bh(''v'')=0$

Tak:

2^{bh(v)}-1=2^{0}-1=1-1=0

Indukční krok: nechť je uzel takový, že podstrom má také alespoň vnitřní uzly. Ukažme, že pak , pro které , má alespoň vnitřní uzly. $proti$ $h(v)=k$ $2^{bh(v)}-1$
$proti'$ $h(v')=k+1$ $2^{bh(v')}-1$

Protože má , jedná se o vnitřní uzel. Jako takové má dvě děti, z nichž obě jsou černé výšky (podle toho , zda je červená nebo černá). Podle indukční hypotézy má každý potomek alespoň vnitřních uzlů, a proto jich má alespoň $proti'$ $h(v')>0$ $bh(v')$ $bh(v')-1$ $proti'$
$2^{bh(v')-1}-1$ $proti'$

2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1

vnitřní uzly.

Pomocí tohoto lemmatu můžeme ukázat, že strom má logaritmickou výšku. Protože alespoň polovina uzlů v jakékoli cestě od kořene k listu je černá (vlastnost 4 červeno-černého stromu), černá výška kořene je alespoň . Podle lemmatu máme: $h(root)/2$

n\geq 2^{{{h({\text{root))) \over 2}}}-1\leftrightarrow \;\log _{2}{(n+1)}\geq {h({\ text{root))) \přes 2}\leftrightarrow \;h({\text{root)))\leq 2\log _{2}{(n+1)}.

Výška kořene je tedy . $O(log(n))$

Viz také

Hloubka první hledání
Šířka první hledání
Vyvážené (samobalanční) stromy:

strom AVL
maticový strom
Dokonale vyvážený strom
rozšiřující se strom
B+-stromy
2-3-strom
R-strom
B*-strom

Seznam datových struktur (stromů)

Odkazy

Literatura

Kormen T., Leizerson C., Rivest R., Stein K. Algoritmy: konstrukce a analýza = Introduction to algorithms. - 2. vyd. - M. : Nakladatelství "Williams" , 2011. - S. 336-364. - ISBN 978-5-8459-0857-5 .

Poznámky

↑ 1 2 datové struktury - Odkud pochází termín "Červený/Černý strom"? - Výměna zásobníku softwarového inženýrství . Získáno 4. ledna 2019. Archivováno z originálu 5. ledna 2019. (neurčitý)
↑ Kurz "Algorithms: Design and Analysis, Part 1", přednáška "Red-Black Trees" Archivováno 25. srpna 2014 na Wayback Machine (Video 5:07 )
↑ Dr Dobbs - Červeno-černé stromy STL
↑ Třída TreeMap . Získáno 13. března 2015. Archivováno z originálu 18. března 2015. (neurčitý)
↑ v limitu pro velký počet listů
↑ AVL vs RB Archivováno 11. července 2016 na Wayback Machine
↑ Red-Black versus AVL: benchmarks Archived 10. února 2015 na Wayback Machine
↑ AVL vs. Červeno-černá: závěr Archivováno 10. února 2015 na Wayback Machine

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree