Arbori Rosu -Negru

55
Arbori Rosu -Negru

Transcript of Arbori Rosu -Negru

Page 1: Arbori Rosu -Negru

Arbori Rosu -Negru

Page 2: 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

Page 3: Arbori Rosu -Negru

• 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

Page 4: Arbori Rosu -Negru

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

Page 5: Arbori Rosu -Negru

Exemplu de Arbore Rosu -Negru

Page 6: Arbori 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

Page 7: Arbori Rosu -Negru

• 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

Page 8: Arbori Rosu -Negru

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)

Page 9: Arbori Rosu -Negru

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

Page 10: Arbori Rosu -Negru

Pornim de la arborele

Page 11: Arbori Rosu -Negru

• 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

Page 12: Arbori Rosu -Negru

Nodul z este nodul introdus in arbore

Page 13: Arbori Rosu -Negru

• 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

Page 14: Arbori Rosu -Negru
Page 15: Arbori Rosu -Negru

• 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

Page 16: Arbori Rosu -Negru
Page 17: Arbori Rosu -Negru

• 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

Page 18: Arbori Rosu -Negru

• 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

Page 19: Arbori Rosu -Negru
Page 20: Arbori Rosu -Negru

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

Page 21: Arbori Rosu -Negru

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

Page 22: Arbori Rosu -Negru

Exemplu de santinela

Page 23: Arbori Rosu -Negru

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)

Page 24: Arbori Rosu -Negru

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

Page 25: Arbori Rosu -Negru

Stergerea unui nod rosu(care nu este frunza)

Page 26: Arbori Rosu -Negru
Page 27: Arbori Rosu -Negru
Page 28: Arbori Rosu -Negru

Stergerea unei frunze rosi

Page 29: Arbori Rosu -Negru
Page 30: Arbori Rosu -Negru

• 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

Page 31: Arbori Rosu -Negru

Cazul 1

Page 32: Arbori Rosu -Negru
Page 33: Arbori Rosu -Negru
Page 34: Arbori Rosu -Negru

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

Page 35: Arbori Rosu -Negru

Cazul 1

Page 36: Arbori Rosu -Negru

Arborele dupa echilibrare

Page 37: Arbori Rosu -Negru

Cazul 2

Page 38: Arbori Rosu -Negru

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

Page 39: Arbori Rosu -Negru

Cazul 2

Page 40: Arbori Rosu -Negru
Page 41: Arbori Rosu -Negru

Cazul 3

Page 42: Arbori Rosu -Negru
Page 43: Arbori Rosu -Negru
Page 44: Arbori Rosu -Negru

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

Page 45: Arbori Rosu -Negru

Cazul 3

Page 46: Arbori Rosu -Negru
Page 47: Arbori Rosu -Negru

Cazul 4

Page 48: Arbori Rosu -Negru
Page 49: Arbori Rosu -Negru
Page 50: Arbori Rosu -Negru

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

Page 51: Arbori Rosu -Negru

Cazul 4

Page 52: Arbori Rosu -Negru

Arborele dupa cazul 4

Page 53: Arbori Rosu -Negru

• 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)

Page 54: Arbori Rosu -Negru

Aplicatii

• In aplicatii in care timpul de raspuns trebuie sa fie mic

• Sunt stucturi de date folosite in geometrie computationala

Page 55: Arbori Rosu -Negru

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