algoritmi e strutture dati alberi bilanciati: alberi red-black
TRANSCRIPT
![Page 1: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/1.jpg)
Algoritmi e Strutture Dati
Alberi Bilanciati: Alberi Red-Black
![Page 2: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/2.jpg)
Alberi Red-Black (alberi rossi-neri)
Un Albero Red-Black (rosso-nero) è essenzialmente un albero binario di ricerca in cui:
1 Le chiavi vengono mantenute solo nei nodi interni dell’albero
2 Le foglie sono costituite da nodi NIL, cioè nodi sentinella il cui contenuto è irrilevante e che evitano di trattare diversamente i puntatori ai nodi dai puntatori NIL. • In altre parole, al posto di un puntatore NIL si
usa un puntatore ad un nodo NIL. • Quando un nodo ha come figli nodi NIL,
quiel nodo sarebbe una foglia nell’albero binario di ricerca corrispondente.
![Page 3: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/3.jpg)
Alberi Red-Black (alberi rossi-neri)Un Albero Red-Black (rosso-nero) deve
soddisfare le seguenti proprietà (vincoli):
1 Ogni nodo è colorato o di rosso o di nero;
2 Per convezione, i nodi NIL si considerano nodi neri;
3 Se un nodo è rosso, allora entrambi i suoi figli
sono neri;
4 Ogni percorso da un nodo interno ad un nodo NIL (figlio di una foglia) ha lo stesso numero di nodi neri;
![Page 4: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/4.jpg)
Alberi Red-Black (alberi rossi-neri)Un Albero Red-Black (rosso-nero) deve
soddisfare le seguenti proprietà (vincoli):
1 Ogni nodo è colorato o di rosso o di nero;
2 Per convezione, i nodi NIL si considerano nodi neri;
3 Se un nodo è rosso, allora entrambi i suoi figli
sono neri;
4 Ogni percorso da un nodo interno ad un nodo NIL (figlio di una foglia) ha lo stesso numero di nodi neri;
Considereremo solo alberi Red-Black in cui la radice è nera.
![Page 5: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/5.jpg)
Alberi Red-Black: esempio I
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
85
5
60
80
10
90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
![Page 6: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/6.jpg)
Alberi Red-Black: esempio I
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
85
5
60
80
10
90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
Vincolo 3 impone che non possano esserci due nodiROSSI adiacenti. (Ma più nodi NERI possono essere adiacenti.)
![Page 7: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/7.jpg)
Alberi Red-Black: esempio I
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
85
5
60
80
10
90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
Ci sono 3 nodi neri lungo ogni percorso dalla radi-ce ad un nodo NIL
![Page 8: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/8.jpg)
Alberi Red-Black: esempio I
30
70
8560
80
10
90
15
20
50
40 55
65Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
Questo è anche un albero AVL
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri.
altezza 2 altezza 3
1 livello di diff.
5 Nil Nil
NilNil
![Page 9: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/9.jpg)
Alberi Red-Black: esempio II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri.
Questo è ancoraun albero Red-Black
![Page 10: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/10.jpg)
Alberi Red-Black: esempio II
Ma NON è un albero AVL!
30
70
8560
80 90
15
20
50
40 55
65Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri.
2 livelli
altezza 1 altezza 3
Nil
10
Nil
![Page 11: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/11.jpg)
Alberi Red-Black: esempio I
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
85
5
60
80
10
90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
Ci sono 3 nodi neri lungo ogni percorso dalla radi-ce ad un nodo NIL
![Page 12: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/12.jpg)
Alberi Red-Black: esempio III
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
85
5
60
80
10
90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
Ci sono 3 nodi neri lungo ogni percorso dalla radi-ce ad un nodo NIL
![Page 13: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/13.jpg)
Alberi Red-Black: esempio IV
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
8560
80
10
90
15
20
50 65Nil Nil Nil Nil
Nil Nil Nil Nil Nil Nil NilNil
Albero RB con 3 nodi neri lungo ogni percorso dalla radice ad un nodo NIL
![Page 14: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/14.jpg)
Alberi Red-Black: esempio V
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
8560
80
10
90
15
20
50 65Nil Nil Nil Nil
Nil Nil Nil Nil Nil Nil NilNil
Stesso albero con 2 nodi neri lungo ogni percorso dalla radice ad un nodo NIL
![Page 15: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/15.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
Questo albero può essere un albero Red-Black?
40 55
Nil Nil NilNil
85
Nil
![Page 16: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/16.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
Per vincolo 4 ci possono essere al più 3 nodi neri lungo un percorso!
40 55
Nil Nil NilNil
85
Nil
![Page 17: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/17.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
Per vincolo 4 ci possono essere al più 3 nodi neri lungo un percorso!
40 55
Nil Nil NilNil
85
Nil
Impossibile!Perché...
![Page 18: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/18.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
Per vincolo 4 ci possono essere al più 3 nodi neri lungo un percorso!
40 55
Nil Nil NilNil
85
Nil
Impossibile!Perché dovremmo
violare vincolo 3
![Page 19: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/19.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
Per vincolo 4 ci possono essere al più 3 nodi neri lungo un percorso!
40 55
Nil Nil NilNil
85
Nil
Quindi uno di questidue nodi deve essere
rosso
![Page 20: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/20.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
40 55
Nil Nil NilNil
85
Nil
Esistono due percorsicon 2 soli nodi neri
Per vincolo 4 ci possono essere al più 3 nodi neri lungo un percorso!
![Page 21: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/21.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
40 55
Nil Nil NilNil
85
Nil
Esiste un percorsocon 2 soli nodi neri
Per vincolo 4 ci possono essere al più 3 nodi neri lungo un percorso!
![Page 22: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/22.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
40 55
Nil Nil NilNil
85
Nil
Esiste un percorsocon 2 soli nodi neri
Per vincolo 4 ci possono essere al più 3 nodi neri lungo un percorso!
Questo caso èimpossibile perchè
un percorso ha 3 neri
![Page 23: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/23.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
Per vincolo 4 e il vincolo 3, ci possono essere al più 2 nodi neri lungo un percorso!
40 55
Nil Nil NilNil
85
Nil
![Page 24: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/24.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
Per vincolo 4 e il vincolo 3, ci possono essere al più 2 nodi neri lungo un percorso!
40 55
Nil Nil NilNil
85
Nil
Questa sarebbel’unica possibilità!
![Page 25: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/25.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
Per vincolo 4 e il vincolo 3, ci possono essere al più 2 nodi neri lungo un percorso!
40 55
Nil Nil NilNil
85
Nil
Impossibile!Perché dovremmo
violare vincolo 4
![Page 26: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/26.jpg)
Alberi Red-Black: esempio VI
3 Se un nodo è rosso, allora entrambi i suoi figli sono neri;4 Ogni percorso da un nodo interno ad un nodo NIL ha lo stesso numero di nodi neri. 30
70
6010
15
20
50Nil Nil Nil Nil Nil Nil
Questo albero NON può essere un albero Red-Black!
40 55
Nil Nil NilNil
85
Nil
A meno che l’albero non venga ristrutturato (tramite rotazioni)
![Page 27: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/27.jpg)
Percorso Nero in alberi Red-Black
Definizione: Il numero di nodi neri lungo ogni percorso da un nodo x (escluso) ad una foglia è detto altezza nera di x
Definizione: L’altezza nera di un albero Red-Black è l’altezza nera della sua radice.
![Page 28: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/28.jpg)
Percorso massimo in alberi Red-Black
Lemma: Un albero Red-Black con n nodi ha altezza al più 2 log(n + 1)
Dimostrazione: Iniziamo col dimostrare per induzione che il sottoalbero con radice x ha almeno
nodi interni
dove bh(x) è l’altezza nera di x.
L’induzione sarà sull’altezza di x.
12 )( xbh
![Page 29: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/29.jpg)
Percorso massimo in alberi Red-Black
12 )( xbh
01212 0)( xbh
Il sottoalbero con radice x ha al meno
nodi interni
dove bh(x) è l’altezza nera di x.
Passo Base:
Se x ha altezza 0: allora x è una foglia NIL e quindi contiene almeno:
![Page 30: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/30.jpg)
Percorso massimo in alberi Red-Black
Il sottoalbero con radice x ha al meno
nodi interni
dove bh(x) è l’altezza nera di x.
Passo Induttivo:
Se x sia interno con 2 figli e
abbia altezza bh(x)>1
Entrambi i suoi figli avranno
altezza bh(x) o bh(x)-1
12 )( xbh
10
15
20
bh(x)
bh(x)bh(x)-1
10
15
20
bh(x)
bh(x) -1bh(x)-1
![Page 31: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/31.jpg)
Percorso massimo in alberi Red-BlackIl sottoalbero con radice x ha al meno
nodi interni
dove bh(x) è l’altezza nera di x.
Passo Induttivo:
Sia x nodo interno con 2 figli
e abbia altezza > 0
Entrambi i suoi figli avranno
altezza nera bh(x) o bh(x)-1
Entrambi i suoi figli avranno altezza
minore di x, quindi possiamo usare ipotesi induttiva
12 )( xbh
10
15
20
bh(x)
bh(x)bh(x)-1
10
15
20
bh(x)
bh(x) -1bh(x)-1
![Page 32: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/32.jpg)
Percorso massimo in alberi Red-BlackIl sottoalbero con radice x ha al meno
nodi interni
dove bh(x) è l’altezza nera di x.
Passo Induttivo:
Se x sia interno con 2 figli e
abbia altezza >0
Entrambi i suoi figli avranno
altezza nera bh(x) o bh(x)-1
Ogni figlio avrà almeno
nodi interni
12 )( xbh
12 1)( xbh
10
15
20
bh(x)
bh(x)bh(x)-1
10
15
20
bh(x)
bh(x) -1bh(x)-1
![Page 33: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/33.jpg)
Percorso massimo in alberi Red-BlackIl sottoalbero con radice x ha al meno
nodi interni
dove bh(x) è l’altezza nera di x.
Passo Induttivo:
Sia x nodo interno con 2 figli e abbia altezza >0
Ogni figlio avrà almeno
nodi interni
Quindi il sottoalbero con radice x conterrà almeno
nodi interni
12 )( xbh
12 1)( xbh
)12(1)12()12( )(1)(1)( xbhxbhxbh
![Page 34: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/34.jpg)
Percorso massimo in alberi Red-BlackIl sottoalbero con radice x ha quindi al meno
nodi interni
dove bh(x) è l’altezza nera di x.
Completiamo la dimostrazione del lemma.
Sia ora h l’altezza dell’albero.
Per il vincolo 3 almeno metà dei nodi lungo ogni percorso (esclusa la radice) sono neri.
Quindi l’altezza nera dell’albero dovrà essere almeno h/2 ( cioè bh h/2 ).
12 )( xbh
![Page 35: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/35.jpg)
Percorso massimo in alberi Red-BlackIl sottoalbero con radice x ha al meno
nodi interni
dove bh(x) è l’altezza nera di x.
Completiamo la dimostrazione del lemma.
Sia ora h l’altezza dell’albero.
Quindi l’altezza nera dell’albero dovrà essere almeno h/2 ( cioè bh h/2 ).
Ma allora, il numero di nodi dell’albero sarà
12 )( xbh
12)12( 2)( hxbhn
![Page 36: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/36.jpg)
Percorso massimo in alberi Red-BlackLemma: Un albero Red-Black con n nodi ha
altezza al più 2 log(n + 1)
Dimostrazione: ….
Completiamo la dimostrazione del lemma.
Sia ora h l’altezza dell’albero.
Ma allora, il numero di nodi dell’albero sarà
Portando 1 a sinistra e applicando il logaritmo:
cioè
12)12( 2)( hxbhn
2)1log( hn )1log(2 nh
![Page 37: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/37.jpg)
Costo operazioni su alberi Red-Black
Teorema: In un albero Red-Black le operazioni di ricerca, inserimento e cancellazione hanno costo O(log(n)).
Dimostrazione: Conseguenza diretta del Lemma precedente e dal fatto che tutte le operazioni hanno costo O(h), con h l’altezza dell’albero.
![Page 38: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/38.jpg)
Violazione delle proprietà per inserimento
• Durante la costruzione di un albero Red-Black, quando un nuovo nodo viene inserito è possibile che le condizioni di bilancia-mento 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 e Rotazione sinistra;
![Page 39: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/39.jpg)
Alberi Red-Black: Rotazione destra
sinistro
key
destro
colore
padre
Nodo
Rotazione col figlio destroRotazione va da destra a sinistraIl libro la chiama Rotazione a Sinistra
y
x
Padre del sottoalbero
![Page 40: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/40.jpg)
Alberi Red-Black: Rotazione destra
sinistro
key
destro
colore
padre
Nodo
Rotazione col figlio destroRotazione va da destra a sinistraIl libro la chiama Rotazione a Sinistra
y
x
Padre del sottoalbero
![Page 41: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/41.jpg)
Alberi Red-Black: Rotazione destra
Rotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
sinistro
key
destro
colore
padre
Nodo
Assunzione:destro[x ] NIL
Rotazione col figlio destroRotazione va da destra a sinistraIl libro la chiama Rotazione a Sinistra
![Page 42: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/42.jpg)
Rotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
Alberi Red-Black: Rotazione destra
y
x
Padre del sottoalbero
![Page 43: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/43.jpg)
Rotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
Alberi Red-Black: Rotazione destra
y
x
Padre del sottoalbero
![Page 44: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/44.jpg)
Rotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
Alberi Red-Black: Rotazione destra
y
x
Padre del sottoalbero
![Page 45: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/45.jpg)
Rotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
Alberi Red-Black: Rotazione destra
y
x
Padre del sottoalbero
![Page 46: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/46.jpg)
Rotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
Alberi Red-Black: Rotazione destra
y
x
Padre del sottoalbero
![Page 47: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/47.jpg)
Alberi Red-Black: Rotazione destraRotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y yx
Padre del sottoalbero
![Page 48: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/48.jpg)
Alberi Red-Black: Rotazione destra
Rotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
y
x
Padre del sottoalbero
![Page 49: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/49.jpg)
Alberi Red-Black: Rotazione destraRotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
y
Padre del sottoalbero
x
![Page 50: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/50.jpg)
Alberi Red-Black: Rotazione destraRotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
Padre del sottoalbero
x
y
![Page 51: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/51.jpg)
Alberi Red-Black: Rotazione destraRotazione-destra(T,x : albero-RB) y = destro[x ] destro[x ] = sinistro[y ] IF sinistro[y ] NIL THEN padre[sinistro[y ]] = x padre[y ] = padre[x ] IF padre[x ] = NIL THEN root[T ] = y ELSE IF x = sinistro[padre[x ]] THEN sinistro[padre[x ]] = y ELSE destro[padre[x ]] = y sinistro[y ] = x padre[x ] = y
Padre del sottoalbero
x
y
![Page 52: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/52.jpg)
Inserimento in alberi Red-Black
Inseriamo un nuovo nodo x usando la stessa procedura usata per gli alberi binari di ricerca
Coloriamo il nuovo nodo di rossoCi spostiamo verso l’alto lungo il percorso di
inserimento per ripristinare la proprietà Red-Black:spostiamo le violazioni verso l’alto rispettando il
vincolo 4 (mantenendo l’altezza nera dell’albero)Al termine, coloriamo la radice di nero.
Le operazioni di ripristino sono necessarie solo quando due nodi consecutivi sono rossi!
![Page 53: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/53.jpg)
Inserimento in alberi Red-Black
Le operazioni di ripristino sono necessarie solo quando due nodi consecutivi sono rossi!
Se la radice è sempre nera, non si presenta mai la necessità di ribilanciare l’albero lungo percorsi che contengono meno di tre nodi!
Non si possono, infatti, verificare violazioni!
5
3
Nil Nil
Nil5
3
Nil Nil
6
Nil Nil
6Nodo da inserire
Radice Radice
![Page 54: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/54.jpg)
Ribilanciamenti: casi 1-3
C
A D
B x
y
B
x
C
A D
y
caso 1
Caso 1: il figlio y del padre del padre di x è rosso
x è il nodo modificato che provoca lo sbilanciamento Red-Black
y è il figlio del padre del padre di x
![Page 55: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/55.jpg)
Ribilanciamenti: casi 1-3
C
A D
B x
y
B
x
C
A D
y
B
x
C
A y
caso 1
caso 2
Questa radiceè nera
Caso 2: il figlio y del padre del padre di x è nero x è un filgio destro
![Page 56: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/56.jpg)
Ribilanciamenti: casi 1-3
C
A D
B x
y
B
x
C
A D
y
B
x
C
A y
C
B
A
x
y
caso 1
caso 2caso 3
La radice diy è neraLa radice di
y è nera
Caso 3: il figlio y del padre del padre di x è nero x è un filgio sinistro
![Page 57: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/57.jpg)
Inserimento in alberi RB: Caso 1Caso 1: il figlio y del
padre del padre di x è rosso
Tutti i sono sottoalberi di uguale altezza nera
C
A D
B
x
y
Cambiamo i colori di alcuni nodi, preservando vincolo 4: tutti i percorsi sotto a questi nodi hanno altezza nera uguale.
Poi si continua verso l’alto facendo del padre del padre di x il nuovo x
caso 1C
A D
B
x
![Page 58: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/58.jpg)
Inserimento in alberi RB: Caso 1y = destro[padre[padre[x]]]
IF colore[y] = ROSSO
THEN colore[padre[x]] = NERO
colore[y] = NERO
colore[padre[padre[y]]] = ROSSO
x = padre[padre[x]]
Caso 1: il figlio y del padre del padre di x è rosso
Tutti i sono sottoalberi di uguale altezza nera
C
A D
B
x
y
Cambiamo i colori di alcuni nodi, preservando vincolo 4: tutti i percorsi sotto a questi nodi hanno altezza nera uguale.
Poi si continua verso l’alto facendo del padre del padre di x il nuovo x
![Page 59: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/59.jpg)
Inserimento in alberi RB: Caso 1y = destro[padre[padre[x]]]
IF colore[y] = ROSSO
THEN colore[padre[x]] = NERO
colore[y] = NERO
colore[padre[padre[y]]] = ROSSO
x = padre[padre[x]]
C
A D
B
C
A D
B
y
Cambiamo i colori di alcuni nodi, preservando vincolo 4: tutti i percorsi sotto hanno altezza nera uguale.
Poi si continua verso l’alto facendo del padre del padre di x il nuovo x
caso 1y
x x
Caso 1: il figlio y del padre del padre di x è rosso
Tutti i sono sottoalberi di uguale altezza nera
![Page 60: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/60.jpg)
Inserimento in alberi RB: Caso 1y = destro[padre[padre[x]]]
IF colore[y] = ROSSO
THEN colore[padre[x]] = NERO
colore[y] = NERO
colore[padre[padre[y]]] = ROSSO
x = padre[padre[x]]
C
A D
B
C
A D
B
y
Cambiamo i colori di alcuni nodi, preservando vincolo 4: tutti i percorsi sotto hanno altezza nera uguale.
Poi si continua verso l’alto facendo del padre del padre di x il nuovo x
caso 1y
x
x
Poiché il padre di C può essere rosso, può essere necessario ripri-stinare la proprietà RB più in alto
![Page 61: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/61.jpg)
B
x
Inserimento in alberi RB: Caso 1
C
A D
C
A D
y
x
Si eseguono le stesse azioni sia quando x è un figlio sinistro o un figlio destro
B
caso 1
y = destro[padre[padre[x]]]
IF colore[y] = ROSSO
THEN colore[padre[x]] = NERO
colore[y] = NERO
colore[padre[padre[y]]] = ROSSO
x = padre[padre[x]]
Caso 1: il figlio y del padre del padre di x è rosso
Tutti i sono sottoalberi di uguale altezza nera
![Page 62: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/62.jpg)
B
x
Inserimento in alberi RB: Caso 2Caso 2:• il figlio y del padre del padre
di x è nero• x è un filgio destro• Trasformiamo nel caso 3
con una rotazione destra
C
A y
Trasformiamo il caso 2 nel caso 3 (x è figlio sinistro) con una rotazione destra. Ciò preserva il vincolo 4: tutti i percorsi sotto x
contengonolo stesso numero di nodi neri
C
B
A
x
caso 2y
![Page 63: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/63.jpg)
B
x
Inserimento in alberi RB: Caso 2
IF x = destro[padre[x]]
THEN x = padre[x]
rotazione-destra(T,x)
// continua con caso 3
Caso 2:• il figlio y del padre del padre
di x è nero• x è un filgio destro• Trasformiamo nel caso 3
con una rotazione destra
C
A ycaso 2
Trasformiamo il caso 2 nel caso 3 (x è figlio sinistro) con una rotazione destra. Ciò preserva il vincolo 4: tutti i percorsi sotto x
contengonolo stesso numero di nodi neri
B
x
C
A y
![Page 64: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/64.jpg)
B
x
Inserimento in alberi RB: Caso 2
IF x = destro[padre[x]]
THEN x = padre[x]
rotazione-destra(T,x)
// continua con caso 3
C
A C
By
A
x
caso 2
y
Trasformiamo il caso 2 nel caso 3 (x è figlio sinistro) con una rotazione destra. Ciò preserva il vincolo 4: tutti i percorsi sotto x
contengonolo stesso numero di nodi neri
Caso 2:• il figlio y del padre del padre
di x è nero• x è un filgio destro• Trasformiamo nel caso 3
con una rotazione destra
![Page 65: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/65.jpg)
Inserimento in alberi RB: Caso 3
Caso 3:• il figlio y del padre
del padre di x è nero• x è un filgio sinistro• Cambiare colori e
rotazione sinistra
caso 3C
B
A
x
y
Eseguiamo alcuni cambi di colore e facciamo una rotazione sinistra. Di nuovo, preserviamo il vincolo 4: tutti i
percorsi sotto x contengono lo stesso numero di nodi neri.
B
Ax
C
![Page 66: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/66.jpg)
Inserimento in alberi RB: Caso 3
colore[padre[x]] = NERO
colore[padre[padre[x]]] = ROSSO
rotazione-sinistra(T,padre[padre[x]])
Caso 3:• il figlio y del padre
del padre di x è nero• x è un filgio sinistro• Cambiare colori e
rotazione sinistra
caso 3C
B
A
x
y
Eseguiamo alcuni cambi di colore e facciamo una rotazione sinistra. Di nuovo, preserviamo il vincolo 4: tutti i
percorsi sotto x contengono lo stesso numero di nodi neri.
C
B
A
x
y
![Page 67: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/67.jpg)
Inserimento in alberi RB: Caso 3
colore[padre[x]] = NERO
colore[padre[padre[x]]] = ROSSO
rotazione-sinistra(T,padre[padre[x]])
caso 3C
B
A
x
y
Eseguiamo alcuni cambi di colore e facciamo una rotazione sinistra. Di nuovo, preserviamo il vincolo 4: tutti i
percorsi sotto x contengono lo stesso numero di nodi neri.
C
B
A
x
y
Questa radiceè nera
Caso 3:• il figlio y del padre
del padre di x è nero• x è un filgio sinistro• Cambiare colori e
rotazione sinistra
![Page 68: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/68.jpg)
Inserimento in alberi RB: Caso 3
colore[padre[x]] = NERO
colore[padre[padre[x]]] = ROSSO
rotazione-sinistra(T,padre[padre[x]])
B
Ax
caso 3C
B
A
x
y C
Eseguiamo alcuni cambi di colore e facciamo una rotazione sinistra. Di nuovo, preserviamo il vincolo 4: tutti i
percorsi sotto x contengono lo stesso numero di nodi neri.
yQuesta radice
è nera
Caso 3:• il figlio y del padre
del padre di x è nero• x è un filgio sinistro• Cambiare colori e
rotazione sinistra
![Page 69: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/69.jpg)
Inserimento in alberi RB: Casi 4-6
• I casi 1-3 assumono che il padre di x sia un figlio sinistro
• Se il padre di x è un figlio destro si applicano i casi 4-6 che sono simmetrici (scambiamo sinistro con destro e viceversa).
L’estensione dell’algoritmo ai casi 4-6 è lasciato come esercizio
![Page 70: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/70.jpg)
Inserimento in alberi Red-BlackRB-Inserisci(T,x : albero-RB) ABR-Inserisci(T,x) colore[x] = ROSSO WHILE (x root[T] AND colore[padre[x]] = ROSSO) DO IF padre[x] = sinistro[padre[padre[x]]] THEN y = destro[padre[padre[x]]] IF colore[y] = ROSSO THEN colore[padre[x]] = NERO colore[y] = NERO colore[padre[padre[y]]] = ROSSO x = padre[padre[x]] ELSE IF x = destro[padre[x]] THEN x = padre[x] rotazione-destra(T,x) colore[padre[x]] = NERO colore[padre[padre[x]]] = ROSSO rotazione-sinistra(T,padre[padre[x]]) ELSE {come il THEN ma con destro e sinistro scambiati} colore[root[T]] = NERO
![Page 71: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/71.jpg)
Inserimento in alberi Red-BlackRB-Inserisci(T,x : albero-RB) ABR-Inserisci(T,x) colore[x] = ROSSO WHILE (x root[T] AND colore[padre[x]] = ROSSO) DO IF padre[x] = sinistro[padre[padre[x]]] THEN y = destro[padre[padre[x]]] IF colore[y] = ROSSO THEN colore[padre[x]] = NERO colore[y] = NERO colore[padre[padre[y]]] = ROSSO x = padre[padre[x]] ELSE IF x = destro[padre[x]] THEN x = padre[x] rotazione-destra(T,x) colore[padre[x]] = NERO colore[padre[padre[x]]] = ROSSO rotazione-sinistra(T,padre[padre[x]]) ELSE {come il THEN ma con destro e sinistro scambiati} colore[root[T]] = NERO
Caso I
![Page 72: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/72.jpg)
Inserimento in alberi Red-BlackRB-Inserisci(T,x : albero-RB) ABR-Inserisci(T,x) colore[x] = ROSSO WHILE (x root[T] AND colore[padre[x]] = ROSSO) DO IF padre[x] = sinistro[padre[padre[x]]] THEN y = destro[padre[padre[x]]] IF colore[y] = ROSSO THEN colore[padre[x]] = NERO colore[y] = NERO colore[padre[padre[y]]] = ROSSO x = padre[padre[x]] ELSE IF x = destro[padre[x]] THEN x = padre[x] rotazione-destra(T,x) colore[padre[x]] = NERO colore[padre[padre[x]]] = ROSSO rotazione-sinistra(T,padre[padre[x]]) ELSE {come il THEN ma con destro e sinistro scambiati} colore[root[T]] = NERO
Caso I
Casi II e III
![Page 73: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/73.jpg)
Inserimento in alberi Red-BlackRB-Inserisci(T,x : albero-RB) ABR-Inserisci(T,x) colore[x] = ROSSO WHILE (x root[T] AND colore[padre[x]] = ROSSO) DO IF padre[x] = sinistro[padre[padre[x]]] THEN y = destro[padre[padre[x]]] IF colore[y] = ROSSO THEN colore[padre[x]] = NERO colore[y] = NERO colore[padre[padre[y]]] = ROSSO x = padre[padre[x]] ELSE IF x = destro[padre[x]] THEN x = padre[x] rotazione-destra(T,x) colore[padre[x]] = NERO colore[padre[padre[x]]] = ROSSO rotazione-sinistra(T,padre[padre[x]]) ELSE {come il THEN ma con destro e sinistro scambiati} colore[root[T]] = NERO
Caso I
Caso II
Caso III
![Page 74: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/74.jpg)
Inserimento in alberi Red-Black: I
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
16
T
x
Il padre è NERO, il nuovo nodo x diventa ROSSO
Nil Nil
![Page 75: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/75.jpg)
Inserimento in alberi Red-Black: I
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
16
T
x
Il padre è NERO, il nuovo nodo x diventa ROSSONessun Cambiamento
Non cambia l’altezza neradi nessun nodo!
Nil Nil
![Page 76: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/76.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
42
x
16
Nil Nil
Nil Nil
![Page 77: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/77.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
xVincolo 3 è violato
Caso I: L’altro figlio del padre del padre di x è rosso
Nil Nil
![Page 78: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/78.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
x
Nil Nil
Caso I: L’altro figlio del padre del padre di x è rosso
•Coloriamo di nero il padre di x
![Page 79: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/79.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
x
Nil Nil
Caso I: L’altro figlio del padre del padre di x è rosso
•Coloriamo di nero padre di x •Coloriamo di nero il figlio del padre del padre di x
![Page 80: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/80.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
x
Nil Nil
Caso I: L’altro figlio del padre del padre di x è rosso
•Coloriamo di nero padre di x •Coloriamo di nero il figlio del padre del padre di x•Coloriamo di rosso il padre del padre di x
![Page 81: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/81.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
x
Nil Nil
Vincolo 3 è ripristinatoVincolo 4 è ripristinato
Caso I: L’altro figlio del padre del padre di x è rosso
Il padre del padre di x è il nuovo x
![Page 82: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/82.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
x
Caso III: L’altro figlio del padre del padre di x è nero
Nil Nil
Vincolo 3 è nuovamente violato
tra il nuovo x e suo padre
![Page 83: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/83.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
x
Nil Nil
•Coloriamo di nero il padre di x
Caso III: L’altro figlio del padre del padre di x è nero
![Page 84: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/84.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
x
Nil Nil
Caso III: L’altro figlio del padre del padre di x è nero
•Coloriamo di nero il padre di x•Coloriamo di rosso padre del padre di x
![Page 85: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/85.jpg)
Inserimento in alberi Red-Black: II
30
70
8560
80
10
90
15
20
50
40 55
65Nil Nil Nil
Nil NilNil
Nil Nil Nil Nil NilNil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
x
Nil Nil
Caso III: L’altro figlio del padre del padre di x è nero
•Coloriamo di nero il padre di x•Coloriamo di rosso padre del padre di x•Rorazione sinistra
![Page 86: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/86.jpg)
Inserimento in alberi Red-Black: II
30
70
85
60
80
10
90
15
20 50
40 55 65Nil Nil Nil
Nil NilNil Nil
Nil Nil Nil Nil
Nil
TSe il padre è ROSSO, il nuovo nodo è ROSSO
Nil
42
x
Nil Nil
Poiché il padre di x sarà sempre nero, abbiamo finito
Vincolo 3 è ripristinatoVincolo 4 è ripristinato
![Page 87: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/87.jpg)
Inserimento in alberi Red-Black: II
30
70
85
60
80
10
90
15
20 50
40 55 65Nil Nil Nil
Nil NilNil Nil
Nil Nil Nil Nil
Nil
T
Nil
42
x
Nil Nil
L’unico caso un cui si procede a ripristinare verso l’alto è il caso I. Negli altri 2
casi, il padre di x sarà sempre nero, si esce quindi
dal WHILE e si termina
![Page 88: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/88.jpg)
Cancellazione in RB
• L’algoritmo di cancellazione per alberi RB è costruito sull’algoritmo di cancellazione per alberi binari di ricerca
• Useremo una variante con delle sentinelle Nil[T], una per ogni nodo NIL (perché?), per semplificare l’algoritmo
• 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é?)
![Page 89: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/89.jpg)
Cancellazione in RBRB-Cancella(T,z:albero-RB) IF (sinistro[z] = Nil[T] OR destro[z] = Nil[T]) THEN y = z ELSE y = ARB-Successore(z) IF sinistro[y] Nil[T] THEN x = sinistro[y] ELSE x = destro[y] IF x Nil[T] THEN padre[x]=padre[y] IF padre[y] = Nil[T] THEN Root[T] = x ELSE IF y = sinistro[padre[y]] THEN sinistro[padre[y]]=x ELSE destro[padre[y]]=x IF y z THEN “copia i campi di y in z” IF colore[y ] = NERO THEN RB-Fix-Cancella(T,x) return y
![Page 90: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/90.jpg)
Cancellazione in RBRB-Cancella(T,z:albero-RB) IF (sinistro[z] = Nil[T] OR destro[z] = Nil[T]) THEN y = z ELSE y = ARB-Successore(z) IF sinistro[y] Nil[T] THEN x = sinistro[y] ELSE x = destro[y] IF x Nil[T] THEN padre[x]=padre[y] IF padre[y] = Nil[T] THEN Root[T] = x ELSE IF y = sinistro[padre[y]] THEN sinistro[padre[y]]=x ELSE destro[padre[y]]=x IF y z THEN “copia i campi di y in z” IF colore[y ] = NERO THEN RB-Fix-Cancella(T,x) return y
caso III
casi I e II
y è il nodo da eli-minare e x è il suo sostituto
y è sostituito da x
![Page 91: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/91.jpg)
Cancellazione in RB
• Dobbiamo ribilanciare se il nodo cancellato è nero (perché è cambiata l’altezza nera)
• Possiamo immaginare di colorare di nero il nodo x che sostituisce il nodo cancellato y
• In tal modo la cancellazione non viola più il vincolo 4 ...
• … ma potrebbe violare il vincolo 1 (perché?)
• L’algoritmo RB-Fix-Cancella(T,x) tenta di ripristinare il vincolo 1 con rotazioni e cambia-menti di colore:• ci sono 4 casi possibili (e 4 simmetrici)
![Page 92: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/92.jpg)
Cancellazione in RB
B
A D
Cx w
E
Il nodo x (cioè A nell’esempio) è bordato di rosso ad indicare che è il nodo con un nero in più da aggiungere (e ridistribuire) nell’albero
Caso 1: fratello rosso, padre nero
![Page 93: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/93.jpg)
Cancellazione in RB
B
A D
Cx w
E
Caso 1: fratello rosso, padre nero
B
A D
Cx w
E
c
Caso 2
Il nodo c (cioè B nell’esempio) può essere sia rosso che nero!
: fratello nero con figli neri
![Page 94: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/94.jpg)
Cancellazione in RB
B
A D
Cx w
E
Caso 1
B
A D
Cx w
E
c
Caso 2
B
A D
Cx w
E
c
Caso 3: fratello nero con figlio sin. rosso
: fratello nero con figli neri
B
A D
Cx w
E
c
c’
Caso 4: fratello nero con figlio des. rosso
: fratello rosso, padre nero
![Page 95: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/95.jpg)
Cancellazione in RB: caso 1
B
A D
Cx w
A
x
D
B E
caso 1
E
C
w
colore[padre[x]] = ROSSOcolore[w] = NEROrotazione-destra(T,padre[x])w = destro[padre[x]]
• Il fratello w di x è rosso• w deve avere figli neri • cambiamo i colori di w e del padre di x e li ruotiamo tra loro
Non violiamo né il vincolo 3 né il 4 e ci riduciamo ad uno degli altri casi
![Page 96: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/96.jpg)
Cancellazione in RB: caso 2
B
A D
Cx w
caso 2
E
B
A D
C
x
E
cc
colore[w] = ROSSOx = padre[x]
• Il fratello w di x è nero• w ha in questo caso entrambi i figli neri • cambiamo il colore di w e il nuovo x diventa il padre
Spostiamo il nero in più da x al nuovo x (il padre) e togliamo il nero da w per rispettare vincolo 4
WHILE ripristina se è il caso (se il padre era nero) il bilanciamento, altrimenti si termina.
Se si arriva dal caso 1, B è sicuramente rosso, quindi dopo il caso 2 non c’è più bisogno di ribilanciare, perché ora B ha un solo nero (il nero in più) e può essere semplicemente colorato di nero.
![Page 97: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/97.jpg)
Cancellazione in RB: caso 3
B
A D
Cx w
caso 3
E
B
A
D
C
x
E
cc
w
colore[sinistro[w]] = NEROcolore[w] = ROSSOrotazione-sinistra(T,w)w = destro[padre[x]]
• Il fratello w di x è nero• w ha in questo caso solo il figlo sinistro rosso• cambiamo il colore del sinistro di w e cambiamo quello di w• ruotiamo w col suo figlio sinistroNon violiamo alcun vincolo (3 e 4) e il nuovo fratello si x è ora
nero con figlio sinistro nero, quindi ci portiamo nel caso 4
![Page 98: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/98.jpg)
Cancellazione in RB: caso 4
B
A D
Cx w
caso 4
E
c D
EB
C
x = root[T ]
A
c
c’c’
colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[destro[w]] = NEROrotazione-destra(T,padre[x])x = root[T]
• Il fratello w di x è nero• w ha in questo caso solo il figlo destro rosso• cambiamo i colori opportunamente e con una rotazione del
padre di x con w si elimina il nero in più su xNon violiamo alcun vincolo (3 e 4) e abbiamo finito!
![Page 99: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/99.jpg)
Cancellazione in RB: casi
• Abbiamo visto i 4 casi possibili quando il nodo x che sostituisce y (cancellato) è un figlio sinistro
• Esistono anche i 4 casi simmetrici (con destro e sinistro scembiati) quando x è figlio destro
Esercizio: Illustrare i 4 casi simmetrici e scrivere lo pseudo-codice che li gestisce
![Page 100: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/100.jpg)
Cancellazione in RB: algoritmo FixRB-Fix-Cancella(T,x : albero-RB) WHILE x root[T] AND colore[x] = NERO DO IF x = sinistro[padre[x]] THEN w = destro[padre[x]] IF colore[w] = ROSSO THEN colore[padre[x]] = ROSSO colore[w] = NERO
rotazione-destra(T,padre[x]) w = destro[padre[x]] ELSE IF (colore[sinistro[w]] = NERO AND colore[destro[w]] = NERO) THEN colore[w] = ROSSO
x = padre[x] ELSE IF colore[destro[w]] = NERO THEN colore[sinistro[w]] = NERO colore[w] = ROSSO rotazione-sinistra(T,w)
w = destro[padre[x]] colore[w] = colore[padre[x]] colore[padre[w]] = NERO colore[destro[w]] = NERO rotazione-destra(T,padre[x]) x = root[T] ELSE {come il THEN ma con destro e sinistro scambiati} colore[x] = NERO
![Page 101: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/101.jpg)
Cancellazione in RB: algoritmo FixRB-Fix-Cancella(T,x : albero-RB) WHILE x root[T] AND colore[x] = NERO DO IF x = sinistro[padre[x]] THEN w = destro[padre[x]] IF colore[w] = ROSSO THEN colore[padre[x]] = ROSSO colore[w] = NERO
rotazione-destra(T,padre[x]) w = destro[padre[x]] ELSE IF (colore[sinistro[w]] = NERO AND colore[destro[w]] = NERO) THEN colore[w] = ROSSO
x = padre[x] ELSE IF colore[destro[w]] = NERO THEN colore[sinistro[w]] = NERO colore[w] = ROSSO rotazione-sinistra(T,w)
w = destro[padre[x]] colore[w] = colore[padre[x]] colore[padre[w]] = NERO colore[destro[w]] = NERO rotazione-destra(T,padre[x]) x = root[T] ELSE {come il THEN ma con destro e sinistro scambiati} colore[x] = NERO
caso I
caso II
caso III
caso IV
![Page 102: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/102.jpg)
Cancellazoine in RB: esempio
30
70
85
60
80
10
90
15
20 50
40 55 65Nil Nil Nil
Nil NilNil Nil
Nil Nil Nil Nil
Nil
T
Nil
42
Nil Nil
z
![Page 103: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/103.jpg)
Cancellazoine in RB: esempio
30
70
85
60
80
10
90
15
20 50
55 65Nil Nil Nil
NilNil Nil
Nil Nil Nil Nil
Nil
T
Nil 42
Nil Nil
x
40
Nil
y
Nil
Il colore di x è rossonon si esegue il WHILE
e si colora x di nero
![Page 104: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/104.jpg)
Cancellazoine in RB: esempio
30
70
85
60
80
10
90
15
20 50
55 65Nil Nil Nil
NilNil Nil
Nil Nil Nil Nil
Nil
T
Nil 42
Nil Nil
x
40
Nil
y
Nil
Fatto!Il colore di x è rossonon si esegue il WHILE
e si colora x di nero
![Page 105: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/105.jpg)
Cancellazoine in RB: esempio II
30
70
85
60
80
10
90
15
20 50
55 65Nil Nil Nil
NilNil Nil
Nil Nil Nil Nil
Nil
T
Nil 42
Nil Nil
z
![Page 106: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/106.jpg)
Cancellazoine in RB: esempio II
30
70
85
60
80
10
90
15
20 55
65Nil Nil Nil Nil
Nil
Nil Nil Nil Nil
Nil
T
Nil 42
Nil Nil
x
y
Caso IIsimmetrico
w
colore[w] = ROSSOx = padre[x]
50
![Page 107: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/107.jpg)
Cancellazoine in RB: esempio II
30
70
85
60
80
10
90
15
20
50
55
65Nil Nil Nil Nil
Nil
Nil Nil Nil Nil
Nil
T
Nil 42
Nil Nil
x
y
Caso IIsimmetrico
w
colore[w] = ROSSOx = padre[x]
![Page 108: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/108.jpg)
Cancellazoine in RB: esempio II
30
70
85
60
80
10
90
15
20 55
65Nil Nil Nil Nil
Nil
Nil Nil Nil Nil
Nil
T
Nil 42
Nil Nil
x
y
w
Il colore di x è ora rossosi esce dal WHILE
e si colora x di nero
50
![Page 109: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/109.jpg)
Cancellazoine in RB: esempio II
30
70
85
60
80
10
90
15
20 55
65Nil Nil Nil Nil
Nil
Nil Nil Nil Nil
Nil
T
Nil 42
Nil Nil
x
y
Fatto!
w
Il colore di x è ora rossosi esce dal WHILE
e si colora x di nero
50
![Page 110: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/110.jpg)
Cancellazoine in RB: esempio IIIT
30
70
85
5
60
80
10
90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil Nil NilNil
z
![Page 111: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/111.jpg)
Cancellazoine in RB: esempio IIIT
30
70
85
5
60
80
10 90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil
Nil
Nily
x
![Page 112: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/112.jpg)
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10 90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil
Nil
Nil
x
Caso IIsimmetrico
w
85
y
colore[w] = ROSSOx = padre[x]
![Page 113: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/113.jpg)
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10 90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil
Nil
Nil
x
Caso IIsimmetrico
w
85
y
colore[w] = ROSSOx = padre[x]
![Page 114: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/114.jpg)
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10 90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil
Nil
Nil
x
Caso IIsimmetrico
85
y
colore[w] = ROSSOx = padre[x]
![Page 115: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/115.jpg)
colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[sinistro[w]] = NEROrotazione-sinistra(T,padre[x])x = root[T]
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10 90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil
Nil
Nil
x
Caso IVsimmetrico
w
85
y
![Page 116: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/116.jpg)
colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[sinistro[w]] = NEROrotazione-sinistra(T,padre[x])x = root[T]
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10 90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil
Nil
Nil
x
Caso IVsimmetrico
w
85
y
![Page 117: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/117.jpg)
colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[sinistro[w]] = NEROrotazione-sinistra(T,padre[x])x = root[T]
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10 90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil
Nil
Nil
x
Caso IVsimmetrico
w
85
y
![Page 118: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/118.jpg)
colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[sinistro[w]] = NEROrotazione-sinistra(T,padre[x])x = root[T]
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10 90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil
Nil
Nil
x
Caso IVsimmetrico
w
85
y
![Page 119: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/119.jpg)
colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[sinistro[w]] = NEROrotazione-sinistra(T,padre[x])x = root[T]
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10 90
15
20
50
40 55
65
NilNil
Nil Nil Nil
Nil Nil NilNil
Nil Nil Nil
Nil
Nil
x
Caso IVsimmetrico
w
85
y
![Page 120: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/120.jpg)
colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[sinistro[w]] = NEROrotazione-sinistra(T,padre[x])x = root[T]
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10
90
15
20 50
40 55 65
NilNil
Nil Nil Nil
Nil Nil NilNil Nil
Nil Nil
NilNil
x
w
85
y
Caso IVsimmetrico
![Page 121: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/121.jpg)
colore[w] = colore[padre[x]]colore[padre[w]] = NEROcolore[sinistro[w]] = NEROrotazione-sinistra(T,padre[x])x = root[T]
Cancellazoine in RB: esempio IIIT
30
70
5
60
80
10
90
15
20 50
40 55 65
NilNil
Nil Nil Nil
Nil Nil NilNil Nil
Nil Nil
NilNil
x
85
y
Fatto!w
![Page 122: Algoritmi e Strutture Dati Alberi Bilanciati: Alberi Red-Black](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb57497959361e8c0db4/html5/thumbnails/122.jpg)
Cancellazoine in RB
• L’operazione di cancellazione è concettual-mente complicata!
• Ma efficiente:• il caso 4 è risolutivo e applica 1 sola rotazione• il caso 3 applica una rotazione e passa nel caso 4• il caso 2 non fa rotazioni e passa in uno qualsiasi dei
casi ma salendo lungo il percorso di cancellazione• il caso 1 fa una rotazione e passa in uno degli altri
casi (ma se va nel caso 2, il caso 2 termina)
Quindi
al massimo vengono eseguite 3 rotazioni