ARBORI ROSU-NEGRI

ARBORI ROsU-NEGRI.

În capitolul 10 am aratat ca operatiile de cautare, predecesor, succesor, minimum, maximum, inserarea, si stergerea pentru un arbore binar de cautare cu înaltimea h se fac în O(h). Deci aceste operatii se executa rapid daca înaltimea este mica; dar, daca înaltimea este mare, performantele lor nu pot fi mai bune decât ale unei lisle înlantuite.

Arborii rosu-negri sunt una din multele scheme de arbori de cautare care sunt "echilibrati" cu scopul de a garanta ca operatiile dinamice sa aiba complexitatea O(lg n).

11.1.Proprietatle arborilor rosu-negri.

Un arbore rosu-negru este un arbore binar care contine cate o informatie în plus pentru fiecare nod aceasta fiind culoarea care poate fi rosu sau negru. Arborii rosu-negrii ne as 757g69h igura ca nu exista o cale cu lungimea de doua ori mai mare decât orice alta cale, deci acesti arbori sunt aproximativ echilibrati.

Fiecare nod al arborelui rosu-negru contine urmatoarele câmpuri:

culoarea (CuI)

cheia (KEY)

legatura din stânga (LS)

legatura din dreapta (LD)

parintele (P)

Un arbore binar de cautare este arbore rosu-negru daca îndeplineste urmatoarele proprietati:

1.Fiecare nod este rosu sau negru

2.Fiecare frunza Nil este neagra

3.Daca un nod este rosu, atunci ambii descendenti sunt negri

4.Pe orice cale între un nod si o frunza descendenta se afla acelasi numar de noduri negre. Un exemplu de arbore rosu-negru avem în figura 11.1 unde nodurile rosii sunt cele umbrite.

fig.11.1.

Lema

Un arbore rosu-negru cu n noduri interne are înaltimea cel mult 2*log(n+ 1).

Consecinta

Operatiile dinamice cautare, minimum, maximum, succesolr, predecesor pot fi implementate pentru arborii rosu-negri în O(lg n).

11.2.Rotatii.

Operatiile de cautare si stergere aplicate unui arbore rosu-negru cu n chei modifica arborele, ceea ce ar putea duce la distrugerea proprietatilor pe care trebuie sa le aiba un arbore rosu-negru. Pentru a restaura aceste proprietati va trebui sa schimbam culoarea anumitor noduri si, deasemenea, sa schimbam structura pointer. Schimbam structura pointer printr-o rotatie, care este o operatie locala într-un arbore de cautare care conserva disciplina cheilor.

In figura 11.2 sunt expuse doua tipuri de rotatii: rotatie_stânga si rotatie_dreapta.

fig. 11.2.

Când facem o rotatie stânga presupunem ca LD(y) Nil. Rotatia_stânga

"pivoteaza" în jurul legaturii dintre x si y, facându-l pe y noua radacina a subarborelui având pe x ca si copil stâng, iar copilul stng al lui y va fi copilul drept al lui x. (a b g, sunt subarbori arbitrari).

Algoritmul pentru rotatie_stânga.

Rotatie_stânga(T ,x)

y=LD(x)

LD(x)=LS(y)

Daca LS(y) Nil atunci

P(LS(y))=x

sdaca

P(y)=P(x)

Daca P(x)=Nil atunci

Rad(T)=y

altfel

Daca x = LS(P(x)) atunci

LS(P(x))=y

altfel

LD(P(x))=y

sdaca

LS(y)=x

P(x)=y

Return

Exercitiul 1.

Algoritmul Rotatie_dreapta este similar. Este momentul sa vedeti daca l-ati înteles pe cel dinainte si sa scrieti algoritmul pentru Rotatie_dreapta.

Ambii algoritmi au complexitatea O(1). În figura 11.3 se vede cum functioneaza Rotatie_stânga:

Fig.11.3

fig.11.3.b

11.3.Inserarea.

Vom folosi algoritmul INS_BIN din capitolul 9. Pentru a insera un nod x în arborele T ca si cum ar fi un arbore binar de cautare oarecare apoi îl vom colora rosu.   Pentru a garanta ca proprietatile rosu-negru sunt pastrate vom 'repara' modificarile aparute în arbore prin recolorarea nodurilor si folosirea rotatiilor. În mare parte algoritmul se ocupa de diferitele cazuri care pot aparea pentru a 'repara' modificarile aparute în arbore.

RN_INSERT(T ,x)

Cheama INS_BIN(T ,x)

Cul(x)=rosu

Atat timp cat x Rad(T) si cul(P(x))=rosu

daca P(x) = LS(P(P(x)) atunci

y= LD(P(P(x))

daca Cul(y)=rosu atunci

Cul(P(x))=negru

Cul(y)=negru

Cul(P(P(x))=rosu

x=P(P(x))

altfel

daca x=LD(P(x)) atunci

x=P(x)

cheama Rotatie_stânga(T,x)

sdaca

Cul(P(x))=negru

Cul(P(P(x)) = ro:u

Cheama Rotatie_dreapta( T ,P(P(x))

Sdaca

(aceleasi instructiuni ca pe ramura de dreapta unde LD si LS au fost schimbate)

Cul(Rad(T))=negru

return

Care dintre proprietatile rosu-negru sunt încalcate dupa primele doua linii ale algoritmului? Proprietatea 1 se pastreaza cu siguranta, la fel si cea de-a doua din moment ce noul nod introdus este rosu si copilul sau este Nil. Proprietatea 4 este satisfacuta pentru ca nodul x înlocuieste un nod negru - Nil si acest nod x este rosu cu copil Nil. Deci singura proprietate care poate fi 'stricata' este cea cu numarul 3  (în cazul în care parintele lui x este rosu). În figura 11.4.a. este dat un exemplu care arata cum este încalcata aceasta proprietate dupa ce un nod x este inserat. La celelalte subpuncte ale figurii sunt prezentati pasii algoritmului care 'repara' aceasta încalcare.

(a)

(b)

(d)

fig. 11.4.

11.4 stergerea.

stergerea unui nod dintr-un arbore rosu-negru este doar un pic mai complicata decât operatia de inserare. Algoritmul RN_Elimin este obtinut din algoritmul ELIMIN_BIN din cap.9 printr-o mica modificare. Vom utiliza o 'sentinela' pentru a reprezenta nodurile Nil. Într-un arbore rou-negru T, 'sentinela' NiI(T) e un nod cu aceeasi structura cu a oricarui nod în arbore. Culoarea sa este neagra, iar restul înregistrarilor (KEY, LS, LD, P) vor avea valori arbitrare. Într-un arbore rosu-negru vom înlocui toate legaturile la Nil cu legaturi la Nil(T). Sensul folosirii 'sentinelei' este de a înlocui un descendent Nil al unui nod x printr-un nod care are ca parinte pe x. Pentru economie de memorie vom folosi o singura 'sentinela' pentru a reprezenta toate nodurile Nil (setând la fiecare folosire a 'sentinelei' legatura de tip parinte catre nodul x la care ne referim). La fel ca la inserare trebuie sa avem grija sa pastram proprietatile rosu-negru ale arborelui. Acest lucru se face cu ajutorul unui algoritm care se apeleaza dupa ce stergerea a fost efectuata. Cazurile care apar la stergerea nodurilor dintr-un arbore rosu-negru sunt prezentate în figura urmatoare : (nodurile umbrite sunt rosii, cele albe sunt cele care pot fi rosii sau negre).

Cazul 1.

Acest caz apare când fratele alaturat al nodului x este rosu.

Cazurile 2, 3, 4.

Aceste cazuri apar când fratele alaturat al nodului x este negru diferentiindu-se între ele dupa culorile copiilor acestui frate.

Întrebari si exercitii la capitolul 11.

Exercitiul 1 este în text la rotatii.

Exercitiul 2.

Pe arborele de la începutul capitolului ilustrati stergerea cheii 30.

Exercitiul 3.

Pe arborele de la începutul capitolului ilustrati adaugarea cheii 13.