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.
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
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(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.
|
