8/19/2019 curs uaic iasi informatica
1/32
Arbori de căutare echilibrat, i.
SD 2015/2016
http://find/
8/19/2019 curs uaic iasi informatica
2/32
Arbori bicolori (red-black trees )
Symmetric binary B-tree , Rudolf Bayer, 1972.
Echilibrarea este ment, inută cu ajutorul unei colorări a nodurilor.
Arborii ros, u-negru sunt arbori binari de căutare care satisfacurmătoarele proprietăt, i:
1. un nod este colorat cu ros, u sau negru;
2. rădăcina s, i nodurile frunză (nil – care fac parte din structură) suntcolorate cu negru;
3. dacă un nod este ros, u, atunci fiii săi sunt negri;
4. drumurile de la un nod la nodurile de pe frontieră au acelas, i număr denoduri negre.
FII, UAIC () Curs 10 SD 2015/2016 2 / 31
http://find/
8/19/2019 curs uaic iasi informatica
3/32
Arbori bicolori - exemplu
20
10
3 15
35
21
30
50
FII, UAIC () Curs 10 SD 2015/2016 3 / 31
http://find/
8/19/2019 curs uaic iasi informatica
4/32
Arbori bicolori
Lemă:Orice subarbore al unui arbore bicolor are cel put , in 2
bh(v ) − 1 noduri interne, unde:
v rădăcina subarborelui, bh(v ) numărul de noduri negre aflate pe un drum de la v la un nod
de pe frontieră, excluzându-l pe v ;
Demonstraţie.
La curs.
FII, UAIC () Curs 10 SD 2015/2016 4 / 31
http://find/http://goback/
8/19/2019 curs uaic iasi informatica
5/32
Arbori bicolori
Teoremă:Un arbore bicolor cu n noduri interne are ı̂nălt , imea h ≤ 2log2(n + 1).
Demonstraţie.
Conform proprietă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/
8/19/2019 curs uaic iasi informatica
6/32
Arbori bicolori: operat, ii
Corolar:
ˆ Intr-un arbore bicolor cu n noduri, operat , ia de căutare are complexitateatimp O (log n).
FII, UAIC () Curs 10 SD 2015/2016 6 / 31
http://find/
8/19/2019 curs uaic iasi informatica
7/32
Operat, ia de inserare
Se caută pozit, ia de inserare s, i se inserează noua valoare ca ı̂n cazularborilor binari de căutare obis, nuit, i.
Se colorează noul nod cu ros, u.
Se restaurează proprietă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/19/2019 curs uaic iasi informatica
8/32
8/19/2019 curs uaic iasi informatica
9/32
Operat, ia de inserare: restaurarea proprietăt, ii 3
Caz 1: “unchiul” nodului inserat este ros, u →
Se recolorează “pă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 stâng →
Se aplică o rotat, ie simplă la stânga ı̂ntre nodul curent s, i nodulpărinte.
Caz 3: “unchiul” nodului inserat este negru s, i nodul inserat este fiulstâng al unui fiu stâng →
Se aplică o rotat, ie simplă la dreapta ı̂ntre nodul “părinte” s, i nodul“bunic” + se recolorează nodurile “părinte” (̂ın negru) s, i “bunic” (̂ınros, u).
Obs.: Operat, ii similare se aplică pentru cazul simetric.
FII, UAIC () Curs 10 SD 2015/2016 9 / 31
http://find/
8/19/2019 curs uaic iasi informatica
10/32
Operat, ia de inserare - Caz 1
FII, UAIC () Curs 10 SD 2015/2016 10 / 31
http://find/
8/19/2019 curs uaic iasi informatica
11/32
Operat, ia de inserare - Caz 2 s, i 3
FII, UAIC () Curs 10 SD 2015/2016 11 / 31
http://find/http://goback/
8/19/2019 curs uaic iasi informatica
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/
8/19/2019 curs uaic iasi informatica
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/
8/19/2019 curs uaic iasi informatica
14/32
Inserare – CAZUL 2: rotat, ie la stânga
20
10
3 15
14
12
17
35
50
FII, UAIC () Curs 10 SD 2015/2016 14 / 31
http://find/
8/19/2019 curs uaic iasi informatica
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/
8/19/2019 curs uaic iasi informatica
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
http://find/http://goback/
8/19/2019 curs uaic iasi informatica
17/32
Operat, ia de inserare: algoritm
Se consideră că fiecare nod a arborelui este o structură cu următoarelecâmpuri:
cheie : informat, ia utilă a nodului;
culoare : ros, u / negru;
pred : adresa nodului părinte (null pentru rădacină);
stg : adresa fiului stâng;
drp : adresa fiului drept.
FII, UAIC () Curs 10 SD 2015/2016 17 / 31
O i d i l i
http://find/
8/19/2019 curs uaic iasi informatica
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 că interschimbăm stg cu drpt → culoare ← negru
end
FII, UAIC () Curs 10 SD 2015/2016 18 / 31
O i d i C 1
http://find/
8/19/2019 curs uaic iasi informatica
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/
8/19/2019 curs uaic iasi informatica
20/32
Operat, ia de inserare: Caz 2
x ← x → pred
rotatie-stânga(t , x )
FII, UAIC () Curs 10 SD 2015/2016 20 / 31
O ti d i C 3
http://find/http://goback/
8/19/2019 curs uaic iasi informatica
21/32
Operat, ia de inserare: Caz 3
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/
8/19/2019 curs uaic iasi informatica
22/32
Operat, ia de inserare - exemplul 2
FII, UAIC () Curs 10 SD 2015/2016 22 / 31
Operatia de inserare exemplul 3
http://find/
8/19/2019 curs uaic iasi informatica
23/32
Operat, ia de inserare - exemplul 3
FII, UAIC () Curs 10 SD 2015/2016 23 / 31
Operatia de inserare exemplul 3
http://find/
8/19/2019 curs uaic iasi informatica
24/32
Operat, ia de inserare - exemplul 3
FII, UAIC () Curs 10 SD 2015/2016 24 / 31
Operatia de stergere
http://find/
8/19/2019 curs uaic iasi informatica
25/32
Operat, ia de s, tergere
Similară cu operat, ia de s, tergere de la arborii binari de căutareobis, nuit, i.
Se va t, ine cont că nodurile “null” fac parte din structură.
În urma s, tergerii este posibil ca proprietatea 4 să nu mai fierespectată.
Se restaurează proprietă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 proprietătii 4
http://find/
8/19/2019 curs uaic iasi informatica
26/32
Operat, ia de s, tergere: restaurarea proprietat, ii 4
Caz 1: Se transformă ı̂ntr-unul din cazurile 2), 3), 4) printr-o rotat, ie.
Caz 2: Nodul pentru care nu este satisfăcută proprietatea estedeplasat spre rădăcină cu un nivel prin recolorarea unui nod.
Caz 3: Se transformă ı̂n cazul 4) printr-o interschimbare de culori s, i orotat, ie.
Caz 4: În acest caz se restabiles, te proprietatea de arbore bicolorpentru ı̂ntreg arborele.
FII, UAIC () Curs 10 SD 2015/2016 26 / 31
Stergere – CAZUL 1
http://find/http://goback/
8/19/2019 curs uaic iasi informatica
27/32
S, tergere CAZUL 1
Caz 1: Se transformă ı̂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
Stergere – CAZUL 2
http://find/http://goback/
8/19/2019 curs uaic iasi informatica
28/32
S, tergere CAZUL 2
Caz 2: Nodul pentru care nu este satisfăcută proprietatea este deplasatspre rădăcină 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
Stergere – CAZUL 3
http://goforward/http://find/http://goback/
8/19/2019 curs uaic iasi informatica
29/32
S, tergere CAZUL 3
Caz 3: Se transformă ı̂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
Stergere – CAZUL 4
http://find/http://goback/
8/19/2019 curs uaic iasi informatica
30/32
S, tergere CAZUL 4
Caz 4: Î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/
8/19/2019 curs uaic iasi informatica
31/32
Arbori bicolori
Complexitatea algoritmilor de inserare / s, tergere: O (log n).
Corolar:Clasa arborilor bicolori este O (log n)–stabilă.
FII, UAIC () Curs 10 SD 2015/2016 31 / 31
Arbori bicolori
http://find/
8/19/2019 curs uaic iasi informatica
32/32
Complexitatea algoritmilor de inserare / s, tergere: O (log n).
Corolar:Clasa arborilor bicolori este O (log n)–stabilă.
Utilizări: System symbol tables.
Kernel Linux (Completely Fair Scheduler).
FII, UAIC () Curs 10 SD 2015/2016 31 / 31
http://find/