Algoritmi e Strutture Dati
Alberi binari di ricerca
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Dizionari
Dizionario
✦
Insieme dinamico che implementa le seguenti funzionalità
✦
Item lookup(Item k)
insert(Item k, Item v)
remove(Item k)
Esempi di implementazione
✦
Array ordinato
✦
✦
Ricerca O(log n), inserimento/cancellazione O(n)
Lista non ordinata
✦
✦
© Alberto Montresor
Ricerca/cancellazione O(n), inserimento O(1)
2
Alberi binari di ricerca (ABR)
Idea “ispiratrice”
✦
Portare l'idea di ricerca binaria in un albero
✦
Definizione
✦
Ogni nodo u contiene una chiave u.key associata ad un valore u.value
✦
Le chiavi appartengono ad un insieme totalmente ordinato
✦
10
Proprietà
✦
1. Le chiavi dei nodi del sottoalbero sinistro di u
sono minori di u.key
2. Le chiavi dei nodi del sottoalbero destro di u
sono maggiori di u.key
© Alberto Montresor
15
6
4
8
12
18
3
Alberi binari di ricerca (ABR)
Proprietà di ricerca
✦
Le proprietà 1. e 2. permettono di realizzare un algoritmo di ricerca dicotomica
✦
Domanda – Proprietà di ordine
✦
Come devo visitare l'albero per ottenere la lista ordinata dei valori?
✦
Dettagli implementativi
✦
Ogni nodo deve mantenere
✦Figlio sinistro, destro
✦
Padre
✦
Chiave
Padre
Key, Value
✦
Valore
✦
© Alberto Montresor
Figlio
sinistro
Figlio
destro
4
Alberi binari di ricerca: Specifica
Operazioni ammesse su ABR
✦
Tree key()
Tree value()
Tree left()
Tree right()
Tree parent()
Tree lookup(Item k)
Tree insert(Item k, Item d)
Tree delete()
© Alberto Montresor
5
Ricerca: esempio
Ricerca del valore 4
4 < 6
4 sta nel sottoalbero
sinistro di 6
T
6
2
1
8
4
3
© Alberto Montresor
6
Ricerca: esempio
Ricerca del valore 4
4 > 2
4 sta nel sottoalbero
destro di 2
T
6
2
1
8
4
3
© Alberto Montresor
7
Ricerca: esempio
Ricerca del valore 4
4 = 4
trovato!
T
6
2
1
8
4
3
© Alberto Montresor
8
Ricerca: Implementazione
Ricorsiva
Iterativa
© Alberto Montresor
9
Ricerca del minimo e del massimo: Esempi
Sottoalbero con
radice 2:
Sottoalbero con
radice 8:
T
- minimo 1
- massimo 4
- massimo 15
6
2
8
44
1
3
© Alberto Montresor
- minimo 8
12
9
15
10
Ricerca del minimo e del massimo: Pseudo-codice
© Alberto Montresor
11
Ricerca del successore/predecessore
Definizione
✦
T
Il successore di un nodo u è il
più piccolo nodo maggiore di u
✦
6
u
Due casi
✦
2
u ha un figlio destro
✦
8
Il successore u' è il minimo
del sottoalbero destro di u
✦
Esempio:
successore di 2 è 3
1
12
4
✦
3
9
15
u'
© Alberto Montresor
12
Ricerca del successore/predecessore
Definizione
✦
Il successore di un nodo u è il
più piccolo nodo maggiore di u
T
u'
6
✦
Due casi
✦
2
u non ha un figlio destro
✦
Il successore è il primo avo
u' tale per cui u sta nel
sottoalbero sinistro di u'
8
✦
Esempio:
successore di 4 è 6
1
12
3
✦
4
9
15
u
© Alberto Montresor
13
Ricerca del successore: Pseudo-codice (iterativo)
© Alberto Montresor
14
Ricerca: costo computazionale
In generale
✦
Le operazioni di ricerca sono
confinate ai nodi posizionati
lungo un singolo percorso
(path) dalla radice ad una foglia
✦
h = altezza dell’albero
Tempo di ricerca: O(h)
✦
Domanda
✦
Qual è il caso pessimo?
✦
Domanda
✦
Qual è il caso ottimo?
✦
© Alberto Montresor
15
Inserimento
5 < 6
Inserimento valore 5
5 > 2
T
5 > 4
6
2
44
1
3
© Alberto Montresor
8
12
5
9
15
16
Inserimento: pseudo-codice (iterativo)
© Alberto Montresor
17
Inserimento: pseudo-codice (iterativo)
© Alberto Montresor
18
Cancellazione
Caso 1: Il nodo u da eliminare non ha figli
T
✦
Semplicemente si elimina
✦
6
Esempio:
✦
Eliminazione nodo 5
2
✦
8
44
1
3
12
5
9
15
u
© Alberto Montresor
19
Cancellazione
Caso 2: Il nodo u da eliminare ha un unico figlio f
T
✦
Si elimina u
✦
6
Si attacca f all'ex-padre p di u
in sostituzione di u (short-cut)
✦
2
p
8
Esempio:
✦
Cancellazione di 4
✦
1
4
3
© Alberto Montresor
f
12
u
9
15
20
Cancellazione
Caso 3: Il nodo u da eliminare ha due figli
T
✦
Si individua il successore s del nodo u
Il successore non ha figlio sinistro
✦
7
Si “stacca” il successore
✦
23
Si attacca l'eventuale
figlio destro di s al
padre di s (short-cut)
✦
Si copia s su u
✦
u
8
5
1
12
Si rimuove il nodo s
✦
s
6
3
9
15
4
© Alberto Montresor
21
Cancellazione: Pseudo-codice
© Alberto Montresor
22
Cancellazione – Dimostrazione di correttezza
Caso 1 - nessun figlio
✦
Eliminare foglie non cambia la proprietà di ordine dei nodi rimanenti
✦
Caso 2 - solo un figlio (destro o sinistro)
✦
Se u è il figlio destro (sinistro) di p,
tutti i i valori nel sottoalbero di f sono maggiori (minori) di p
✦
Quindi f può essere attaccato come figlio destro (sinistro) di p al posto di u
✦
Caso 3 - due figli
✦
Il successore s
✦
è sicuramente maggiore di tutti i nodi del sottoalbero sinistro di u
✦
è sicuramente minore di tutti i nodi del sottoalbero destro di u
✦
Quindi può essere sostituito a u
✦
© Alberto Montresor
23
Modifica: costo computazionale
In generale
✦
Le operazioni di modifica sono
confinate ai nodi posizionati
lungo un singolo percorso
(path) dalla radice ad una foglia
✦
h = altezza dell’albero
Tempo di ricerca: O(h)
✦
© Alberto Montresor
24
Complessità media
Qual è l'altezza media di un albero di ricerca?
✦
Caso generale (inserimenti + cancellazione)
✦
Difficile da trattare
✦
Caso “semplice”: inserimenti in ordine casuale
✦
E' possibile dimostrare che l'altezza media è O(log n)
✦
Fattore di bilanciamento
✦
Il fattore di bilanciamento β(v) di un nodo v è la massima differenza di altezza fra i
sottoalberi di v
✦
Esempio: albero perfetto:
✦
β(v)=0 per ogni nodo v
✦
In generale:
✦
Sono necessarie tecniche per mantenere bilanciato l'albero
✦
© Alberto Montresor
25
Algoritmi di bilanciamento
Alberi AVL (Adel'son-Vel'skii e Landis, 1962)
✦
β(v) ≤ 1 per ogni nodo v
✦
Bilanciamento ottenuto tramite rotazioni
✦
B-Alberi (Bayer, McCreight, 1972)
✦
β(v) = 0 per ogni nodo v
✦
Specializzati per strutture in memoria secondaria
✦
Alberi 2-3 (Hopcroft, 1983)
✦
β(v) = 0 per ogni nodo v
✦
Bilanciamento ottenuto tramite merge/split, grado variabile
✦
B-alberi binari (Andersson, 1993)
✦
Alberi Red-Black (Bayer, 1972)
✦
© Alberto Montresor
26
Esempio di rotazione
v
u
u
v
T3
T1
T2
T3
T2
T1
© Alberto Montresor
27
Alberi Rosso-Nero (Red-Black Treee, RB-Tree)
Un albero Red-Black è 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:
✦
1. La radice è nera
2. Tutte le foglie sono nere
3. Entrambi i figli di un nodo rosso sono neri
4. Tutti i cammini semplici da ogni nodo u ad una delle foglie contenute nel
sottoalbero radicato in u hanno lo stesso numero di nodi neri
© Alberto Montresor
28
Alberi Red-Black
Ogni nodo mantiene
✦
parent
puntatore al padre
left, right
puntatori ai figli sinistro/destro
✦
✦
color
✦
key, data
✦
colore
chiave e dati
Nodo Nil
✦
nodo sentinella il cui scopo è evitare 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'ABR corrispondente
✦
© Alberto Montresor
29
Alberi Red-Black
Definizione:
✦
Il numero di nodi neri lungo ogni percorso da un nodo v (escluso) ad ogni foglia
(inclusa) del suo sottoalbero è detto altezza nera di v, indicato b(v)
✦
Ben definito perché tutti i percorsi hanno lo stesso numero di nodi neri (regola 4)
✦
Definizione:
✦
L’altezza nera di un albero Red-Black è pari all’altezza nera della sua radice
✦
© Alberto Montresor
30
Alberi Red-Black: esempio I
3. Entrambi i figli di un nodo rosso sono neri.
Ma un nodo nero può avere figli neri!
30
15
70
Nil
5
Nil
60
20
10
Nil
Nil
Nil
40
Nil
© Alberto Montresor
50
Nil
85
80
65
55
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
31
Alberi Red-Black: esempio I
4. Ogni percorso da un nodo interno ad un nodo Nil ha lo stesso numero di nodi neri.
Altezza nera di questo albero: 3
30
15
70
Nil
5
Nil
60
20
10
Nil
Nil
Nil
40
Nil
© Alberto Montresor
50
Nil
85
80
65
55
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
32
Alberi Red-Black: più colorazioni sono possibili
Albero Red-Black con 3 nodi neri lungo ogni percorso dalla
radice ai nodi Nil
30
15
70
Nil
5
Nil
60
20
10
Nil
Nil
Nil
40
Nil
© Alberto Montresor
50
Nil
85
80
65
55
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
33
Alberi Red-Black: più colorazioni sono possibili
Albero Red-Black con 3 nodi neri lungo ogni percorso dalla
radice ai nodi Nil
30
15
70
Nil
5
Nil
60
20
10
Nil
Nil
Nil
40
Nil
© Alberto Montresor
50
Nil
85
80
65
55
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
34
Alberi Red-Black: colorazione diversa, altezza nera diversa
Albero RB con 3 nodi neri
lungo ogni percorso dalla radice ai nodi Nil
30
15
70
Nil
60
20
10
Nil
Nil
Nil
50
Nil
© Alberto Montresor
85
80
65
Nil
Nil
Nil
Nil
90
Nil Nil Nil
35
Alberi Red-Black: colorazione diversa, altezza nera diversa
Stesso albero con 2 nodi neri
lungo ogni percorso dalla radice ai nodi Nil
30
15
70
Nil
60
20
10
Nil
Nil
Nil
50
Nil
© Alberto Montresor
85
80
65
Nil
Nil
Nil
Nil
90
Nil Nil Nil
36
Alberi Red-Black: questo albero può essere un albero RB?
30
15
70
Nil
60
20
10
Nil
Nil
Nil
Nil
© Alberto Montresor
Nil
50
40
Nil
85
Nil Nil
55
Nil Nil
37
Alberi Red-Black: questo albero può essere un albero RB?
Per vincolo sull'altezza nera
ci possono essere al più 3 nodi neri lungo un percorso!
30
15
70
Nil
60
20
10
Nil
Nil
Nil
Nil
© Alberto Montresor
Nil
50
40
Nil
85
Nil Nil
55
Nil Nil
38
Alberi Red-Black: questo albero può essere un albero RB?
La radice è nera.
Supponiamo che 60 e 70 siano entrambi neri.
30
15
70
Nil
Nil
Impossibile!
Perché dovremmo
violare vincolo 3
© Alberto Montresor
60
20
10
Nil
Nil
Nil
Nil
50
40
Nil
85
Nil Nil
55
Nil Nil
39
Alberi Red-Black: questo albero può essere un albero RB?
30
15
Nil
Quindi uno di questi
due nodi deve essere
rosso
© Alberto Montresor
60
20
10
Nil
70
Nil
Nil
40
85
Nil
50
Nil Nil
55
Nil Nil Nil Nil
40
Alberi Red-Black: questo albero può essere un albero RB?
Proviamo a colorare di rosso il nodo 60.
Esiste un percorso con 2 nodi neri
Esiste un percorso con 3 nodi neri
30
Impossibile per il
vincolo sulla lunghezza
15
60
20
10
Nil
70
Nil
Nil
Nil
40
85
Nil
50
Nil Nil
55
Nil Nil Nil Nil
© Alberto Montresor
41
Alberi Red-Black: questo albero può essere un albero RB?
Proviamo a colorare di rosso il nodo 70
30
15
60
20
10
Nil
70
Nil
Nil
Nil
40
Esistono due percorsi
con 2 soli nodi neri
© Alberto Montresor
85
Nil
50
Nil Nil
55
Nil Nil Nil Nil
42
Alberi Red-Black: questo albero può essere un albero RB?
Per vincolo 4 e il vincolo 3, ci possono essere al più 2 nodi
neri lungo un percorso!
30
15
70
Nil
60
20
10
Nil
Nil
Nil
Nil
© Alberto Montresor
Nil
50
40
Nil
85
Nil Nil
55
Nil Nil
43
Alberi Red-Black: questo albero può essere un albero RB?
Per vincolo 4 e il vincolo 3, ci possono essere al più 2 nodi
neri lungo un percorso!
30
15
70
Nil
60
20
10
Nil
Nil
Nil
Nil
© Alberto Montresor
Nil
50
40
Questa sarebbe
l’unica possibilità!
Nil
85
55
Nil Nil
Nil Nil
Impossibile!
Perché dovremmo
violare vincolo 1
44
Alberi Red-Black: questo albero può essere un albero RB?
Questo albero NON può essere un albero Red-Black!
30
15
70
Nil
60
20
10
Nil
Nil
Nil
Nil
© Alberto Montresor
Nil
50
40
Nil
85
Nil Nil
55
Nil Nil
45
Alberi Red-Black: Proprietà
Da cui segue:
✦
Le operazioni di ricerca hanno costo O(log n)
✦
Cosa succede per le operazioni di modifica?
✦
© Alberto Montresor
46
Inserimenti
Durante la modifica di un albero Red-Black:
✦
è possibile che le condizioni di bilanciamento risultino violate.
✦
Quando le proprietà Red-Black vengono violate si può agire:
✦
modificando i colori nella zona della violazione;
✦
operando dei ribilanciamenti dell’albero tramite rotazioni:
✦
Rotazione destra
✦
Rotazione sinistra
✦
© Alberto Montresor
47
Rotazione a sinistra
p
Operazioni
x
✦
(1) far diventare B figlio destro di x
(2) far diventare x il figlio sinistro di y
y
A
(3) far diventare y figlio di p, il vecchio padre di x
B
© Alberto Montresor
C
48
Rotazione a sinistra
p
Operazioni
y
✦
(1) far diventare B figlio destro di x
x
(2) far diventare x il figlio sinistro di y
C
(3) far diventare y figlio di p, il vecchio padre di x
A
© Alberto Montresor
B
49
Rotazione a sinistra
p
Operazioni
y
✦
(1) far diventare B figlio destro di x
x
(2) far diventare x il figlio sinistro di y
C
(3) far diventare y figlio di p, il vecchio padre di x
A
© Alberto Montresor
B
50
Inserimento in alberi Red-Black
Inserimento
✦
Ricerca della posizione usando la stessa procedura usata per gli alberi binari di
ricerca
✦
Coloriamo il nuovo nodo di rosso
✦
Quale delle quattro proprietà può essere violata?
✦
Ripasso:
✦
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
✦
© Alberto Montresor
51
Come modificare la insertNode()
balanceTree(n)
© Alberto Montresor
52
Inserimento in alberi Red-Black
Come sistemare:
✦
Ci spostiamo verso l’alto lungo il percorso di inserimento
✦
per ripristinare la proprietà 3 (red-black)
✦
spostando le violazioni verso l’alto rispettando il vincolo 4 (mantenendo
l’altezza nera dell’albero)
✦
Al termine, coloriamo la radice di nero
✦
Nota
✦
Le operazioni di ripristino sono necessarie solo quando due nodi consecutivi sono
rossi!
✦
© Alberto Montresor
53
balanceNode(Tree t)
Nodi coinvolti
n
✦
Il nodo inserito t
✦
Suo padre p
✦
p
z
Suo nonno n
✦
Suo zio z
✦
© Alberto Montresor
t
54
Inserimento - 7 casi possibili
Caso 1:
✦
Nuovo nodo t non ha padre
✦
Primo nodo ad essere inserito o
siamo risaliti fino alla radice
✦
Si colora t di nero
✦
Caso 2
✦
Padre p di t è nero
✦
Nessun vincolo violato
✦
© Alberto Montresor
55
Inserimento - 7 casi possibili
Caso 1:
✦
Nuovo nodo t non ha padre
✦
Primo nodo ad essere inserito
✦
Si colora t di nero
✦
Caso 2
✦
Padre p di t è nero
✦
Nessun vincolo violato
✦
© Alberto Montresor
56
Inserimento - 7 casi possibili
Caso 3
✦
t rosso
✦
p rosso
✦
z rosso
✦
Se z è rosso, è possibile colorare di nero p, z, e di rosso n.
✦
Poiché tutti i cammini che passano per z e p passano per n,
la lunghezza dei cammini neri non è cambiata.
✦
Il problema può essere ora sul nonno:
✦
violato vincolo (1), ovvero n può essere una radice rossa
✦
violato vincolo (3), ovvero n rosso può avere un padre rosso.
✦
Poniamo t = n, e il ciclo continua.
✦
© Alberto Montresor
57
Inserimento - 7 casi possibili
Caso 3
✦
t rosso
✦
p rosso
✦
z rosso
✦
Se z è rosso, è possibile colorare di nero p, z, e di rosso n.
✦
Poiché tutti i cammini che passano per z e p passano per n,
la lunghezza dei cammini neri non è cambiata.
✦
Il problema può essere ora sul nonno:
✦
violato vincolo (1), ovvero n può essere una radice rossa
✦
violato vincolo (3), ovvero n rosso può avere un padre rosso.
✦
Poniamo t = n, e il ciclo continua.
✦
© Alberto Montresor
58
Inserimento - 7 casi possibili
Caso 4a,4b
✦
t rosso
✦
p rosso
✦
z nero
✦
Si assuma che t sia figlio destro di p e che p sia figlio sinistro di n
✦
Una rotazione a sinistra a partire dal nodo p scambia i ruoli di t e p ottenendo il
caso (5a), dove i nodi rossi in conflitto sul vincolo (3) sono entrambi figli sinistri dei
loro padri
✦
I nodi coinvolti nel cambiamento sono p e t, entrambi rossi, quindi la lunghezza dei
cammini neri non cambia
✦
© Alberto Montresor
59
Inserimento - 7 casi possibili
Caso 4a,4b
✦
t rosso
✦
p rosso
✦
z nero
✦
Si assuma che t sia figlio destro di p e che p sia figlio sinistro di n
✦
Una rotazione a sinistra a partire dal nodo p scambia i ruoli di t e p ottenendo il
caso (5a), dove i nodi rossi in conflitto sul vincolo (3) sono entrambi figli sinistri dei
loro padri
✦
I nodi coinvolti nel cambiamento sono p e t, entrambi rossi, quindi la lunghezza dei
cammini neri non cambia
✦
© Alberto Montresor
60
Inserimento - 7 casi possibili
Caso 5a,5b
✦
t rosso
✦
p rosso
✦
z nero
✦
Si assuma che t sia figlio sinistro di p e p sia figlio sinistro di n
✦
Una rotazione a destra a partire da n ci porta ad una situazione in cui t e n sono figli
di p
✦
Colorando n di rosso e p di nero ci troviamo in una situazione in cui tutti i vincoli
Red-Black sono rispettati
✦
in particolare, la lunghezza dei cammini neri che passano per la radice è uguale alla
situazione iniziale
✦
© Alberto Montresor
61
Inserimento - 7 casi possibili
Caso 5a,5b
✦
t rosso
✦
p rosso
✦
z nero
✦
Si assuma che t sia figlio sinistro di p e p sia figlio sinistro di n
✦
Una rotazione a destra a partire da n ci porta ad una situazione in cui t e n sono figli
di p
✦
Colorando n di rosso e p di nero ci troviamo in una situazione in cui tutti i vincoli
Red-Black sono rispettati
✦
in particolare, la lunghezza dei cammini neri che passano per la radice è uguale alla
situazione iniziale
✦
© Alberto Montresor
62
All together, now!
© Alberto Montresor
63
Inserimento in alberi Red-Black
T
t
30
15
10
Nil
Nil
60
Nil
Nil
50
40
Nil
© Alberto Montresor
Nil
70
20
Nil
Nil
85
80
65
55
16
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
64
Inserimento in alberi Red-Black
T
p è nero, t è rosso
30
15
70
10
Nil
Nil
t 16
Nil
Caso 2: nessun cambiamento
Non cambia l’altezza nera
di nessun nodo!
© Alberto Montresor
60
20
Nil
50
40
Nil
Nil
Nil
85
80
65
55
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
65
Inserimento in alberi Red-Black:
T
x 42
30
15
70
60
20
10
Nil
Nil
Nil
Nil
50
40
Nil
© Alberto Montresor
Nil
Nil
85
80
65
55
Nil
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
66
Inserimento in alberi Red-Black
p è rosso, t è rosso
30
T
15
70
10
Nil
60
20
Nil
Nil
85
n
Nil
50
90
z
p
Vincolo 3 è violato
80
65
40
55
Nil
Nil
Nil
Nil Nil Nil
t
Caso 3: z è rosso
Nil
Nil
© Alberto Montresor
42
Nil Nil
Nil
67
Inserimento in alberi Red-Black
T
p è rosso, t è rosso
30
15
70
10
Nil
60
20
Nil
Nil
n
Nil
50
80
65
90
z
p
Coloriamo di nero p
Coloriamo di nero z
Coloriamo di rosso n
40
55
Nil
Nil
Nil
Nil Nil Nil
t
Nil
Nil
© Alberto Montresor
85
42
Nil Nil
Nil
68
Inserimento in alberi Red-Black
T
p è rosso, t è rosso
30
15
70
10
Nil
60
20
t
Nil
Nil
Nil
Vincolo 3 è ripristinato
Altri vincoli mai stati
violati
50
40
Nil
Il padre del padre
di t è il nuovo t
© Alberto Montresor
85
Nil
55
42
80
65
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
Nil
69
Inserimento in alberi Red-Black
T
p è rosso, t è rosso
30
Caso 5a: z è nero
15
70
n
p
Nil
60
20
10
85
t
Nil
Nil
Nil
50
40
Vincolo 3 è nuovamente violato
tra il nuovo t e suo padre
Nil
Nil
© Alberto Montresor
z
55
42
80
65
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
Nil
70
Inserimento in alberi Red-Black
T
p è rosso, t è rosso
30
Caso 5a: z è nero
15
70
10
Nil
Nil
Coloriamo di nero t
Coloriamo di rosso n
Rotazione sinistra
Nil
Nil
50
40
Nil
Nil
© Alberto Montresor
60
x
20
80
65
55
42
85
Nil
Nil
Nil
90
Nil Nil Nil
Nil Nil
Nil
71
Inserimento in alberi Red-Black
T
p è rosso, t è rosso
30
Caso 5a: z è nero
15
60
t
10
Nil
Nil
Vincolo 3 è ripristinato
Altri vincoli mai stati
violati
Abbiamo finito
© Alberto Montresor
Nil
70
50
20
40
Nil
Nil
Nil
55
42
Nil
85
65
Nil Nil Nil Nil
Nil
80
90
Nil Nil Nil
72
Inserimento in alberi Red-Black
T
30
15
60
x
10
Nil
Nil
Nil
L’unico caso un cui si procede a
ripristinare verso l’alto è il caso
3. Negli altri casi, si esce dal
while e si termina
© Alberto Montresor
70
50
20
40
Nil
Nil
Nil
55
42
Nil
85
65
Nil Nil Nil Nil
Nil
80
90
Nil Nil Nil
73
Inserimento: complessità
Totale: O(log n)
✦
O(log n) per scendere fino al punto di inserimento
✦
O(1) per effettuare l'inserimento
✦
O(log n) per risalire e “aggiustare”
(caso pessimo – solo nel caso 3)
✦
Esiste anche la possibilità di effettuare una “top-down” insertion
✦
Scendere fino al punto di inserimento, “aggiustando” l'albero mano a mano
✦
Effettuare l'inserimento in una foglia
✦
© Alberto Montresor
74
Cancellazione in RB
L’algoritmo di cancellazione per alberi RB è costruito sull’algoritmo di
cancellazione per alberi binari di ricerca
✦
Dopo la cancellazione si deve decidere se è necessario ribilanciare o meno
✦
Le operazioni di ripristino del bilanciamento sono necessarie solo quando il nodo
cancellato è nero! (perché?)
✦
© Alberto Montresor
75
Cancellazione in RB
Se il nodo “cancellato” è rosso
✦
altezza nera invariata
✦
non sono stati creati nodi rossi consecutivi
✦
la radice resta nera
✦
Se il nodo “cancellato” è nero
✦
possiamo violare il vincolo 1: la radice può essere un nodo rosso
✦
possiamo violare il vincolo 3: se il padre e uno dei figli del nodo
cancellato erano rossi
✦
abbiamo violato il vincolo 4: altezza nera cambiata
✦
L’algoritmo balanceDelete(T,t) ripristina la proprietà Red-Black con rotazioni e
cambiamenti di colore:
✦
ci sono 4 casi possibili (e 4 simmetrici)!
✦
© Alberto Montresor
76
Cancellazione
if u.color = BLACK then balanceDelete(T, t)
© Alberto Montresor
77
Cancellazione - 8 casi possibili
© Alberto Montresor
78
Cancellazione - 8 casi possibili
© Alberto Montresor
79
Cancellazione in RB
© Alberto Montresor
80
Cancellazione in RB
L’operazione di cancellazione è concettualmente complicata!
✦
Ma efficiente:
✦
Dal caso (1) si passa ad uno dei casi (2), (3), (4)
✦
Dal caso (2) si torna ad uno degli altri casi, ma risalendo di un livello l’albero
✦
Dal caso (3) si passa al caso (4)
✦
Nel caso (4) si termina
✦
Quindi
✦
In altre parole, è possibile visitare al massimo un numero O(log n) di casi,
ognuno dei quali è gestito in tempo O(1)
✦
© Alberto Montresor
81
Esercizi
Esercizio - visita non ricorsiva
✦
Scrivere l’algoritmo non ricorsivo che effettua un attraversamento in ordine di un
ABR
✦
Qual è la sua complessità
✦
Esercizio - limite inferiore
✦
Dimostrare: poiché l'ordinamento basato su confronti di n elementi è Ω(n log n),
allora qualunque algoritmo basato su confronti per costruire un ABR è Ω(n log n)
✦
Esercizio - proprietà albero
✦
Dimostrate che se un nodo in un ABR ha due figli, allora il suo successore non ha
un figlio sinistro e il suo predecessore non ha un figlio destro
✦
Esercizio
✦
L'operazione di cancellazione è commutativa? Nel senso che cancellare x e y
oppure cancellare y e x produce lo stesso ABR?
✦
© Alberto Montresor
82