8/19/2019 Arbori Rosu Negru Iz
1/55
Arbori Rosu -Negru
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
5/55
Eemplu de Arbore Rosu -Negru
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
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/19/2019 Arbori Rosu Negru Iz
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$
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
10/55
'ornim de la arborele
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
12/55
Nodul ! este nodul introdus in
arbore
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
14/55
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
16/55
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
18/55
8/19/2019 Arbori Rosu Negru Iz
19/55
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
22/55
Eemplu de santinela
8/19/2019 Arbori Rosu Negru Iz
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 $
8/19/2019 Arbori Rosu Negru Iz
24/55
%bservatii
• Nodul transmis procedurii este unicul fiual lui 8 #nodul sters$ daca
8/19/2019 Arbori Rosu Negru Iz
25/55
8/19/2019 Arbori Rosu Negru Iz
26/55
8/19/2019 Arbori Rosu Negru Iz
27/55
8/19/2019 Arbori Rosu Negru Iz
28/55
+tergerea unei frun!e rosi
8/19/2019 Arbori Rosu Negru Iz
29/55
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
31/55
Ca!ul 0
8/19/2019 Arbori Rosu Negru Iz
32/55
8/19/2019 Arbori Rosu Negru Iz
33/55
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
35/55
Ca!ul 0
8/19/2019 Arbori Rosu Negru Iz
36/55
Arborele dupa echilibrare
8/19/2019 Arbori Rosu Negru Iz
37/55
Ca!ul .
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
39/55
Ca!ul .
8/19/2019 Arbori Rosu Negru Iz
40/55
8/19/2019 Arbori Rosu Negru Iz
41/55
Ca!ul @
8/19/2019 Arbori Rosu Negru Iz
42/55
8/19/2019 Arbori Rosu Negru Iz
43/55
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
45/55
Ca!ul @
8/19/2019 Arbori Rosu Negru Iz
46/55
8/19/2019 Arbori Rosu Negru Iz
47/55
Ca!ul
8/19/2019 Arbori Rosu Negru Iz
48/55
8/19/2019 Arbori Rosu Negru Iz
49/55
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
51/55
Ca!ul
8/19/2019 Arbori Rosu Negru Iz
52/55
Arborele dupa ca!ul
8/19/2019 Arbori Rosu Negru Iz
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$
8/19/2019 Arbori Rosu Negru Iz
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
8/19/2019 Arbori Rosu Negru Iz
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