arbori de cautare echilibrati.sd/curs/curs-10.pdfarbori bicolori (red-black trees) i symmetric...
Post on 10-Feb-2020
63 Views
Preview:
TRANSCRIPT
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
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
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 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
top related