Post on 18-Dec-2014
description
Prof. Pier Luca Lanzi
Alberi Red BlackAlgoritmi e Calcolo Parallelo
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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)
Prof. Pier Luca Lanzi
9
Prof. Pier Luca Lanzi
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
Prof. Pier Luca LanziL7.12
Esempio di Albero Red-Black
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
Prof. Pier Luca LanziL7.13
Esempio di Albero Red-Black
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
Prof. Pier Luca Lanzi
Esempio di Albero Red-Black
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
Prof. Pier Luca LanziL7.15
Esempio di Albero Red-Black
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
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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 15Ricolorare
muovendo sula violazione 88
1010
1818
2626
2222
77
33
1111
20
1515
Prof. Pier Luca Lanzi
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 15Ricolorare
muovendo sula violazione 88
1010
1818
2626
2222
77
33
1111
21
1515
Prof. Pier Luca Lanzi
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 15Ricolorare
muovendo sula violazione
Rotate(18)88
1010
1818
2626
2222
77
33
1111
22
1515
Prof. Pier Luca Lanzi
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 15Ricolorare
muovendo sula violazione
Rotate(18)
23
88
1111
1010
1818
2626
2222
77
1515
33
Prof. Pier Luca Lanzi
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 15Ricolorare
muovendo sula violazione
Rotate(18)Left-Rotate(7) e
ricolorare
24
88
1111
1010
1818
2626
2222
77
1515
33
Prof. Pier Luca Lanzi
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 15Ricolorare
muovendo sula violazione
Rotate(18)Left-Rotate(7) e
ricolorare
25
88 1111
1010
1818
2626
2222
77
1515
33
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
Notazione Grafica
denota un sottoalbero con una radice nera
Tutti i hanno la stessa altezza nera
27
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
Inserimento: Caso 2
L7.29
BB
CC
AA
x
y
Left-Rotate(A)
AA
CC
BB
x
y
Transforma nel Caso 3
29
Prof. Pier Luca LanziL7.30
Inserimento: Caso 3
AA
CC
BB
x
y
Right-Rotate(C)
AA
BB
CC
Finito! Nessuna violazione delle proprietà RB
30
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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)
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
map C++
• Funzionioperator=
• Iteratoribegin(), end(), rbegin(), rend()
• Modificatoriclear, insert, erase, swap
• Ricercacount, find, lower_bound, upper_bound
34
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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
Prof. Pier Luca Lanzi
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