Algoritmi e Calcolo Parallelo 2012/2013 - Alberi Red-Black

Prof. Pier Luca Lanzi

Alberi Red BlackAlgoritmi e Calcolo Parallelo


Riferimenti

• Bertossi Alan A., Montresor Alberto. “Algoritmi e strutture di dati” (seconda edizione), CittàStudi 2010

• Stanley B. Lippman, Barbara E. Moo, Josee Lajoie“C++ Primer”, 5th Edition Addison-Wesley

2


Alberi Binari di Ricerca

• Alberi Binari di Ricerca Struttura dati ispirata alla ricerca binaria Le chiavi dei nodi del sottoalbero

sinistro left[x] sono ≤ key[x] Le chiavi dei nodi del sottoalbero

destro right[x] sono ≥ key[x]

• Operazioni Ricerca, minimo, massimo, prev, next, inserimento, e

cancellazione

• Complessità Ricerca, inserimento, cancellazione sono O(h) per un albero

di altezza h Un albero binario di ricerca con n nodi generato in maniera

casuale ha un’altezza O(lg n)

4


5Alberi di Ricerca Bilanciati

• Alberi di ricerca Permettono di trovare un elemento in tempo O(h) Nel caso peggiore, h = O(n)Ma se l'albero è bilanciato, h=O(log n)

• Sono alberi di ricerca per i quali un’altezza di O(lg n) è garantita quando sono implementate le funzioni di inserimento/cancellazione dinamica

• Esempi di alberi bilanciati Alberi AVL Alberi 2-3 Alberi 2-3-4 B-alberi Alberi Red-black


Cosa Significa Bilanciato?

• Fattore di bilanciamento Il fattore di bilanciamento β(v) di un nodo v è la

massima differenza di altezza fra i sottoalberi di v

• EsempioUn albero perfettamente bilanciato ha β(v)=0

per ogni nodo v

6


Algoritmi di Bilanciamento

• Alberi AVL (Adel'son-Vel'skii e Landis, 1962) β(v) ≤ 1 per ogni nodo v Bilanciamento ottenuto tramite rotazioni

• Alberi 2-3 (Hopcroft, 1983) β(v) = 0 per ogni nodo v Bilanciamento ottenuto tramite merge/split,

grado variabile

• B-Alberi (Bayer, McCreight, 1972) β(v) = 0 per ogni nodo v Specializzati per strutture in memoria secondaria

• Alberi Red-Black (Bayer, 1972)

7


8Alberi Red-Black (Red-Black Trees, RB-Tree)

• Un albero rosso-nero è un albero binario di ricerca in cui:Ogni nodo è colorato di rosso o di nero Le chiavi vengono mantenute solo nei nodi interni dell’albero Le foglie sono costituite da nodi nil

• Un albero red-black deve soddisfare i seguenti vincoli: La radice è nera I nodi nil sono neri Se un nodo è rosso, allora entrambi i suoi figli sono neriOgni percorso da un nodo interno ad una foglia ha lo stesso

numero di nodi neri

• Ogni nodo mantiene: puntatore al genitore (parent); puntatori ai figli sinistro/destro (left, right); colore (color); chiave e dati (key, data)


9


Alberi Rosso-Nero (Red-Black Trees, RB-Tree)

• Nodo nil nodo sentinella che evita di trattare diversamente i

puntatori ai nodi dai puntatori nil al posto di un puntatore nil, si usa un puntatore ad un

nodo nil ne esiste solo uno, per risparmiare memoria nodo con figli nil → foglia nell'ARB corrispondente

• Definizione Il numero di nodi neri lungo ogni percorso da un nodo v

(escluso) ad una foglia è detto altezza nera di v, indicato bh(v)

Ben definito perché tutti i percorsi hanno lo stesso numero di nodi (regola 4)

• Definizione L’altezza nera di un albero RB è l’altezza nera della sua

radice

10

Prof. Pier Luca LanziL7.11

Esempio di Albero Red-Black

h = 4

88 1111

1010

1818

2626

2222

33

77

NIL NIL

NIL NIL NIL NIL

NIL

NIL NIL

11



88 1111

1010

1818

2626

2222

33

77

NIL NIL

NIL NIL NIL NIL

NIL

NIL NIL

12

1. Ogni nodo è colorato di rosso o di nero



88 1111

1010

1818

2626

2222

33

77

NIL NIL

NIL NIL NIL NIL

NIL

NIL NIL

13

2. La radice e i nodi nil sono neri



88 1111

1010

1818

2626

2222

33

77

NIL NIL

NIL NIL NIL NIL

NIL

NIL NIL

14

3. Se un nodo è rosso, allora entrambi i suoi figli sono neri. Se un nodo è rosso, allora il nodo parente è nero



88 1111

1010

1818

2626

2222

33

77

NIL NIL

NIL NIL NIL NIL

NIL

NIL NIL

15

4. Ogni percorso da un nodo interno ad una foglia ha lo stesso numero di nodi neri

bh = 2

bh = 1

bh = 1

bh = 2

bh = 0


Altezza di Albero Red-Black

• TeoremaUn albero red-black con n chiavi ha un’altezza h,

h ≤ 2 lg(n + 1).

• CorollarioLe funzioni di SEARCH, MIN, MAX, SUCCESSOR,

and PREDECESSOR sono eseguite con un tempo che è O(lg n) per un albero red-black con n chiavi

16


Alberi Red-Black

Le operazioni di INSERT e DELETEmodificano in un albero red-black

È possibile che le condizioni di bilanciamento risultino violate

Se le proprietà red-black vengono violate si può, modificare i colori nella zona della violazione;ribilanciare l’albero con opportune rotazioni


Rotazioni

• Le rotazioni mantengono l’ordinamento inordine delle chiavi

a Î a, b Î b, c Î g a ≤ A ≤ b ≤ B ≤ c

• Una rotazione può essere eseguita in O(1)

AA

BB

aa bbgg

RIGHT-ROTATE(B)

BB

AA

ggbbaa

LEFT-ROTATE (A)

18


Alberi Red-Black: Inserimento

• Qual è l’idea? Inserire x nell’albero. Colorare il nodo x rosso. Solo la proprietà 3 potrebbe essere violataMuovere la violazione verso l’alto ricolorando

fino a quando è aggiustata attraverso rotazioni e ricolorazioni

• Esempio: Inserire 15

88

1010

1818

2626

2222

77

33

1111

19


Alberi red-black: Inserimento



• Esempio: Inserire 15Ricolorare

muovendo sula violazione 88

1010

1818

2626

2222

77

33

1111

20

1515






muovendo sula violazione 88

1010

1818

2626

2222

77

33

1111

21

1515






muovendo sula violazione

Rotate(18)88

1010

1818

2626

2222

77

33

1111

22

1515







Rotate(18)

23

88

1111

1010

1818

2626

2222

77

1515

33







Rotate(18)Left-Rotate(7) e

ricolorare

24

88

1111

1010

1818

2626

2222

77

1515

33







Rotate(18)Left-Rotate(7) e

ricolorare

25

88 1111

1010

1818

2626

2222

77

1515

33


Pseudo-Codice

RB-INSERT(T, x)TREE-INSERT(T, x) color[x] ← RED only RB property 3 can be violated⊳ while x<>root[T] and color[p[x]] = RED do if p[x] = left[p[p[x]] then y ← right[p[p[x]] y = aunt/uncle of x⊳ if color[y] = RED then <Case 1> else if x = right[p[x]]

then <Case 2> Case 2 falls into Case 3⊳ <Case 3> else <“then” clause with “left” and “right” swapped>color[root[T]] ← BLACK

26


Notazione Grafica

denota un sottoalbero con una radice nera

Tutti i hanno la stessa altezza nera

27


Inserimento: Caso 1

BB

CC

DDAA

x

y

oppure con i figli di A scambiati

BB

CC

DDAA

new x

Spinge il nero di C su A e D, e continua ricorsivamente, dato che I parenti di C potrebbero essere rossi

Ricolora

28


Inserimento: Caso 2

L7.29

BB

CC

AA

x

y

Left-Rotate(A)

AA

CC

BB

x

y

Transforma nel Caso 3

29


Inserimento: Caso 3

AA

CC

BB

x

y

Right-Rotate(C)

AA

BB

CC

Finito! Nessuna violazione delle proprietà RB

30


Analisi

• Sommario dell’algoritmo di inserimento Inserisce l’elemento e lo colora di rossoRisalisce l’albero applicando il caso 1, che

ricolora i nodiSe il caso 2 e 3 si verificano, applicare una o due

rotazioni

• Esecuzione: O(lg n) con rotazioni che sono O(1)

• Cancellazione: stessa complessità e stesso numero di rotazioni dell’inserimento (dal libro di testo)

31


32Sommario

• Alberi di ricerca bilanciati Alberi di ricerca per i quali un’altezza di O(lg n) è

garantita quando sono implementate le funzioni di inserimento/cancellazione dinamica

• Un albero rosso-nero è un albero binario di ricerca in cui: Ogni nodo è colorato di rosso o di nero Le chiavi vengono mantenute solo nei nodi interni

dell’albero Le foglie sono costituite da nodi nil

• Un albero red-black deve soddisfare quattro vincoli: La radice è nera I nodi nil sono neri Se un nodo è rosso, allora entrambi i suoi figli sono neri Ogni percorso da un nodo interno ad una foglia ha lo

stesso numero di nodi neri

• Inserimento e cancellazione devono mantenere le proprietà RB, hanno complessità O(lg n)


Alberi Red-Black e Mappe C++

• Le STL del C++ non hanno implementazioni di alberi di ricerca

• Gli alberi red-black sono utilizzati nelle map e nelle multimap

• Le mappe sono container associativi che memorizzano delle combinazioni di chiave e valore mappato

33


map C++

• Funzionioperator=

• Iteratoribegin(), end(), rbegin(), rend()

• Modificatoriclear, insert, erase, swap

• Ricercacount, find, lower_bound, upper_bound

34


Esempio: Conta la frequenza delle parole

#include <iostream>#include <string>#include <map> int main(){ std::map<std::string, int> wordcounts; std::string s; while (std::cin >> s && s != "end") ++wordcounts[s]; while (std::cin >> s && s != "end") std::cout << s << ' ' << wordcounts[s] << '\n';}

35


Iteratori delle map

std::map<std::string, int>::iterator it;

for(it=wordcounts.begin(); it!=wordcounts.end(); it++){

// cosa indica *it?}

• Le mappe memorizzano un tipo speciale chiamato “pair”

• Una mappa “map<std::string, int>” memorizza elementi di tipo pair<std::string,int>

• “pair” e’ raggruppa due elementi accessibili attraverso il campo first e il campo second

• Le funzioni di insert ed erase lavorano su oggetti di tipo pair

36


Esempio: Iteratori

#include <iostream>#include <string>#include <map>

int main(){ std::map<std::string, int> wordcounts; std::string s;

// legge tutte le parole dall'input fino a quando finisce l'input// o trova end

while (std::cin >> s) ++wordcounts[s];

std::map<std::string, int>::iterator it;

for(it=wordcounts.begin(); it!=wordcounts.end(); it++) std::cout << it->first << " => " << it->second << std::endl;}

37

Algoritmi e Calcolo Parallelo 2012/2013 - Alberi Red-Black

Education

Transcript of Algoritmi e Calcolo Parallelo 2012/2013 - Alberi Red-Black