Alberi Rosso-Neri
Algoritmi e Strutture Dati
20 aprile 2001
Alberi Binari di Ricerca
Gli alberi di ricerca binari consentono
l’individuazione di un elemento al proprio
interno in un tempo mediamente proporzionale
all’altezza dell’albero considerato
Costruiamo un albero a partire dalla sequenza:
4, 2, 6, 1, 3, 5, 7
4
2
1
3 = O(log(n))
6
3
5
7
Alberi Binari di Ricerca
Inseriamo gli stessi elementi con un diverso ordine:
1, 2, 3, 4, 5, 6, 7
1
2
3
4
7 = O(n)
5
6
7
Alberi Rosso-Neri
•
Gli alberi Rosso-Neri sono alberi binari
di ricerca estesi
• Ciascun nodo di tali alberi contiene un
campo addizionale che riporta il suo colore
• Le operazioni di inserimento e cancellazione
vengono opportunamente integrate in modo
tale da rendere l’albero binario bilanciato
Un esempio di albero Rosso-Nero
Caratterizzazione
La caratterizzazione degli alberi Rosso-Neri
avviene attraverso la formulazione di
quattro proprietà vincolanti
Proprietà n. 1
Ogni nodo dell’albero è rosso o nero
46
26
21
62
31
51
85
Proprietà n. 2
Ogni foglia dell’albero (NIL) è nera
52
45
NIL
NIL
NIL
Proprietà n.3
Se un nodo è rosso entrambi i suoi
figli sono neri
42
12
78
Proprietà n.4
Dato un nodo, tutti i percorsi discendenti che
raggiungono una foglia contengono lo stesso
numero di nodi neri
65
42
32
26
NIL
73
51
NIL NIL NIL
NIL
NIL
NIL
Proprietà
1. Ogni nodo è rosso o nero
2. Ogni foglia (NIL) è nera
3. Se un nodo è rosso entrambi i suoi figli
sono neri
4. Dato un nodo, tutti i percorsi discendenti che
raggiungono una foglia contengono lo stesso
numero di nodi neri
Osservazione
Proviamo a costruire un albero Rosso-Nero
sbilanciato…
1
2
NIL
NIL
3
NIL
4
NIL
5
NIL
6
NIL
NIL
Osservazione
1
2
NIL
NIL
3
NIL
4
NIL
5
NIL
6
NIL
NIL
Altezza-nero
• Definiamo altezza-nero di un nodo x
(black-height(x)) il numero di nodi neri
che si incontrano in un qualsiasi cammino
discendente da x verso una foglia
• Definiamo l’altezza-nero di un albero
Rosso-Nero come l’altezza-nero della sua
radice
Altezza-nero
black-height(32) = 2
65
42
black-height(42) = 2
black-height(T)
= black-height(65) = 3
32
26
NIL
73
51
NIL NIL NIL
NIL
NIL
NIL
Lemma 1
Un albero Rosso-Nero con n nodi interni ha
altezza al più 2lg(n+1)
Lemma 2
Dato un nodo x appartenente ad un albero
Rosso-Nero, il sottoalbero ivi radicato
contiene almeno 2bh(x)-1 nodi interni
Dimostrazione Lemma 2
Dimostriamo il Lemma 2 per induzione
sull’altezza del nodo x.
Se l’altezza di x è 0, x è una foglia…
questo implica che
Il sottoalbero radicato in x ha 0 = 20-1 nodi
interni
NIL
Dimostrazione Lemma 2
Consideriamo un nodo x che ha altezza > 0,
esso avrà quindi due figli…
Ciascuno dei due figli di x avrà altezza bh(x)
oppure bh(x)-1.
6
6
2
8
2
8
Dimostrazione Lemma 2
Per l’ipotesi induttiva, poiché l’altezza dei figli di
x è inferiore all’altezza di x possiamo affermare
che ciascun figlio ha almeno 2bh(x)-1-1 nodi interni
Quindi, il sottoalbero radicato in x ha almeno
(2bh(x)-1-1) + (2bh(x)-1-1) + 1 nodi interni
(2bh(x)-1-1) + (2bh(x)-1-1) + 1 =
2bh(x)-1 + 2bh(x)-1 –1
=
2*2bh(x)-1 – 1
= 2bh(x) –1
Dimostrazione Lemma 1
Un albero Rosso-Nero con n nodi interni ha
altezza al più 2lg(n+1)
Dim.
Sia h l’altezza dell’albero considerato. La
proprietà 3 degli alberi Rosso-Neri impone
che almeno la metà dei nodi che separano
la radice dalle foglie siano neri.
Questo implica che l’altezza-nero
dell’albero è perlomeno h/2.
Dimostrazione Lemma 1
Dall’applicazione del Lemma 2 possiamo
affermare che il numero di nodi interni n è
maggiore o uguale di 2h/2 –1
n
2h/2 –1
n +1
2h/2
log(n+1)
h
h/2
2lg(n+1)
Alberi Rosso-Neri
Il mantenimento delle proprietà caratterizzanti
gli alberi Rosso-Neri deve essere garantito
in corrispondenza delle comuni operazioni che
vanno a modificare la struttura dell’albero stesso
Le operazioni di inserimento e cancellazione
già viste per gli alberi binari di ricerca vengono
mantenute ed integrate con una successiva
operazione di ribilanciamento
Rotazioni
Ai fini dell’implementazione delle procedure
di ribilanciamento si rivela utile l’introduzione
delle operazioni di left-rotation (rotazione sinistra)
e right-rotation (rotazione destra)
Right-Rotate(T,y)
x
y
a
x
a
y
c
b
Left-Rotate(T,x)
b
c
Rotazione sinistra
z
z
y
x
a
x
y
b
c
a
c
b
Left-Rotate
Left-Rotate(T,x)
a
Yright[x]
right[x] left[y]
If left[y]  NIL
then p[left[y]]  x
p[y]p[x]
If p[x] = NIL
then root[T]  y
else if x = left[p[x]]
then left[p[x]]  y
else right[p[x]]  y
left[y]  x
p[x]  y
z
z
y
x
x
y
b
c
a
c
b
Inserimento
L’algoritmo di inserimento di un nodo x in un
albero Rosso-Nero:
• Inserisce il nuovo nodo nell’albero secondo
il tradizionale algoritmo di inserimento per alberi
binari di ricerca
• Verifica se l’albero risultante viola le proprietà
degli alberi Rosso-Neri
• In caso di violazione, si risale l’albero sino alla
radice operando opportunamente rotazioni e
cambiamenti di colore
Inserimento
L’algoritmo di inserimento che presenteremo
distingue tre possibili casi di intervento per
ripristinare le proprietà degli alberi Rosso-Neri
più altri tre simmetrici
RB-Insert(T,x)
RB-Insert(T,x)
Tree-Insert(T,x)
color[x] RED
While x  root[T] and color[p[x]] = RED
do if p[x] = left[p[p[x]]]
then y  right[p[p[x]]]
if color[y] = RED
then color[p[x]] = BLACK
color[y] = BLACK
color[p[p[x]]] = RED
x p[p[x]]
…
RB-Insert(T,x)
….
else if x = right[p[x]]
then
x  p[x]
Left-Rotate(T,x)
color[p[x]] = BLACK
color[p[p[x]]] = RED
Right-Rotate(T,p[p[x]])
else
….
Color[root[T]]  BLACK
Un esempio 1/3
Inseriamo nell’albero corrente l’elemento x = 24
65
42
32
26
NIL
73
51
NIL NIL NIL
NIL
NIL
NIL
Un esempio 2/3
Ci troviamo nel terzo caso della procedura
di ribilanciamento
65
42
73
p[p[x]]
32
p[x]
26
NIL NIL NIL
x
24
NIL
51
NIL
NIL
NIL
NIL
Un esempio 3/3
65
42
51
26
x
24
73
32
NIL NIL
NIL NIL NIL NIL
NIL
NIL
Cancellazione
L’algoritmo di cancellazione di un nodo x da un
albero Rosso-Nero opera secondo la stessa
filosofia dell’algoritmo di inserimento:
• Cancella il nodo dall’albero secondo il
tradizionale algoritmo di cancellazione per
alberi binari di ricerca
• Verifica se l’albero risultante viola le proprietà
degli alberi Rosso-Neri
• In caso di violazione, si risale l’albero sino alla
radice operando opportunamente rotazioni e
cambiamenti di colore
Cancellazione
• L’algoritmo di cancellazione prevede quattro
possibili casi di intervento più altri quattro
simmetrici
• La complessità di tale algoritmo è di ordine
O(h)
Un esempio
65
26
24
x
NIL
73
42
NIL
32
NIL
51
NIL NIL NIL NIL
NIL