Post on 29-Jun-2015
transcript
Arbori Rosu -Negru
Ce este un Arbore Rosu -Negru ?
• Este un arbore binar de cautare ale carui noduri au un bit suplimentar ce contine culoarea : fie neagra, fie rosie
• Astfel fiecare nod va contine : campul culoare, campul cheie, pointer catre tata, pointer catre fiul stang si pointer catre fiul drept
• Daca fiul sau tatal unui nod nu exista, campul pointer corespunzator din nod are valuarea Nil
• Vom considera ca aceste valori Nil sunt pointeri la noduri (frunze) externe ale arborelui binar, iar restul nodurilor le vom considera noduri interne ale arborelui
Proprietati
• Orice nod este rosu sau negru
• Radacina este negra
• Fiecare frunza(Nil) este negra
• Daca un nod este rosu, atunci ambi fii ai sai sunt negri
• Pentru orice nod, toate drumurile de la nod la frunzele descendente contine acelasi numar de noduri negre
Exemplu de Arbore Rosu -Negru
De ce sa folosim Arborele Rosu – Negru ?
• Asa cum stim la Arbori Binari de Cautare urmatoarele operatii se realizeaza in O(inaltimea arborelui):
* Cautarea
* Predecesor, Succesor
* Aflarea Maximului, Minimului
* Inserarea
* Stergere
• Inaltimea in Arborele Binar de Cautare este cuprinsa intre N (numarul de noduri) si lgN( la arborele complet)
• Cazurile in care inaltimea este lgN sunt destul de izolate
• In arborele Rosu-Negru inaltimea este maxim 2 lg(N+1) astfel ca toate operatiile mai sus mentionate sunt mult mai rapide
Functii identice cu Arborele Binar
* Cautare
* Minim, Maxim
* Succesor, Predecesor
• Toate aceste functii sunt identice cu cele de la Arbori Binari de Cautare, mai mult pentru ca inaltimea Arborelui Rosu-Negru
este O(lgN), complexitatea lor va fi O(lgN)
Inserarea
• Intr-un Arbore Rosu-Negru cu N noduri, Inserarea se realizeaza intr-un timp O(lgN)
• Functia Insereaza de la Arborele Binar de Cautare nu ne granteaza pastrarea proprietatiilor arborelui Rosu-Negru
• Vom pastra proprietatiile prin rotatii si recolorari
Pornim de la arborele
• Folosim procedura de inserare in Arborele Binar de Cautare, culoarea noului nod va fi rosie
• In momentul inserarii singura proprietate care poate fi incalcata este cea care ne spune ca un nod rosu are ambi fii negri
• Daca tatal nostru este de culoare rosie vom avea un caz asemanator cu cel ce urmeaza
Nodul z este nodul introdus in arbore
• Daca unchiul stanga al nodului nostru este rosu atunci vom face modificarile urmatoare :
* tatal si unchiul se vor colora negru
* bunicul se va colora cu rosu
* nodul “va urca” in bunic
• Daca tatal nodului este tot rosu, unchiul stang este negru si x este fiul drept al tatalui atunci vom face urmatoarele modificari :
* rotim la stanga nodul
• Daca tatal nodului este tot rosu, unchiul stang este negru si x este fiu stang al tatalui atunci vom face urmatoarele modificari :
* rotim la dreapta nodul
* tatal nodului il vom colora cu negru
* bunicul nodului il vom colora cu rosu
• Daca parintele si nodul au tot culoarea rosie se repeta operatiile
• Daca nodul este inserat ca fiu drept, operatiile sunt simetrice( vom schimba stanga cu dreapta)
• In cazul nostru nu mai e nevoie de modificari
Stergerea
• Intr-un Arbore Rosu-Negru cu N noduri, Stergerea se realizeaza intr-un timp O(lgN)
• Functia de Stergere de la Arborele Binar de Cautare nu ne granteaza pastrarea proprietatiilor arborelui Rosu-Negru
• Vom pastra proprietatiile prin rotatii si recolorari
Ce este o santinela?
• Santinela este un obiect cu aceleasi campuri ca si un nod, cu culoarea neagra
• Toti pointerii la Nil din arbore vor fi inlocuiti cu pointeri catre santinela
• Vom folosi o singura santinela, astfel cand dorim sa manipulam un fiu al unui nod x, vom seta in prealabil parinte[Nil[T]]=x
Exemplu de santinela
Stergerea unui nod din arbore
• Folosim procedura de Stergere de la Arborele Binar de Cautare cu precizarile:
* referintele la Nil au fost inlocuite cu referinte la Nil[T]
* atribuirea p[x] <- p[y] se va face neconditionata
* apelarea functiei RB-DELETE-FIXUP(T, x)
Observatii
• Nodul x transmis procedurii este unicul fiu al lui y (nodul sters) daca x!=Nil, sau santinela daca y nu a avut fii
• Daca nodul sters a fost rosu proprietatiile sunt conservate
Stergerea unui nod rosu(care nu este frunza)
Stergerea unei frunze rosi
• Daca nodul sters este negru, se micsoreaza cu 1 numarul de noduri negre de pe fiecare drum care a continut acel nod
• Vom trata cazul in care x este fiul stang al tatalui lui
Cazul 1
Cazul 1
• Apare atunci cand w, fratele lui x (x fiind fiul nodului succesor in preordine) este colorat cu rosu
• W trebuie sa aibe fii negri• Vom interschimba culorile lui w si p[x]• Vom roti la stanga lui p[x]• Noul frate al lui x, unul din fii lui w va fi
clorat cu negru• Cazul 1 => Cazul 2, 3 sau 4
Cazul 1
Arborele dupa echilibrare
Cazul 2
Cazul 2
• Apare atunci cand w este colorat cu negru si fii lui sunt colorati cu negru
• Va trebui sa “scoatem un negru” de la w si de la x
• X va ramane cu un singur negru• W va deveni rosu• X se va duce in parintele lui• Culoarea lui x se va face neagra si se
repteta ciclul daca e nevoie
Cazul 2
Cazul 3
Cazul 3
• Apare cand w este colorat cu negru, fiul lui stang este rosu si fiul drept este negru
• Interschimbam culorile lui w si ale fiului sau stang
• Efectuam o rotatie la dreapta in w• Noul frate w a lui x este acum un nod
negru care are fiul drept colorat cu rosu • X va trece in parintele lui• Am transformat cazul 3 in cazul 3 sau 4
Cazul 3
Cazul 4
Cazul 4
• Apare atunci cand w este negru si fiul drept al lui este rosu
• Culoarea lui w va deveni culoarea bunicului lui• Culoarea bunicului va deveni neagra• Culoarea fiului lui drept al lui w va deveni neagra• Se roteste la stanga tatal lui x• X va deveni radacina arborelui care va primi
culoarea neagra
Cazul 4
Arborele dupa cazul 4
• Procedura de “reparare” – Cazurile 1,2,3 si 4 se repeta cat timp nodul x are culoarea neagra si nu este radacina arborelui
• De observat: *Cazul 1 => Cazul 2,3 sau 4 *Cazul 2 => Se repeta ciclul sau se iese
din functie(arborele s-a echilibrat) *Cazul 3 => Cazul 3 sau 4 * Cazul 4 => Se repeta ciclul sau se iese
din functie(arborele s-a echilibrat)
Aplicatii
• In aplicatii in care timpul de raspuns trebuie sa fie mic
• Sunt stucturi de date folosite in geometrie computationala
Comparatie Arbori Rosu- Negru AVL
• AVL au aparut in 1962 fiind primi arbori echilibrati• Arborii Rosu- Negru au aparut in 1972 pornind de la B-
arbori• Au structuri asemanatoare din punct de vedere
matematic• Arbori Rosu-Negru au inaltimea maxima 2log2(n + 1), pe
cand AVL au inaltimea maxima 1,44 log2(n+2)-1• La arborii Rosu-Negru inserarea si stergerea se fac mult
mai rapid, in AVL uneori este nevoie de LogN reechilibrari• Totusi recuperarea informatiilor se face mai rapid in AVL