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