Algoritmi e Strutture Dati
Alberi Bilanciati: Alberi Red-Black
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.
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;
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.
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
15
Nil
Nil
Nil
60
20
10
5
70
Nil
Nil
40
50
85
65
80
90
55 Nil Nil Nil Nil Nil Nil
Nil Nil Nil Nil
Alberi Red-Black: esempio I
Vincolo 3 impone che non
possano esserci due nodi
ROSSI adiacenti.
30 (Ma più nodi NERI possono
essere adiacenti.)
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.
15
Nil
Nil
Nil
60
20
10
5
70
Nil
Nil
40
50
85
65
80
90
55 Nil Nil Nil Nil Nil Nil
Nil Nil Nil Nil
Alberi Red-Black: esempio I
Ci sono 3 nodi neri lungo
ogni percorso dalla radice ad un nodo NIL
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
15
Nil
Nil
Nil
60
20
10
5
70
Nil
Nil
40
50
85
65
80
90
55 Nil Nil Nil Nil Nil Nil
Nil Nil Nil Nil
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.
altezza 2
Nil
30
15
70
60
20
10
Nil
5
Questo è anche
un albero AVL
Nil
1 livello di diff.
Nil
Nil
40
50
altezza 3
85
65
80
90
55 Nil Nil Nil Nil Nil Nil
Nil Nil Nil Nil
Alberi Red-Black: esempio II
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
15
60
20
10
Nil
70
Nil
Nil
Questo è ancora
un albero Red-Black
Nil
40
50
85
65
80
90
55 Nil Nil Nil Nil Nil Nil
Nil Nil Nil Nil
Alberi Red-Black: esempio II
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 1
30
15
70
60
20
10
Nil
Ma NON è un
albero AVL!
Nil
Nil
Nil
40
50
altezza 3
85
65
80
90
55 Nil Nil Nil Nil Nil Nil
2 livelli
Nil Nil Nil Nil
Alberi Red-Black: esempio I
Ci sono 3 nodi neri lungo
ogni percorso dalla radice ad un nodo NIL
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
15
Nil
Nil
Nil
60
20
10
5
70
Nil
Nil
40
50
85
65
80
90
55 Nil Nil Nil Nil Nil Nil
Nil Nil Nil Nil
Alberi Red-Black: esempio III
Ci sono 3 nodi neri lungo
ogni percorso dalla radice ad un nodo NIL
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
15
Nil
Nil
Nil
60
20
10
5
70
Nil
Nil
40
50
85
65
80
90
55 Nil Nil Nil Nil Nil Nil
Nil Nil Nil Nil
Alberi Red-Black: esempio IV
Albero RB con 3 nodi neri
lungo ogni percorso dalla
radice ad un nodo NIL
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
15
60
20
10
Nil
70
Nil
Nil
Nil
Nil
50
85
65
80
90
Nil Nil Nil Nil Nil Nil Nil
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.
Stesso albero con 2 nodi
neri lungo ogni percorso
dalla radice ad un nodo
NIL
30
15
60
20
10
Nil
70
Nil
Nil
Nil
Nil
50
85
65
80
90
Nil Nil Nil Nil Nil Nil Nil
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.
Questo albero può essere
un albero Red-Black?
30
15
60
20
10
Nil
70
Nil
Nil
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
Alberi Red-Black: esempio VI
Per vincolo 4 ci possono
essere al più 3 nodi neri
lungo un percorso!
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
15
60
20
10
Nil
70
Nil
Nil
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
Alberi Red-Black: esempio VI
Per vincolo 4 ci possono
essere al più 3 nodi neri
lungo un percorso!
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
15
60
20
10
Nil
70
Nil
Impossibile!
Perché...
Nil
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
Alberi Red-Black: esempio VI
Per vincolo 4 ci possono
essere al più 3 nodi neri
lungo un percorso!
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
15
60
20
10
Nil
70
Nil
Impossibile!
Perché dovremmo
violare vincolo 3
Nil
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
Alberi Red-Black: esempio VI
Per vincolo 4 ci possono
essere al più 3 nodi neri
lungo un percorso!
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
15
60
20
10
Nil
70
Nil
Nil
Quindi uno di questi
due nodi deve essere
rosso
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
Alberi Red-Black: esempio VI
Per vincolo 4 ci possono
essere al più 3 nodi neri
lungo un percorso!
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
15
60
20
10
Nil
70
Nil
Nil
Esistono due percorsi
con 2 soli nodi neri
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
Alberi Red-Black: esempio VI
Per vincolo 4 ci possono
essere al più 3 nodi neri
lungo un percorso!
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
15
60
20
10
Nil
70
Nil
Nil
Esiste un percorso
con 2 soli nodi neri
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
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.
Per vincolo 4 ci possono
essere al più 3 nodi neri
lungo un percorso!
30
15
60
20
10
Nil
70
Nil
Nil
Esiste un percorso
con 2 soli nodi neri
Nil
50
85
Nil
Nil Nil
Questo caso è
40
55 impossibile perchè
un percorso ha 3 neri
Nil Nil Nil Nil
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
Per vincolo 4 e il vincolo
3, ci possono essere al
più 2 nodi neri lungo un
percorso!
15
60
20
10
Nil
70
Nil
Nil
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
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
Per vincolo 4 e il vincolo
3, ci possono essere al
più 2 nodi neri lungo un
percorso!
15
60
20
10
Nil
70
Nil
Questa sarebbe
l’unica possibilità!
Nil
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
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
Per vincolo 4 e il vincolo
3, ci possono essere al
più 2 nodi neri lungo un
percorso!
15
60
20
10
Nil
70
Nil
Impossibile!
Perché dovremmo
violare vincolo 4
Nil
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
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.
Questo albero NON può
essere un albero RedBlack!
30
15
60
20
10
Nil
70
Nil
Nil
A meno che l’albero
non venga ristrutturato
(tramite rotazioni)
Nil
40
85
Nil
50
55
Nil Nil Nil Nil
Nil Nil
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.
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
bh( x)
nodi interni
2
1
dove bh(x) è l’altezza nera di x.
L’induzione sarà sull’altezza di x.
Percorso massimo in alberi Red-Black
Il sottoalbero con radice x ha al meno
bh( x)
2
1
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:
2
bh( x )
1  2 1  0
0
Percorso massimo in alberi Red-Black
Il sottoalbero con radice x ha al meno
bh( x)
2
1
nodi interni
15 bh(x)
dove bh(x) è l’altezza nera di x.
bh(x)-1 10
20 bh(x)
Passo Induttivo:
Se x sia interno con 2 figli e
15 bh(x)
abbia altezza bh(x)>1
Entrambi i suoi figli avranno
bh(x)-1 10
20 bh(x) -1
altezza bh(x) o bh(x)-1
Percorso massimo in alberi Red-Black
Il sottoalbero con radice x ha al meno
bh( x)
2
1
nodi interni
15 bh(x)
dove bh(x) è l’altezza nera di x.
bh(x)-1 10
20 bh(x)
Passo Induttivo:
Sia x nodo interno con 2 figli
e abbia altezza > 0
15 bh(x)
Entrambi i suoi figli avranno
20 bh(x) -1
altezza nera bh(x) o bh(x)-1 bh(x)-1 10
Entrambi i suoi figli avranno altezza
minore di x, quindi possiamo usare ipotesi induttiva
Percorso massimo in alberi Red-Black
Il sottoalbero con radice x ha al meno
bh( x)
2
1
nodi interni
15 bh(x)
dove bh(x) è l’altezza nera di x.
bh(x)-1 10
20 bh(x)
Passo Induttivo:
Se x sia interno con 2 figli e
abbia altezza >0
15 bh(x)
Entrambi i suoi figli avranno
20 bh(x) -1
altezza nera bh(x) o bh(x)-1 bh(x)-1 10
Ogni figlio avrà almeno
bh( x)1
2
1
nodi interni
Percorso massimo in alberi Red-Black
Il sottoalbero con radice x ha al meno
bh( x)
2
1
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
bh( x)1
2
1
nodi interni
Quindi il sottoalbero con radice x conterrà almeno
(2bh( x)1  1)  (2bh( x)1  1)  1  (2bh( x)  1) nodi interni
Percorso massimo in alberi Red-Black
Il sottoalbero con radice x ha quindi al meno
bh( x)
2
1
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 ).
Percorso massimo in alberi Red-Black
Il sottoalbero con radice x ha al meno
bh( x)
2
1
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à
n  (2bh( x)  1)  2h 2 1
Percorso massimo in alberi Red-Black
Lemma: 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à
n  (2
bh( x)
 1)  2
h2
1
Portando 1 a sinistra e applicando il logaritmo:
log(n  1)  h 2
cioè
h  2 log(n  1)
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.
Violazione delle proprietà per inserimento
• Durante la costruzione di un albero RedBlack, quando un nuovo nodo viene inserito
è 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 e
Rotazione sinistra;
Alberi Red-Black: Rotazione destra
Nodo
Padre del
sottoalbero
key
colore
x

padre
sinistro destro
y


Rotazione col figlio destro
Rotazione va da destra a sinistra
Il libro la chiama Rotazione a Sinistra
Alberi Red-Black: Rotazione destra
Nodo
Padre del
sottoalbero
key
y
padre
sinistro destro
x

colore


Rotazione col figlio destro
Rotazione va da destra a sinistra
Il libro la chiama Rotazione a Sinistra
Alberi Red-Black: Rotazione destra
Nodo
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
Rotazione col figlio destro
Rotazione va da destra a sinistra
Il libro la chiama Rotazione a Sinistra
key
colore
padre
sinistro destro
Assunzione:
destro[x ]  NIL
Alberi Red-Black: Rotazione destra
Rotazione-destra(T,x : albero-RB)
y = destro[x ]
Padre del
destro[x ] = sinistro[y ]
sottoalbero
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
x
y



Alberi Red-Black: Rotazione destra
Rotazione-destra(T,x : albero-RB)
y = destro[x ]
Padre del
destro[x ] = sinistro[y ]
sottoalbero
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
x
y



Alberi Red-Black: Rotazione destra
Rotazione-destra(T,x : albero-RB)
y = destro[x ]
Padre del
destro[x ] = sinistro[y ]
sottoalbero
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
x
y



Alberi Red-Black: Rotazione destra
Rotazione-destra(T,x : albero-RB)
y = destro[x ]
Padre del
destro[x ] = sinistro[y ]
sottoalbero
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
x
y



Alberi Red-Black: Rotazione destra
Rotazione-destra(T,x : albero-RB)
y = destro[x ]
Padre del
destro[x ] = sinistro[y ]
sottoalbero
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
x
y



Alberi Red-Black: Rotazione destra
Rotazione-destra(T,x : albero-RB)
y = destro[x ]
destro[x ] = sinistro[y ]
Padre del
IF sinistro[y ]  NIL
sottoalbero
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
x

y


Rotazione-destra(T,x : albero-RB)
y Alberi
= destro[x
]
Red-Black:
Rotazione destra
destro[x ] = sinistro[y ]
IF sinistro[y ]  NIL
Padre del
THEN padre[sinistro[y ]] = x
sottoalbero
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



Rotazione-destra(T,x : albero-RB)
y =Alberi
destro[x
]
Red-Black:
Rotazione destra
destro[x ] = sinistro[y ]
IF sinistro[y ]  NIL
Padre del
THEN padre[sinistro[y ]] = x
padre[y ] = padre[x ]
sottoalbero
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



Rotazione-destra(T,x : albero-RB)
y =Alberi
destro[x
]
Red-Black:
Rotazione destra
destro[x ] = sinistro[y ]
IF sinistro[y ]  NIL
Padre del
THEN padre[sinistro[y ]] = x
padre[y ] = padre[x ]
sottoalbero
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



Rotazione-destra(T,x : albero-RB)
y =Alberi
destro[x
]
Red-Black:
Rotazione destra
destro[x ] = sinistro[y ]
IF sinistro[y ]  NIL
Padre del
THEN padre[sinistro[y ]] = x
padre[y ] = padre[x ]
sottoalbero
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



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 rosso
 Ci spostiamo verso l’alto lungo il percorso di
inserimento per ripristinare la proprietà RedBlack:
 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!
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!
Radice
Radice
5
3
Nil
5
Nil
Nil
Nodo da inserire
3
Nil
6
6
Nil
Nil
Nil
Ribilanciamenti: casi 1-3
C
caso 1
A

A
D y
B x

C



B x

D y



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

Ribilanciamenti: casi 1-3
C
caso 1
A






A
B x

D y




caso 2
C
y
B x

A
D y
B x

C

Questa radice
è nera
Caso 2: il figlio y del padre del padre
di x è nero x è un filgio destro
Ribilanciamenti: casi 1-3
C
caso 1
A

A
D y
B x





B x




caso 2

A
C
y
B
B x

D y
Caso 3: il figlio y del padre del padre
di x è nero x è un filgio sinistro
C

C

La radice di
y è nera
A x



caso 3
y
La radice di
y è nera
Inserimento in alberi RB: Caso 1
Caso 1: il figlio y del
padre del padre di x è
rosso
Tutti i  sono sottoalberi
di uguale altezza nera
C
caso 1
A

A
D y
B x

C x




D
B




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
Inserimento in alberi RB: 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
C
A

D y
B x




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
Inserimento in alberi RB: 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]]
C

C
A
D y
B x

Tutti i  sono sottoalberi
di uguale altezza nera
caso 1
A

Caso 1: il figlio y del
padre del padre di x è
rosso



D y
B x




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
Inserimento in alberi RB: 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]]
C
A
D y
B x

C x
caso 1
A


Poiché il padre di C
può essere rosso, può
essere necessario ripristinare la proprietà RB
più in alto



D y
B




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
Inserimento in alberi RB: 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]]
C


C x
A
D y

Tutti i  sono sottoalberi
di uguale altezza nera
caso 1
A
B x
Caso 1: il figlio y del
padre del padre di x è
rosso



B

D


Si eseguono le stesse azioni sia quando x è un figlio
sinistro o un figlio destro

Inserimento in alberi RB: Caso 2
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

y
B
B x


C
caso 2
A x


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
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

B x


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

caso 2
y
A x

y
B


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
Inserimento in alberi RB: Caso 2
Caso 2:
• il figlio y del padre del padre
di x è nero
• x è un filgio destro
• Trasformiamo nel caso 3
con una rotazione destra
IF x = destro[padre[x]]
THEN x = padre[x]
rotazione-destra(T,x)
// continua con caso 3
C
A x

y
B
B

C
caso 2
A x



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
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
C
B
A x


y
B
caso 3
x A

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.
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
colore[padre[x]] = NERO
colore[padre[padre[x]]] = ROSSO
rotazione-sinistra(T,padre[padre[x]])
C
B
A x



y
C
caso 3
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.
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
colore[padre[x]] = NERO
colore[padre[padre[x]]] = ROSSO
rotazione-sinistra(T,padre[padre[x]])
C
B
A x



y
C
caso 3
Questa radice
è nera
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.
Inserimento in alberi RB: Caso 3
colore[padre[x]] = NERO
colore[padre[padre[x]]] = ROSSO
rotazione-sinistra(T,padre[padre[x]])
C
B
A x



y
Caso 3:
• il figlio y del padre
del padre di x è nero
• x è un filgio sinistro
• Cambiare colori e
rotazione sinistra
B
caso 3
Questa radice
è nera
x A

C



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.
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
Inserimento in alberi Red-Black
RB-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
Inserimento in alberi Red-Black
RB-Inserisci(T,x : albero-RB)
ABR-Inserisci(T,x)
colore[x] = ROSSO
WHILE (x  root[T] AND colore[padre[x]] = ROSSO) DO
Caso I
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
Inserimento in alberi Red-Black
RB-Inserisci(T,x : albero-RB)
ABR-Inserisci(T,x)
colore[x] = ROSSO
WHILE (x  root[T] AND colore[padre[x]] = ROSSO) DO
Caso I
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]]
Casi II e III
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
Inserimento in alberi Red-Black
RB-Inserisci(T,x : albero-RB)
ABR-Inserisci(T,x)
colore[x] = ROSSO
WHILE (x  root[T] AND colore[padre[x]] = ROSSO) DO
Caso I
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]]
Caso II
ELSE IF x = destro[padre[x]]
THEN x = padre[x]
rotazione-destra(T,x)
Caso III
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
Inserimento in alberi Red-Black: I
T
Il padre è NERO, il nuovo
nodo x diventa ROSSO
30
15
60
20
10
Nil
70
Nil
Nil
x
Nil
40
50
85
65
90
55 Nil Nil Nil Nil Nil Nil
16
Nil Nil Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: I
Il padre è NERO, il nuovo
nodo x diventa ROSSO
Nessun Cambiamento
T
30
15
10
Nil
60
20
x
Nil
70
16
Nil Nil
Nil
40
50
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil Nil Nil Nil
Non cambia l’altezza nera
di nessun nodo!
80
Inserimento in alberi Red-Black: II
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
60
20
10
Nil
70
Nil
x
Nil
16
Nil
Nil 40
50
85
65
90
55 Nil Nil Nil Nil Nil Nil
42
Nil Nil Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Caso I: L’altro figlio
del padre del padre
di x è rosso
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
60
20
10
Nil
70
Nil
Vincolo 3 è violato
Nil
Nil
x
50
40
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil 42 Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Caso I: L’altro figlio
del padre del padre
di x è rosso
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
60
20
10
Nil
70
Nil
•Coloriamo di nero
il padre di x
Nil
Nil
x
50
40
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil 42 Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Caso I: L’altro figlio
del padre del padre
di x è rosso
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
60
20
10
Nil
70
Nil
•Coloriamo di nero
padre di x
•Coloriamo di nero
il figlio del padre
del padre di x
Nil
Nil
x
50
40
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil 42 Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Caso I: L’altro figlio
del padre del padre
di x è rosso
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
60
20
10
Nil
70
Nil
Nil
•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
Nil
x
50
40
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil 42 Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Caso I: L’altro figlio
del padre del padre
di x è rosso
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
20
10
Nil
70
Nil
Nil
Vincolo 3 è ripristinato
Vincolo 4 è ripristinato
Il padre del padre
di x è il nuovo x
60
x
Nil
50
40
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil 42 Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Caso III: L’altro figlio
del padre del padre
di x è nero
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
20
10
Nil
70
Nil
Vincolo 3 è
nuovamente violato
tra il nuovo x
e suo padre
Nil
60
x
Nil
50
40
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil 42 Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Caso III: L’altro figlio
del padre del padre
di x è nero
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
20
10
Nil
70
Nil
Nil
•Coloriamo di nero il
padre di x
60
x
Nil
50
40
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil 42 Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Caso III: L’altro figlio
del padre del padre
di x è nero
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
20
10
Nil
70
Nil
Nil
•Coloriamo di nero il
padre di x
•Coloriamo di rosso
padre del padre di x
60
x
Nil
50
40
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil 42 Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Caso III: L’altro figlio
del padre del padre
di x è nero
T
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
15
20
10
Nil
70
Nil
Nil
•Coloriamo di nero il
padre di x
•Coloriamo di rosso
padre del padre di x
•Rorazione sinistra
60
x
Nil
50
40
85
65
90
55 Nil Nil Nil Nil Nil Nil
Nil 42 Nil Nil
Nil Nil
80
Inserimento in alberi Red-Black: II
Se il padre è ROSSO, il
nuovo nodo è ROSSO
30
x
15
Nil
Nil
Nil
Vincolo 3 è ripristinato
Vincolo 4 è ripristinato
60
70
50
20
10
Poiché il padre di x
sarà sempre nero,
abbiamo finito
T
Nil 40
55
65
85
Nil 42 Nil Nil Nil Nil 80
Nil Nil
90
Nil Nil Nil Nil
Inserimento in alberi Red-Black: II
T
30
x
15
20
10
Nil
Nil
Nil
Nil 40
60
70
50
55
65
85
Nil 42 Nil Nil Nil Nil 80 90
L’unico caso un cui si
procede a ripristinare verso
l’alto è il caso I. Negli altri 2
Nil Nil Nil Nil
Nil Nil
casi, il padre di x sarà
sempre nero, si esce quindi
dal WHILE e si termina
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é?)
Cancellazione in RB
RB-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
Cancellazione in RB
casi I e II
RB-Cancella(T,z:albero-RB)
IF (sinistro[z] = Nil[T] OR destro[z] = Nil[T])
THEN y = z
y è il nodo da eliELSE y = ARB-Successore(z)
minare e x è il suo
sostituto
IF sinistro[y]  Nil[T]
THEN x = sinistro[y]
ELSE x = destro[y]
y è sostituito da x
IF x  Nil[T] THEN padre[x]=padre[y]
IF padre[y] = Nil[T]
caso III
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
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 cambiamenti di colore:
• ci sono 4 casi possibili (e 4 simmetrici)
Cancellazione in RB
Il nodo x (cioè A nell’esempio) è bordato
di rosso ad indicare che è il nodo con
Caso 1: fratello rosso, padre nero
un nero in più da aggiungere (e
ridistribuire) nell’albero
B
x

A
D w


C
E
 

Cancellazione in RB
Caso 2: fratello nero con figli neri
Caso 1: fratello rosso, padre nero
B c
B
x

A
x
D w


C

E
 

A
D w


C
E
 
Il nodo c (cioè B nell’esempio) può
essere sia rosso che nero!

Cancellazione in RB
Caso 1 : fratello rosso, padre nero
Caso 2 : fratello nero con figli neri
B c
B
x
A



x
D w
C

E
 
A
D w



C
E
 

Caso 3: fratello nero con figlio sin. rosso Caso 4: fratello nero con figlio des. rosso
B c
x

A
B c
x
D w


C

E
 

A
D w


C c’
 
E

Cancellazione in RB: caso 1
B
x

D
caso 1
A
B
D w


C
A x
E
 



E
C
w



• 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
colore[padre[x]] = ROSSO
colore[w] = NERO
rotazione-destra(T,padre[x])
w = destro[padre[x]]
Cancellazione in RB: caso 2
x
B c
x

A
caso 2
A
D w


C

E
 
B c

D


C
E
 

• 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
Se si 4arriva dal caso 1, B è sicuramente rosso,
WHILE ripristina se è il caso
(sedopo
il padre
era nero)
il bilanciamento,
quindi
il caso
2 non
c’è più bisogno di
altrimenti si termina. ribilanciare, perché ora B ha un solo nero (il
nero in più) e può essere semplicemente
colore[w] = ROSSO
colorato di nero.
x = padre[x]
Cancellazione in RB: caso 3
B c
x

A
caso 3
x A
D w


B c
C

E
 


C

D

• 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 sinistro
Non violiamo alcun vincolo (3 e 4) e il nuovo fratello si x è ora
nero con figlio sinistro nero, quindi ci portiamo nel caso 4
colore[sinistro[w]] = NERO
colore[w] = ROSSO
rotazione-sinistra(T,w)
w = destro[padre[x]]
w
E


Cancellazione in RB: caso 4
B c
x

c
caso 4
A
D w


C c’
D
E
B
E
 
A


c’ C
 


• 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 x
Non violiamo alcun vincolo (3 e 4) e abbiamo finito!
colore[w] = colore[padre[x]]
colore[padre[w]] = NERO
colore[destro[w]] = NERO
rotazione-destra(T,padre[x])
x = root[T]
x = root[T ]

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
Cancellazione in RB: algoritmo Fix
RB-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
Cancellazione in RB: algoritmo Fix
RB-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
caso I
rotazione-destra(T,padre[x])
w = destro[padre[x]]
ELSE IF (colore[sinistro[w]] = NERO AND
colore[destro[w]] = NERO)
THEN colore[w] = ROSSO
caso II
x = padre[x]
ELSE IF colore[destro[w]] = NERO
THEN colore[sinistro[w]] = NERO
colore[w] = ROSSO
caso III
rotazione-sinistra(T,w)
w = destro[padre[x]]
colore[w] = colore[padre[x]]
colore[padre[w]] = NERO
colore[destro[w]] = NERO
caso IV
rotazione-destra(T,padre[x])
x = root[T]
ELSE {come il THEN ma con destro e sinistro scambiati}
colore[x] = NERO
Cancellazoine in RB: esempio
T
30
15
Nil
Nil
70
50
20
10
Nil
60
Nil 40
65
55
85
Nil 42 Nil Nil Nil Nil 80
90
Nil Nil Nil Nil
Nil Nil
z
Cancellazoine in RB: esempio
Il colore di x è rosso
non si esegue il WHILE
e si colora x di nero
T
30
15
60
x
10
Nil
Nil
Nil
70
50
20
Nil 42
55
65
85
Nil Nil Nil Nil Nil Nil 80
40
Nil
y
Nil
90
Nil Nil Nil Nil
Cancellazoine in RB: esempio
Il colore di x è rosso
non si esegue il WHILE
e si colora x di nero
Fatto!
T
30
15
60
x
10
Nil
Nil
Nil
70
50
20
Nil 42
55
65
85
Nil Nil Nil Nil Nil Nil 80
40
Nil
y
Nil
90
Nil Nil Nil Nil
Cancellazoine in RB: esempio II
T
30
15
Nil
Nil
Nil
70
50
20
10
60
z
Nil 42
55
65
85
Nil Nil Nil Nil Nil Nil 80
90
Nil Nil Nil Nil
Cancellazoine in RB: esempio II
Caso II
simmetrico
T
colore[w] = ROSSO
x = padre[x]
30
15
20
10
Nil
60
Nil
Nil
w
70
55
Nil 42
Nil Nil
x
Nil
65
85
Nil Nil 80
90
y
Nil Nil Nil Nil
50
Cancellazoine in RB: esempio II
Caso II
simmetrico
T
colore[w] = ROSSO
x = padre[x]
30
15
20
10
Nil
Nil
Nil
w
60
x
55
Nil 42
Nil Nil
Nil
70
65
85
Nil Nil 80
90
y
Nil Nil Nil Nil
50
Cancellazoine in RB: esempio II
Il colore di x è ora rosso
si esce dal WHILE
e si colora x di nero
T
30
15
20
10
Nil
Nil
Nil
w
60
x
55
Nil 42
Nil Nil
Nil
70
65
85
Nil Nil 80
90
y
Nil Nil Nil Nil
50
Cancellazoine in RB: esempio II
Il colore di x è ora rosso
si esce dal WHILE
e si colora x di nero
Fatto!
T
30
15
20
10
Nil
Nil
Nil
w
60
x
55
Nil 42
Nil Nil
Nil
70
65
85
Nil Nil 80
90
y
Nil Nil Nil Nil
50
Cancellazoine in RB: esempio III
T
30
15
Nil
Nil
Nil
60
20
10
5
70
Nil
Nil 50
40
z
85
65
80
90
55 Nil Nil Nil Nil Nil Nil
Nil Nil Nil Nil
Cancellazoine in RB: esempio III
T
30
15
Nil
Nil
Nil
60
20
10
5
70
Nil
y
85
Nil 50
40
90
65
80
55 Nil Nil Nil Nil
Nil Nil Nil Nil
x
Nil
Cancellazoine in RB: esempio III
T
colore[w] = ROSSO
x = padre[x]
Caso II
simmetrico
30
15
Nil
Nil
Nil
60
20
10
5
70
Nil
y
85
Nil 50
40
w
65
90
80
55 Nil Nil Nil Nil
Nil Nil Nil Nil
x
Nil
Cancellazoine in RB: esempio III
T
colore[w] = ROSSO
x = padre[x]
Caso II
simmetrico
30
15
Nil
Nil
Nil
60
20
10
5
70
Nil
y
85
Nil 50
40
w
65
90
80
55 Nil Nil Nil Nil
Nil Nil Nil Nil
x
Nil
Cancellazoine in RB: esempio III
T
colore[w] = ROSSO
x = padre[x]
Caso II
simmetrico
30
15
Nil
Nil
Nil
Nil
y
85
x
60
20
10
5
70
Nil 50
40
90
65
80
55 Nil Nil Nil Nil
Nil Nil Nil Nil
Nil
Cancellazoine in RB: esempio III
colore[w] = colore[padre[x]]
colore[padre[w]] = NERO
colore[sinistro[w]] = NERO
rotazione-sinistra(T,padre[x])
x = root[T]
T
30
w
15
Nil
5
Nil
Nil
Nil
y
85
70
x
60
20
10
Caso IV
simmetrico
Nil 50
40
90
65
80
55 Nil Nil Nil Nil
Nil Nil Nil Nil
Nil
Cancellazoine in RB: esempio III
colore[w] = colore[padre[x]]
colore[padre[w]] = NERO
colore[sinistro[w]] = NERO
rotazione-sinistra(T,padre[x])
x = root[T]
T
30
w
15
Nil
5
Nil
Nil
Nil
y
85
70
x
60
20
10
Caso IV
simmetrico
Nil 50
40
90
65
80
55 Nil Nil Nil Nil
Nil Nil Nil Nil
Nil
Cancellazoine in RB: esempio III
colore[w] = colore[padre[x]]
colore[padre[w]] = NERO
colore[sinistro[w]] = NERO
rotazione-sinistra(T,padre[x])
x = root[T]
T
30
w
15
Nil
5
Nil
Nil
Nil
y
85
70
x
60
20
10
Caso IV
simmetrico
Nil 50
40
90
65
80
55 Nil Nil Nil Nil
Nil Nil Nil Nil
Nil
Cancellazoine in RB: esempio III
colore[w] = colore[padre[x]]
colore[padre[w]] = NERO
colore[sinistro[w]] = NERO
rotazione-sinistra(T,padre[x])
x = root[T]
T
30
w
15
Nil
5
Nil
Nil
Nil
y
85
70
x
60
20
10
Caso IV
simmetrico
Nil 50
40
90
65
80
55 Nil Nil Nil Nil
Nil Nil Nil Nil
Nil
Cancellazoine in RB: esempio III
colore[w] = colore[padre[x]]
colore[padre[w]] = NERO
colore[sinistro[w]] = NERO
rotazione-sinistra(T,padre[x])
x = root[T]
T
30
w
15
Nil
5
Nil
Nil
Nil
y
85
70
x
60
20
10
Caso IV
simmetrico
Nil 50
40
90
65
80
55 Nil Nil Nil Nil
Nil Nil Nil Nil
Nil
Cancellazoine in RB: esempio III
colore[w] = colore[padre[x]]
colore[padre[w]] = NERO
colore[sinistro[w]] = NERO
rotazione-sinistra(T,padre[x])
x = root[T]
T
30
w
15
Nil
5
Nil
Nil
60
20
10
Nil
y
85
Caso IV
simmetrico
70
50
Nil 40
x
55
90
65
Nil Nil Nil Nil Nil Nil 80
Nil Nil
Nil
Cancellazoine in RB: esempio III
colore[w] = colore[padre[x]]
colore[padre[w]] = NERO
colore[sinistro[w]] = NERO
rotazione-sinistra(T,padre[x])
x = root[T]
T
x
w
30
15
Nil
5
Nil
Nil
60
20
10
Nil
y
85
Fatto!
70
50
Nil 40
55
90
65
Nil Nil Nil Nil Nil Nil 80
Nil Nil
Nil
Cancellazoine in RB
• L’operazione di cancellazione è concettualmente 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