Arbori de cautare echilibrat, i.

SD 2019/2020

Arbori bicolori (red-black trees)

I Symmetric binary B-tree, Rudolf Bayer, 1972.

I Echilibrarea este ment, inuta cu ajutorul unei colorari a nodurilor.

I Arborii ros,u-negru sunt arbori binari de cautare care satisfacurmatoarele proprietat, i:

1. un nod este colorat cu ros,u sau negru;

2. radacina s, i nodurile frunza (nil – care fac parte din structura) suntcolorate cu negru;

3. daca un nod este ros,u, atunci fiii sai sunt negri;

4. drumurile de la un nod la nodurile de pe frontiera au acelas, i numar denoduri negre.

FII, UAIC Curs 10 SD 2019/2020 2 / 31

Arbori bicolori - exemplu

20

10

3 15

35

21

30

50

FII, UAIC Curs 10 SD 2019/2020 3 / 31

Arbori bicolori

Lema:Orice subarbore al unui arbore bicolor are cel put, in 2bh(v) − 1 noduriinterne, unde:

I v radacina subarborelui,

I bh(v) numarul de noduri negre aflate pe un drum de la v la un nodde pe frontiera, excluzandu-l pe v ;

Demonstratie.

La curs.

FII, UAIC Curs 10 SD 2019/2020 4 / 31

Arbori bicolori

Teorema:Un arbore bicolor cu n noduri interne are ınalt, imea h ≤ 2 log2(n + 1).

Demonstratie.

Conform proprietat, ii 3,n ≥ 2h/2 − 1 ⇒ h/2 ≤ log2(n + 1) ⇒ h ≤ 2 log2(n + 1).

FII, UAIC Curs 10 SD 2019/2020 5 / 31

Arbori bicolori: operat, ii

Corolar:Intr-un arbore bicolor cu n noduri, operat, ia de cautare are complexitateatimp O(log n).

FII, UAIC Curs 10 SD 2019/2020 6 / 31

Operat, ia de inserare

I Se cauta pozit, ia de inserare s, i se insereaza noua valoare ca ın cazularborilor binari de cautare obis,nuit, i.

I Se coloreaza noul nod cu ros,u.

I Se restaureaza proprietat, ile de arbore bicolor prin recolorare de noduris, i aplicare de rotat, ii simple.

FII, UAIC Curs 10 SD 2019/2020 7 / 31

Operat, ia de inserare

I Proprietatea 1: satisfacuta.

I Proprietatea 2 – satisfacuta (ambii fii ai nodului inserat sunt nil).Daca nodul inserat este radacina → recolorare ın negru.

I Proprietatea 4 – satisfacuta (noul nod ros,u ınlocuies, te o frunza).

I Poate sa nu fie respectata proprietatea 3 - daca parintele nodului esteros,u.

I Muta mai sus aceasta situat, ie prin recolorarea nodurilor pana candpoate fi reparata prin operat, ii de rotat, ie s, i recolorare.

FII, UAIC Curs 10 SD 2019/2020 8 / 31

Operat, ia de inserare: restaurarea proprietat, ii 3

I Caz 1: “unchiul” nodului inserat este ros,u →Se recoloreaza “parintele” s, i “unchiul” ın negru s, i “bunicul” in ros,u.

I Caz 2: “unchiul” nodului inserat este negru s, i nodul inserat este fiuldrept al unui fiu stang →

Se aplica o rotat, ie simpla la stanga ıntre nodul curent s, i nodulparinte.

I Caz 3: “unchiul” nodului inserat este negru s, i nodul inserat este fiulstang al unui fiu stang →

Se aplica o rotat, ie simpla la dreapta ıntre nodul “parinte” s, i nodul“bunic” + se recoloreaza nodurile “parinte” (ın negru) s, i “bunic” (ınros,u).

Obs.: Operat, ii similare se aplica pentru cazul simetric.

FII, UAIC Curs 10 SD 2019/2020 9 / 31

Operat, ia de inserare - Caz 1

FII, UAIC Curs 10 SD 2019/2020 10 / 31

Operat, ia de inserare - Caz 2 s, i 3

FII, UAIC Curs 10 SD 2019/2020 11 / 31

Inserare – exemplu: nodul 12

20

10

3 15

14 17

35

50

FII, UAIC Curs 10 SD 2019/2020 12 / 31

Inserare – CAZUL 1: recolorare

20

10

3 15

14

12

17

35

50

FII, UAIC Curs 10 SD 2019/2020 13 / 31

Inserare – CAZUL 2: rotat, ie la stanga

20

10

3 15

14

12

17

35

50

FII, UAIC Curs 10 SD 2019/2020 14 / 31

Inserare – CAZUL 3: rotat, ie la dreapta + recolorare

20

15

10

3 14

12

17

35

50

FII, UAIC Curs 10 SD 2019/2020 15 / 31

Inserare – Arborele ros,u-negru valid

15

10

3 14

12

20

17 35

50

FII, UAIC Curs 10 SD 2019/2020 16 / 31

Operat, ia de inserare: algoritm

Se considera ca fiecare nod a arborelui este o structura cu urmatoarelecampuri:

I cheie: informat, ia utila a nodului;

I culoare: ros,u / negru;

I pred: adresa nodului parinte (null pentru radacina);

I stg: adresa fiului stang;

I drp: adresa fiului drept.

FII, UAIC Curs 10 SD 2019/2020 17 / 31

Operat, ia de inserare: algoritm

Procedure inserare(t, x)begin

insArbBinCautare(t, x)x → culoare ← rosuwhile (x! = t and x → pred → culoare == rosu) do

if (x → pred == x → pred → pred → stg) theny ← x → pred → pred → drpif (y → culoare == rosu) then

Caz 1else

if (x == x → pred → drp) thenCaz 2

Caz 3else

similar cu ramura ”then”, doar ca interschimbam stg cu drpt → culoare ← negru

end

FII, UAIC Curs 10 SD 2019/2020 18 / 31

Operat, ia de inserare: Caz 1

x → pred → culoare ← negruy → culoare ← negrux → pred → pred → culoare ← ros,ux ← x → pred → pred

FII, UAIC Curs 10 SD 2019/2020 19 / 31

Operat, ia de inserare: Caz 2

x ← x → predrotatie-stanga(t, x)

FII, UAIC Curs 10 SD 2019/2020 20 / 31

Operat, ia de inserare: Caz 3

x → pred → culoare ← negrux → pred → pred → culoare ← ros,urotatie-dreapta(t, x → pred → pred)

FII, UAIC Curs 10 SD 2019/2020 21 / 31

Operat, ia de inserare - exemplul 2

FII, UAIC Curs 10 SD 2019/2020 22 / 31

Operat, ia de inserare - exemplul 3

FII, UAIC Curs 10 SD 2019/2020 23 / 31

Operat, ia de inserare - exemplul 3

FII, UAIC Curs 10 SD 2019/2020 24 / 31

Operat, ia de s, tergere

I Similara cu operat, ia de s, tergere de la arborii binari de cautareobis,nuit, i.

I Se va t, ine cont ca nodurile “null” fac parte din structura.

I In urma s, tergerii este posibil ca proprietatea 4 sa nu mai fierespectata.

I Se restaureaza proprietat, ile de arbore bicolor prin recolorare de noduris, i aplicare de rotat, ii simple.

FII, UAIC Curs 10 SD 2019/2020 25 / 31

Operat, ia de s, tergere: restaurarea proprietat, ii 4

I Caz 1: Se transforma ıntr-unul din cazurile 2), 3), 4) printr-o rotat, ie.

I Caz 2: Nodul pentru care nu este satisfacuta proprietatea estedeplasat spre radacina cu un nivel prin recolorarea unui nod.

I Caz 3: Se transforma ın cazul 4) printr-o interschimbare de culori s, i orotat, ie.

I Caz 4: In acest caz se restabiles, te proprietatea de arbore bicolorpentru ıntreg arborele.

FII, UAIC Curs 10 SD 2019/2020 26 / 31

S, tergere – CAZUL 1

Caz 1: Se transforma ıntr-unul din cazurile 2), 3), 4) printr-o rotat, ie.

v

u

A B

y

x

C D

z

E F

7→

y

v

u

A B

x

C D

z

E F

FII, UAIC Curs 10 SD 2019/2020 27 / 31

S, tergere – CAZUL 2

Caz 2: Nodul pentru care nu este satisfacuta proprietatea este deplasatspre radacina cu un nivel prin recolorarea unui nod.

v

u

A B

y

x

C D

z

E F

7→

v

u

A B

y

x

C D

z

E F

FII, UAIC Curs 10 SD 2019/2020 28 / 31

S, tergere – CAZUL 3

Caz 3: Se transforma ın cazul 4) printr-o interschimbare de culori s, i orotat, ie.

v

u

A B

y

x

C D

z

E F

7→

v

u

A B

x

C y

D z

E F

FII, UAIC Curs 10 SD 2019/2020 29 / 31

S, tergere – CAZUL 4Caz 4:

In acest caz se restabiles, te proprietatea de arbore bicolor pentru ıntregarborele.

v

u

A B

y

x

C D

z

E F

7→

y

v

u

A B

x

C D

z

E F

FII, UAIC Curs 10 SD 2019/2020 30 / 31

Arbori bicolori

I Complexitatea algoritmilor de inserare / s, tergere: O(log n).

Corolar:Clasa arborilor bicolori este O(log n)–stabila.

I Utilizari:I System symbol tables

I Kernel Linux (Completely Fair Scheduler)

I Runway reservation system

I Java: TreeMap, TreeSet; C++ STL: map, multimap, multiset

FII, UAIC Curs 10 SD 2019/2020 31 / 31

Arbori bicolori

I Complexitatea algoritmilor de inserare / s, tergere: O(log n).

Corolar:Clasa arborilor bicolori este O(log n)–stabila.

I Utilizari:I System symbol tables

I Kernel Linux (Completely Fair Scheduler)

I Runway reservation system

I Java: TreeMap, TreeSet; C++ STL: map, multimap, multiset

FII, UAIC Curs 10 SD 2019/2020 31 / 31