arbori rosu negru iz

8/19/2019 Arbori Rosu Negru Iz

1/55

Arbori Rosu -Negru


2/55

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 fiuldrept


3/55

• Daca fiul sau tatal unui nod nu eista,

campul pointer corespun!ator din nod are

valuarea Nil

• "om considera ca aceste valori Nil sunt

pointeri la noduri #frun!e$ eterne ale

arborelui binar, iar restul nodurilor le vom

considera noduri interne ale arborelui


4/55

Proprietati

• %rice nod este rosu sau negru

• Radacina este negra

• &iecare frun!a#Nil$ este negra• Daca un nod este rosu, atunci ambi fii ai

sai sunt negri

• 'entru orice nod, toate drumurile de lanod la frun!ele descendente contine

acelasi numar de noduri negre


5/55

Eemplu de Arbore Rosu -Negru


6/55

De ce sa folosim Arborele

Rosu ( Negru ?

• Asa cum stim la Arbori )inari de Cautare

urmatoarele operatii se reali!ea!a in

%#inaltimea arborelui$:

* Cautarea

* 'redecesor, +uccesor

* Aflarea aimului, inimului * nserarea

* +tergere


7/55

• naltimea in Arborele )inar de Cautare

este cuprinsa intre N #numarul de noduri$

si lgN# la arborele complet$

• Ca!urile in care inaltimea este lgN sunt

destul de i!olate

• n arborele Rosu-Negru inaltimea este

maim . lg#N/0$ astfel ca toate operatiile

mai sus mentionate sunt mult mai rapide


8/55

&unctii identice cu Arborele )inar

* Cautare

* inim, aim

* +uccesor, 'redecesor • 1oate aceste functii sunt identice cu cele

de la Arbori )inari de Cautare, mai mult

pentru ca inaltimea Arborelui Rosu-Negru este %#lgN$, compleitatea lor va fi %#lgN$


9/55

nserarea

• ntr-un Arbore Rosu-Negru cu N noduri,

nserarea se reali!ea!a intr-un timp %#lgN$

• &unctia nserea!a de la Arborele )inar de

Cautare nu ne grantea!a pastrarea

proprietatiilor arborelui Rosu-Negru

• "om pastra proprietatiile prin rotatii si

recolorari


10/55

'ornim de la arborele


11/55

• &olosim procedura de inserare in Arborele

)inar de Cautare, culoarea noului nod va

fi rosie• n 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 ca! asemanator cu cel ce

urmea!a


12/55

Nodul ! este nodul introdus in

arbore


13/55

• Daca unchiul stanga al nodului nostru este

rosu atunci vom face modificarileurmatoare :

* tatal si unchiul se vor colora negru

* bunicul se va colora cu rosu * nodul 2va urca3 in bunic


14/55


15/55

• Daca tatal nodului este tot rosu, unchiul

stang este negru si este fiul drept al

tatalui atunci vom face urmatoarele

modificari :

* rotim la stanga nodul


16/55


17/55

• Daca tatal nodului este tot rosu, unchiul

stang este negru si 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


18/55


19/55


20/55

+tergerea

• ntr-un Arbore Rosu-Negru cu N noduri,

+tergerea se reali!ea!a intr-un timp

%#lgN$

• &unctia de +tergere de la Arborele )inar

de Cautare nu ne grantea!a pastrarea

proprietatiilor arborelui Rosu-Negru

• "om pastra proprietatiile prin rotatii si

recolorari


21/55

Ce este o santinela?

• +antinela este un obiect cu aceleasi

campuri ca si un nod, cu culoarea neagra

• 1oti pointerii la Nil din arbore vor fi inlocuiti

cu pointeri catre santinela

• "om folosi o singura santinela, astfel cand

dorim sa manipulam un fiu al unui nod ,

vom seta in prealabil parinte4Nil41556


22/55

Eemplu de santinela


23/55

+tergerea unui nod din arbore

• &olosim procedura de +tergere de la

Arborele )inar de Cautare cu preci!arile:

* referintele la Nil au fost inlocuite cu

referinte la Nil415

* atribuirea p45 7- p485 se va face

neconditionata

* apelarea functiei R)-DE9E1E-&;'#T ,

x $


24/55

%bservatii

• Nodul transmis procedurii este unicul fiual lui 8 #nodul sters$ daca


25/55


26/55


27/55


28/55

+tergerea unei frun!e rosi


29/55


30/55

• Daca nodul sters este negru, se

micsorea!a cu 0 numarul de noduri negre

de pe fiecare drum care a continut acel

nod

• "om trata ca!ul in care este fiul stang al

tatalui lui


31/55

Ca!ul 0


32/55


33/55


34/55

Ca!ul 0

• Apare atunci cand =, fratele lui # fiind fiulnodului succesor in preordine$ este coloratcu rosu

• > trebuie sa aibe fii negri• "om interschimba culorile lui = si p45

• "om roti la stanga lui p45

• Noul frate al lui , unul din fii lui = va ficlorat cu negru

• Ca!ul 0 6 Ca!ul ., @ sau


35/55

Ca!ul 0


36/55

Arborele dupa echilibrare


37/55

Ca!ul .


38/55

Ca!ul .

• Apare atunci cand = este colorat cu negrusi fii lui sunt colorati cu negru

• "a trebui sa 2scoatem un negru3 de la = si

de la • va ramane cu un singur negru

• > va deveni rosu

• se va duce in parintele lui• Culoarea lui se va face neagra si se

repteta ciclul daca e nevoie


39/55

Ca!ul .


40/55


41/55

Ca!ul @


42/55


43/55


44/55

Ca!ul @

• Apare cand = este colorat cu negru, fiul luistang este rosu si fiul drept este negru

• nterschimbam culorile lui = si ale fiului sau

stang• Efectuam o rotatie la dreapta in =

• Noul frate = a lui este acum un nod negru

care are fiul drept colorat cu rosu• va trece in parintele lui

• Am transformat ca!ul @ in ca!ul @ sau


45/55

Ca!ul @


46/55


47/55

Ca!ul


48/55


49/55


50/55

Ca!ul

• Apare atunci cand = este negru si fiul drept al lui

este rosu

• Culoarea lui = va deveni culoarea bunicului lui

• Culoarea bunicului va deveni neagra• Culoarea fiului lui drept al lui = va deveni neagra

• +e roteste la stanga tatal lui

• va deveni radacina arborelui care va primiculoarea neagra


51/55

Ca!ul


52/55

Arborele dupa ca!ul


53/55

• 'rocedura de 2reparare3 ( Ca!urile 0,.,@ si

se repeta cat timp nodul are culoareaneagra si nu este radacina arborelui

• De observat:

*Ca!ul 0 6 Ca!ul .,@ sau

*Ca!ul . 6 +e repeta ciclul sau se iesedin functie#arborele s-a echilibrat$

*Ca!ul @ 6 Ca!ul @ sau

* Ca!ul 6 +e repeta ciclul sau se iesedin functie#arborele s-a echilibrat$


54/55

Aplicatii

• n aplicatii in care timpul de raspuns

trebuie sa fie mic

• +unt stucturi de date folosite in geometrie

computationala

C ti A b i R N


55/55

Comparatie Arbori Rosu- Negru

A"9• A"9 au aparut in 0B. fiind primi arbori echilibrati

• Arborii Rosu- Negru au aparut in 0B. pornind de la )-arbori

• Au structuri asemanatoare din punct de vedere

matematic• Arbori Rosu-Negru au inaltimea maima .log.#n / 0$, pe

cand A"9 au inaltimea maima 0, log.#n/.$-0

• 9a arborii Rosu-Negru inserarea si stergerea se fac mult

mai rapid, in A"9 uneori este nevoie de 9ogN reechilibrari

• 1otusi recuperarea informatiilor se face mai rapid in A"9

arbori rosu negru iz

Documents