Arbori rosu-negru (red-black trees)

Notiuni introductive

In capitolul precedent am vazut ca principalele operatii asupra arborilor binari de cautare (cautare, minim, maxim, inserare si stergere) se realizeaza in O(h), unde h este inaltimea arborelui. Am aratat, de asemenea, ca in cazul unei distributii uniforme a cheilor de cautare, inaltimea h a arborelui este proportionala cu , unde n este numarul de noduri ale arborelui. Exista totusi posibilitatea nefericita in care arborele binar de cautare devine degenerat, situatie in care viteza operatiilor nu este cu nimic mai buna decat in cazul unei liste liniare inlantuite.

Figura 1.1‑ Doi arbori binari de cautare care contin aceleasi chei (2,3,5,5,7,8). In primul arbore, orice operatie de cautare necesita cel mult 3 comparatii, in timp ce in arborele din dreapta sunt necesare maxim 5 comparatii

In figura de mai sus, ambii arbori contin aceleasi chei de cautare. Totusi, inaltimea (adancimea) lor este diferita: primul arbore are adancimea 2, iar al doilea are adancimea 4. Este evident ca in arborele din stanga operatiile de cautare, inserare etc. se realizeaza mai rapid decat in cazul arborelui din dreapta.

Arborii rosu-negru reprezinta una dintre numeroasele structuri de cautare care sunt 'echilibrate', pentru a garanta ca chiar si in cazul cel mai nefavorabil, inaltimea este proportionala cu .

Ce este un arbore rosu-negru?

Arborii rosu-negru sunt arbori binari de cautare, care mai au niste proprietati in plus. Un nod al unui arbore rosu-negru poate sa fie rosu sau negru. Aceasta presupune deja ca in cadrul fiecarui nod sa gestionam un bit (0/1) in plus pentru a retine culoarea nodului. Echilibrarea unui arbore rosu-negru este asigurata de anumite constrangeri pe care le impunem asupra culorilor nodurilor.

Un nod al unui arbore rosu-negru va contine pe langa informatiile obisnuite (valoarea (INFO), fiul din stanga (FS), fiul din dreapta (FD), culoarea (CUL)) si o referinta catre parintele sau, pe care o vom nota cu P. Daca fiul unui nod nu exista, atunci referinta care ii corespunde va fi NIL; parintele radacinii este de asemenea NIL. Pentru comoditatea descrierii arborilor rosu-negru, vom privi fiecare legatura NIL ca fiind un pointer catre o frunza a arborelui (v. Figura 1.2‑1) etichetata cu NIL.

Definitie: Un arbore rosu-negru este un arbore binar de cautare care are in plus urmatoarele proprietati:

P1. Fiecare nod este fie rosu, fie negru

P2. Toate frunzele (NIL) sunt negre

P3. Daca un nod este rosu, atunci ambii fii sunt negri

P4. Toate drumurile de la un nod la o frunza contin acelasi numar de noduri negre

Figura 1.2‑ Exemplu de arbore rosu-negru, cu nodurile negre inchise, iar nodurile rosii umbrite. Fiecare nod intr-un arbore rosu-negru este fie rosu, fie negru, fiecare frunza (NIL) este neagra, ambii descendenti ai unui nod rosu sunt negri, fiecare cale de la un nod la o frunza din subarborele sau are acelasi numar de noduri negre. In stanga fiecarui nod s-a trecut n-adancimea nodului. Frunzele au n-adancimea 0.

Numarul de noduri negre de la un nod,    x, pana la o frunza a lui il vom numi n-adancimea nodului, notata cu na(x).

Propozitia urmatoare arata de ce arborii rosu-negru sunt echilibrati:

Propozitie: An arbore rosu-negru cu n noduri are adancimea cel mult .

Demonstratia acestei propozitii este simpla si o gasiti in [2].

O consecinta directa a acestei propozitii este ca operatiile de cautare, minim si maxim definite in capitolul anterior pentru arborii binari de cautare au complexitate .

Desi algoritmii de inserare (INSERT) si de stergere (DELETE) din capitolul anterior au evident complexitatea si pentru arborii rosu-negru, ei nu pot fi utilizati pentru a insera, respectiv sterge dintr-un arbore rosu-negru, deoarece nu garanteaza ca arborele rezultat va fi tot un arbore rosu-negru. Pentru a intelege mai bine acest aspect, sa incercam sa aplicam algoritmul DELETE din paragraful Error! Reference source not found., pentru a sterge nodul 47 din arborele din Figura 1.2‑1. Arborele rezultat va fi:

Figura 1.2‑ Arbore rosu-negru din care s-a sters un nod utilizand algoritmul DELETE. Se observa ca notiunea de n-adancime nu mai are sens pentru nodurile 26 si 41

In acest arbore deja nu mai putem vorbi de n-adancimea nodurilor 26 si 41. De exemplu, pe drumul 26-41-NIL avem doua noduri negre, in timp ce pe drumul 26-41-30-38-39-NIL avem trei noduri negre.

In consecinta, algoritmii INSERT si DELETE trebuie adaptati pentru a pastra structura de arbore rosu-negru, sau, cu alte cuvinte, pentru a respecta proprietatile P1-P4. Vom vedea in paragrafele care urmeaza, ca desi algoritmii de INSERARE si STERGERE sunt mai complecsi decat in cazul arborilor binari de cautare simpli, complexitatea lor ramane .

Exercitii:

Desenati arborele de cautare complet cu inaltimea 2 care contine cheile . Adaugati frunzele (NIL) si incercati sa colorati nodurile in asa fel incat sa rezulte un arbore rosu-negru!

Sa presupunem ca radacina unui arbore rosu-negru este rosie. Daca o facem neagra, arborele ramane arbore rosu-negru?

Rotatia

Am vazut in paragraful precedent ca daca aplicam arborilor rosu-negru operatiile DELETE si INSERT definite pentru arborii binari de cautare, acestea nu pastreaza proprietatile P1-P4. Solutia la care s-a recurs este aceea de a utiliza totusi aceste operatii, dupa care se 'repara' stricaciunile pe care ele le-au produs, prin schimbarea culorilor anumitor noduri si a modului de inlantuire.

O operatie simpla pe care o vom folosi in curand la 'repararea' stricaciunilor este rotatia.

Figura 1.3‑ Reprezentarea operatiilor de rotatie asupra unui arbore de cautare. Operatia Rotatie-dreapta(T) modifica configuratia celor doua noduri din stanga in configuratia din dreapta prin modificarea unui numar constant de legaturi. Reciproc, configuratia din dreapta poate fi transformata in configuratia din stanga prin operatia inversa, Rotatie-stanga(T). Nodurile x si y pot sa apara oriunde intr-un arbore binar de cautare. Literele a b si g desemneaza subarbori arbitrari. T este un pointer catre radacina subarborelui. Operatia de rotatie pastreaza ordonarea cheilor: cheile din    a sunt mai mici decat x, care este mai mic decat cheile din b, care sunt mai mici decat y, care este mai mic decat cheile din g

Modul de inlantuire al nodurilor este schimbat prin operatia de rotatie, care este o operatie locala intr-un arbore de cautare care pastreaza ordinea cheilor. Figura 1.3‑1 prezinta doua tipuri de rotatii: la stanga si la dreapta. Rotatiile 'pivoteaza' in jurul legaturii dintre x si y.

Algoritmul Rotatie-stanga(T) de mai jos realizeaza rotatia la stanga a subarborelui cu radacina T, care contine cheia x: y devine radacina, x devine fiul stang al lui y, iar fiul stang al lui y devine fiul drept al lui x:

ROTATIE-STANGA(T)

U = T.FD //U va fi un pointer catre fiul din dreapta al lui T, care are cheia y

T.FD = U.FS //subarborele stang al lui y (b) devine subarborele drept al lui x

Daca U.FS <> NIL atunci //daca b este nevid

U.FS.P = T //parintele lui U.FS (b) devine T (nodul cu cheia x)

U.P = T.P //parintele lui U este acum parintele lui T

Daca T.P <> NIL atunci //daca T nu este chiar radacina

Daca T = T.P.FS atunci //daca T este fiul din stanga al tatalui sau

T.P.FS = U //noul fiu din stanga al tatalui lui T este U

Altfel

T.P.FD = U //noul fiu din dreapta al tatalui lui T este U

U.FS = T //T devine fiul din stanga al lui U

T.P = U //parintele lui T este acum U

END (ROTATIE-STANGA)

Rutina de mai sus este o simpla secventa de atribuiri prin care se modifica legaturile nodurilor care se rotesc. In consecinta complexitatea ei este constanta, O(1). Figura de mai jos arata efectul operatiei de rotire catre stanga asupra unui arbore de cautare oarecare. Se roteste la stanga axa 11-16:

Figura 1.3‑ Efectul operatiei de rotatie asupra unui arbore binar de cautare oarecare. Se observa ca dupa rotatie arborele ramane de cautare

Exercitii:

Desenati arborele rezultat in urma inserarii in arborele din Figura 1.2‑1 a nodului cu cheia 36. Daca culoarea nodului inserat este neagra, arborele rezultat este arbore rosu-negru? Dar daca culoarea nodului inserat este rosie?

Scrieti programul pseudocod pentru algoritmul Rotatie-dreapta(T)!

Argumentati de ce rotatiile pastreaza structura de arbore de cautare!

Inserarea unui nod intr-un arbore rosu-negru

Pentru a insera un nod x intr-un arbore rosu-negru de radacina T, vom utiliza algoritmul INSERT(T,x) (paragraful Error! Reference source not found.), ca si cand am avea de a face cu un arbore de cautare oarecare. Nodul inserat, x, va fi colorat cu rosu. Urmeaza apoi partea de 'reparare a stricaciunilor' provocate de INSERT, care utilizeaza rotatii si recolorari de noduri.

Sa vedem acum ce fel de stricaciuni poate provoca algoritmul INSERT. Prin stricaciune intelegem violarea uneia dintre proprietatile P1-P4 ale arborilor rosu-negru:

P1 este in mod cert respectata, deoarece culoarea nodului inserat este rosu, iar celelalte culori nu se modifica

P2 este si ea respectata, deoarece nodul nou inserat are copiii NIL

P4, care spune ca numarul de noduri negre    este acelasi pentru orice cale de la un nod dat, este de asemeni respectata, deoarece x inlocuieste un nod NIL(negru), iar x este rosu cu copiii negri

Singura proprietate care poate fi violata este deci P3, care spune ca un nod rosu nu poate avea un fiu rosu. Aceasta se intampla atunci cand tatal nodului nou inserat, x, este rosu, deoarece si x este colorat in rosu.

Algoritmul de inserare trebuie sa rezolve deci violarea proprietatii P3. Figura 1.4‑1 arata modul in care incalcarea lui P3 este rezolvata: ideea este de a muta incalcarea lui P3 catre in sus in arbore, avand insa grija sa mentinem P4.

Figura 1.4‑ Modul de operare al rutinei RB-INSERT. (a) Nodul x, cu cheia 4, dupa inserare, indicat de varibila U. Deoarece atat U cat si parintele sau sunt rosii, apare o violare a lui P3. Unchiul lui U, notat cu V, este rosu, si deci se aplica cazul 1. Nodurile sunt recolorate si pointerul U este mutat catre in sus, ca in figura (b). Inca odata U si parintele sau sunt rosii, dar de data aceasta unchiul V al lui U este negru. Deoarece U este copilul din dreapta al parintelui sau, ne aflam in cazul 2. Se realizeaza o rotatie la stanga si cazul 2 este redus la cazul 3, cu arborele rezultat reprezentat in (c). Acum U este copilul din stanga al parintelui sau, si aplicam cazul 3. O rotatie la dreapta genereaza arborele din (d) care este un arbore rosu-negru corect.

Cea mai mare parte din codul algoritmului de inserare RB-INSERT(T,x), care insereaza nodul x in arborele rosu-negru de radacina T, este dedicata rezolvarii incalcarii lui P3.

RB-INSERT(T,x)

INSERT(T,x) //se apeleaza INSERT din par. Error! Reference source not found.

U = FIND(T,x) //se apeleaza FIND din par. Error! Reference source not found., se retine in U adresa lui x

U.Cul = Rosu //se stabileste culoarea nodului inserat

cat timp U<>T si U.P.Cul=Rosu

daca U.P = U.P.P.FS atunci //tatal lui U este fiul stang al bunicului lui U

V = U.P.P.FD //V este un pointer catre unchiul lui U (y)

daca V.CUL = Rosu atunci //unchiul lui U este rosu, cazul 1

U.P.CUL = Negru

V.CUL = Negru

U.P.P.CUL = Rosu

U = U.P.P //U urca in arbore

altfel //unchiul lui U este negru, cazurile 2,3

daca U = U.P.FD atunci //cazul 2

U = U.P //U urca in arbore

Rotatie-stanga(U) //facem o rotatie pentru a ajunge la cazul 3

U.P.Cul = Negru

U.P.P.Cul = Rosu

Rotatie-dreapta(U.P.P)

altfel (analog cu ramura anterioara, se interschimba doar stanga cu dreapta)

T.Cul = Negru

END (RB-INSERT)

Algoritmul de mai sus nu este chiar asa impunator cum pare; el este mai degraba stufos decat dificil.

Linia 1 realizeaza inserarea nodului x in arbore. Linia 2 retine in variabila U un pointer catre nodul nou inserat[2], x. Linia 3 coloreaza nodul x cu rosu.

Scopul ciclului cat timp din liniile 4-19 este rezolvarea incalcarii lui P3, mentinand P4 invarianta. La inceputul fiecarei iteratii variabila U indica un nod rosu care are parintele rosu, singura ilegalitate din arbore. Conditia U<>T inseamna ca nodul curent, U, este diferit de radacina arborelui, T. Intr-adevar, daca nodul curent este radacina, P3 nu mai poate fi incalcata deoarece radacina nu are parinte. Conditia U.P.Cul = Rosu inseamna ca tatal nodului curent este rosu ca si U, deci apare o incalcare a lui P3; daca tatal lui U este negru, atunci P3 nu este incalcata si algoritmul se incheie.

In ciclul cat timp ar trebui considerate 6 cazuri distincte, dar trei dintre ele sunt simetrice fata de celelalte trei. Primele trei cazuri apar atunci cand parintele lui U, indicat de variabila U.P, este fiul din stanga al bunicului U.P.P al lui U, iar urmatoarele trei apar cand tatal este fiul din dreapta al bunicului. Linia 5 este cea care distinge intre cele doua cazuri. Pentru a nu produce palpitatii, am scris algoritmul numai pentru primele trei cazuri. Pentru a ne asigura ca parintele lui U (care este rosu) nu este chiar radacina am presupus ca radacina arborelui este neagra, fapt de care ne asiguram de fiecare data la terminarea algoritmului, in linia 20. Daca parintele lui U ar fi chiar radacina, atunci (vezi Exercitiul 2, paragraful ) coloram radacina in negru si problema este rezolvata.

Cazul 1 este distins de cazurile 2 si 3 de culoarea unchiului lui U. Linia 6 incarca in variabila V, adresa unchiului lui U, dupa care se testeaza culoarea in linia 7. Daca V este rosu, atunci se executa cazul 1, altfel se da controlul cazurilor 2 si 3. In toate cele trei cazuri bunicul lui U este negru, deoarece tatal lui U este rosu, iar P3 este violata doar de catre U.

Situatia din cazul 1 este prezentata in Figura 1.4‑2. Deoarece bunicul lui U este negru, putem colora pe tatal si pe unchiul sau (U.P si V in figura, liniile 8,9 in algoritm) cu negru, rezolvand astfel problema ca atat U cat si tatal sau sunt rosii, dupa care coloram bunicul (U.P.P) in rosu pentru a mentine P4 (linia 10). Singura problema care ar putea acum sa apara este ca bunicul (U.P.P) sa aiba parintele rosu, si deci trebuie sa repetam ciclul cat timp cu U.P.P ca fiind noul U (linia 11).

Figura 1.4‑ Cazul 1 din procedura RB-INSERT. Proprietatea 3 este violata deoarece atat U cat si tatal sau sunt rosii. Aceeasi actiune are loc si daca (a) U este fiu din dreapta si daca (b) este fiu din stanga. Fiecare dintre subarborii a b g d e are radacina neagra si toti au aceeasi n-adancime. In acest caz se schimba culoarea unor noduri, avand grija sa respectam P4. Ciclul cat timp se reia cu bunicul lui U ca fiind noul U. Orice violare a lui P3 poate acum sa aiba loc numai intre noul U, care este rosu, si parintele sau, in cazul in care si acesta este rosu.

In cazurile 2 si 3 unchiul V al lui U este negru. Cele doua cazuri sunt distinse de faptul ca U este fiul drept sau stang al lui U.P (linia 13). Liniile 14, 15 reprezinta cazul 2 care este prezentat in Figura 1.4‑3, alaturi de cazul 3. In cazul 2, nodul U este fiul din dreapta al parintelui sau. Folosim imediat o rotatie la stanga pe axa A-B pentru a ajunge la situatia din cazul 3. Deorece U si U.P sunt rosii, n-adancimea nodurilor nu este afectata, si deci P4 se mentine. Fie ca intram in cazul 3 direct, fie ca intram prin intermediul cazului 2, unchiul lui U este negru, caci altfel am fi executat cazul 1. Realizam cateva schimbari de culori si o rotatie la dreapta pe axa C-B, dupa care, deoarece nu mai avem doua noduri rosii consecutive, am terminat. Corpul ciclului cat timp nu mai este executat inca o data, deoarece U.P este acum negru.

Figura 1.4‑ Cazurile 2 si 3 ale algoritmului RB-Insert. Ca si in cazul 1, si aici P3 este incalcata, deoarece atat U cat si parintele sau sunt rosii. Fiecare dintre subarborii a b g d e are radacina neagra si toti au aceeasi n-adancime. Cazul 2 este redus la cazul 3 printr-o rotatie la stanga care mentine P4 intacta. Cazul 3 implica niste recolorari si o rotatie la dreapta, care mentin P4 intacta. Ciclul cat timp se termina acum, deoarece P3 este acum satisacuta: nu mai exista doua noduri rosii consecutive.

Care este complexitatea in timp algoritmului RB-Insert? Deoarece adancimea unui arbore cu n noduri este , apelul INSERT(T,x) are complexitate . Ciclul cat timp se executa doar cand ne aflam in cazul 1, si la fiecare iteratie pointerul U urca in arbore. Numarul total de iteratii ale ciclului cat timp este deci si el . Astfel, complexitatea lui RB-Insert este. Este interesant de observat ca RB-Insert nu realizeaza niciodata mai mult de 2 operatii de rotatie, deoarece ciclul cat timp se termina atunci cand se executa cazul 2 sau 3.

Exercitii:

In linia 3 a algoritmului RB-Insert, setam culoarea nodului proaspat inserat pe rosu. Se observa ca daca am fi setat culoarea nodului pe negru, proprietatea 3 nu ar mai fi fost incalcata. De ce nu am setat coloarea nodului pe negru?

In linia 20 a lui RB-Insert, se seteaza culoarea radacinii pe negru. Ce avantaj avem realizand acest lucru?

Desenatii arborii rosu-negru care rezulta dupa inserarea intr-un arbore initial vid a cheilor 50, 27, 25, 10, 13, 4!

Sa presupunem ca n-adancimea fiecaruia dintre subarborii a b g d e din Figura 1.4‑2 si Figura 1.4‑3 este k. Etichetati fiecare nod din cele doua figuri cu n-adancimea sa, pentru a verifica daca P4 este respectata!