curs uaic iasi informatica

8/19/2019 curs uaic iasi informatica

1/32

Arbori de căutare echilibrat, i.

SD 2015/2016

http://find/


2/32

Arbori bicolori (red-black trees )

Symmetric binary B-tree , Rudolf Bayer, 1972.

Echilibrarea este ment, inută cu ajutorul unei colorări a nodurilor.

Arborii ros, u-negru sunt arbori binari de căutare care satisfacurmătoarele proprietăt, i:

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

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

3. dacă un nod este ros, u, atunci fiii săi sunt negri;

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

FII, UAIC () Curs 10 SD 2015/2016 2 / 31

http://find/


3/32

Arbori bicolori - exemplu

20

10

3 15

35

21

30

50

FII, UAIC () Curs 10 SD 2015/2016 3 / 31

http://find/


4/32

Arbori bicolori

Lemă:Orice subarbore al unui arbore bicolor are cel put , in 2

bh(v ) − 1 noduri interne, unde:

v rădăcina subarborelui, bh(v ) numărul de noduri negre aflate pe un drum de la v la un nod

de pe frontieră, excluzându-l pe v ;

Demonstraţie.

La curs.

FII, UAIC () Curs 10 SD 2015/2016 4 / 31

http://find/http://goback/


5/32

Arbori bicolori

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

Demonstraţie.

Conform proprietăt, ii 4,n ≥ 2h/2 − 1 ⇒ h/2 ≤ log2(n + 1) ⇒ h ≤ 2log2(n + 1).

FII, UAIC () Curs 10 SD 2015/2016 5 / 31

http://find/


6/32

Arbori bicolori: operat, ii

Corolar:

ˆ Intr-un arbore bicolor cu n noduri, operat , ia de căutare are complexitateatimp O (log n).

FII, UAIC () Curs 10 SD 2015/2016 6 / 31

http://find/


7/32

Operat, ia de inserare

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

Se colorează noul nod cu ros, u.

Se restaurează proprietăt, ile de arbore bicolor prin recolorare de noduris, i aplicare de rotat, ii simple.

FII, UAIC () Curs 10 SD 2015/2016 7 / 31

http://find/


8/32


9/32

Operat, ia de inserare: restaurarea proprietăt, ii 3

Caz 1: “unchiul” nodului inserat este ros, u →

Se recolorează “părintele” s, i “unchiul” ı̂n negru s, i “bunicul” in ros, u.

Caz 2: “unchiul” nodului inserat este negru s, i nodul inserat este fiuldrept al unui fiu stâng →

Se aplică o rotat, ie simplă la stânga ı̂ntre nodul curent s, i nodulpărinte.

Caz 3: “unchiul” nodului inserat este negru s, i nodul inserat este fiulstâng al unui fiu stâng →

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

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

FII, UAIC () Curs 10 SD 2015/2016 9 / 31

http://find/


10/32

Operat, ia de inserare - Caz 1

FII, UAIC () Curs 10 SD 2015/2016 10 / 31

http://find/


11/32

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

FII, UAIC () Curs 10 SD 2015/2016 11 / 31



12/32

Inserare – exemplu: nodul 12

20

10

3 15

14 17

35

50

FII, UAIC () Curs 10 SD 2015/2016 12 / 31

http://find/


13/32

Inserare – CAZUL 1: recolorare

20

10

3 15

14

12

17

35

50

FII, UAIC () Curs 10 SD 2015/2016 13 / 31

http://find/


14/32

Inserare – CAZUL 2: rotat, ie la stânga

20

10

3 15

14

12

17

35

50

FII, UAIC () Curs 10 SD 2015/2016 14 / 31

http://find/


15/32

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

20

15

10

3 14

12

17

35

50

FII, UAIC () Curs 10 SD 2015/2016 15 / 31

http://find/


16/32

Inserare – Arborele ros, u-negru valid

15

10

3 14

12

20

17 35

50

FII, UAIC () Curs 10 SD 2015/2016 16 / 31

O i d i l i



17/32

Operat, ia de inserare: algoritm

Se consideră că fiecare nod a arborelui este o structură cu următoarelecâmpuri:

cheie : informat, ia utilă a nodului;

culoare : ros, u / negru;

pred : adresa nodului părinte (null pentru rădacină);

stg : adresa fiului stâng;

drp : adresa fiului drept.

FII, UAIC () Curs 10 SD 2015/2016 17 / 31

O i d i l i

http://find/


18/32

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 → drp if (y → culoare == rosu) then

Caz 1else

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

Caz 3else

similar cu ramura ”then”, doar că interschimbăm stg cu drpt → culoare ← negru

end

FII, UAIC () Curs 10 SD 2015/2016 18 / 31

O i d i C 1

http://find/


19/32

Operat, ia de inserare: Caz 1

x → pred → culoare ← negruy → culoare ← negru

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

FII, UAIC () Curs 10 SD 2015/2016 19 / 31

O ti d i C 2

http://find/


20/32


x ← x → pred

rotatie-stânga(t , x )

FII, UAIC () Curs 10 SD 2015/2016 20 / 31

O ti d i C 3



21/32


x → pred → culoare ← negru

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

FII, UAIC () Curs 10 SD 2015/2016 21 / 31

Operatia de inserare exemplul 2

http://find/


22/32

Operat, ia de inserare - exemplul 2

FII, UAIC () Curs 10 SD 2015/2016 22 / 31


http://find/


23/32


FII, UAIC () Curs 10 SD 2015/2016 23 / 31


http://find/


24/32


FII, UAIC () Curs 10 SD 2015/2016 24 / 31

Operatia de stergere

http://find/


25/32

Operat, ia de s, tergere

Similară cu operat, ia de s, tergere de la arborii binari de căutareobis, nuit, i.

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

În urma s, tergerii este posibil ca proprietatea 4 să nu mai fierespectată.

Se restaurează proprietăt, ile de arbore bicolor prin recolorare de noduris, i aplicare de rotat, ii simple.

FII, UAIC () Curs 10 SD 2015/2016 25 / 31

Operatia de stergere: restaurarea proprietătii 4

http://find/


26/32

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

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

Caz 2: Nodul pentru care nu este satisfăcută proprietatea estedeplasat spre rădăcină cu un nivel prin recolorarea unui nod.

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

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

FII, UAIC () Curs 10 SD 2015/2016 26 / 31

Stergere – CAZUL 1



27/32

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

→

y

v

u

A B

x

C D

z

E F

FII, UAIC () Curs 10 SD 2015/2016 27 / 31




28/32

S, tergere CAZUL 2

Caz 2: Nodul pentru care nu este satisfăcută proprietatea este deplasatspre rădăcină cu un nivel prin recolorarea unui nod.

v

u

A B

y

x

C D

z

E F

→

v

u

A B

y

x

C D

z

E F

FII, UAIC () Curs 10 SD 2015/2016 28 / 31


http://goforward/http://find/http://goback/


29/32

S, tergere CAZUL 3

Caz 3: Se transformă ı̂n cazul 4) printr-o interschimbare de culori s, i o

rotat, ie.

v

u

A B

y

x

C D

z

E F

→

v

uA B

x

C y

D z

E F

FII, UAIC () Curs 10 SD 2015/2016 29 / 31




30/32

S, tergere CAZUL 4

Caz 4: În acest caz se restabiles, te proprietatea de arbore bicolor pentru

ı̂ntreg arborele.

v

u

A B

y

x

C D

z

E F

→

y

v

u

A B

x

C D

z

E F

FII, UAIC () Curs 10 SD 2015/2016 30 / 31

Arbori bicolori

http://goforward/http://find/http://goback/


31/32

Arbori bicolori

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

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

FII, UAIC () Curs 10 SD 2015/2016 31 / 31

Arbori bicolori

http://find/


32/32

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

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

Utilizări: System symbol tables.

Kernel Linux (Completely Fair Scheduler).

FII, UAIC () Curs 10 SD 2015/2016 31 / 31
http://find/

Date post:	08-Jul-2018
Category:	Documents
Upload:	jan-holdbach
View:	230 times
Download:	2 times

curs uaic iasi informatica

Documents