Alberi Rosso-Neri
Algoritmi e Strutture Dati
20 aprile 2001
Alberi Binari di Ricerca
Gli alberi di ricerca binari consentonol’individuazione di un elemento al propriointerno in un tempo mediamente proporzionaleall’altezza dell’albero considerato
4
2 6
1 3 5 7
Costruiamo un albero a partire dalla sequenza:4, 2, 6, 1, 3, 5, 7
3 = O(log(n))
Alberi Binari di Ricerca
4
5
6
1
2
3
7
1, 2, 3, 4, 5, 6, 7
7 = O(n)
Inseriamo gli stessi elementi con un diverso ordine:
• Gli alberi Rosso-Neri sono alberi binari di ricerca estesi
• Ciascun nodo di tali alberi contiene uncampo addizionale che riporta il suo colore
• Le operazioni di inserimento e cancellazionevengono opportunamente integrate in modotale da rendere l’albero binario bilanciato
Alberi Rosso-Neri
Un esempio di albero Rosso-Nero
Caratterizzazione
La caratterizzazione degli alberi Rosso-Neriavviene attraverso la formulazione diquattro proprietà vincolanti
Proprietà n. 1
Ogni nodo dell’albero è rosso o nero
46
26 62
21 31 51 85
Proprietà n. 2
NIL NIL
Ogni foglia dell’albero (NIL) è nera
52
45 NIL
Proprietà n.3
Se un nodo è rosso entrambi i suoifigli sono neri
42
12 78
Proprietà n.4Dato un nodo, tutti i percorsi discendenti cheraggiungono una foglia contengono lo stessonumero di nodi neri
65
42 73
32 51 NIL NIL
26
NIL NIL
NILNILNIL
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
Proprietà
OsservazioneProviamo a costruire un albero Rosso-Nerosbilanciato…
4
5
6
1
2
3
NIL
NIL
NIL
NIL
NIL
NIL
NIL
Osservazione
4
5
6
1
2
3
NIL
NIL
NIL
NIL
NIL
NIL
NIL
Altezza-nero
• Definiamo altezza-nero di un nodo x(black-height(x)) il numero di nodi neriche si incontrano in un qualsiasi camminodiscendente da x verso una foglia
• Definiamo l’altezza-nero di un alberoRosso-Nero come l’altezza-nero della suaradice
Altezza-nero
65
42 73
32 51 NIL NIL
26
NIL NIL
NILNILNIL
black-height(32) = 2
black-height(42) = 2
black-height(T)= black-height(65) = 3
Lemma 1
Un albero Rosso-Nero con n nodi interni haaltezza al più 2lg(n+1)
Lemma 2
Dato un nodo x appartenente ad un alberoRosso-Nero, il sottoalbero ivi radicato contiene almeno 2bh(x)-1 nodi interni
Dimostrazione Lemma 2Dimostriamo il Lemma 2 per induzionesull’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 nodiinterni
NIL
Dimostrazione Lemma 2Consideriamo un nodo x che ha altezza > 0,esso avrà quindi due figli…
6
82
6
82
Ciascuno dei due figli di x avrà altezza bh(x) oppure bh(x)-1.
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
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.
Un albero Rosso-Nero con n nodi interni haaltezza al più 2lg(n+1)
Dimostrazione Lemma 1
n 2h/2 –1
n +1 2h/2
log(n+1) h/2
h 2lg(n+1)
Dall’applicazione del Lemma 2 possiamo affermare che il numero di nodi interni n è maggiore o uguale di 2h/2 –1
Alberi Rosso-Neri
Il mantenimento delle proprietà caratterizzantigli alberi Rosso-Neri deve essere garantitoin corrispondenza delle comuni operazioni chevanno a modificare la struttura dell’albero stesso
Le operazioni di inserimento e cancellazionegià viste per gli alberi binari di ricerca vengonomantenute ed integrate con una successivaoperazione di ribilanciamento
Rotazioni
Ai fini dell’implementazione delle proceduredi ribilanciamento si rivela utile l’introduzionedelle operazioni di left-rotation (rotazione sinistra)e right-rotation (rotazione destra)
y
x
ba
c y
x
b
a
c
Right-Rotate(T,y)
Left-Rotate(T,x)
Rotazione sinistra
b
z
b
y
x
a
c
y
x
a
c
z
Left-RotateLeft-Rotate(T,x)
Yright[x]right[x] left[y]If left[y] NIL
then p[left[y]] xp[y]p[x]If p[x] = NIL
then root[T] yelse if x = left[p[x]]then left[p[x]] yelse right[p[x]] y
left[y] xp[x] y
b
z
b
y
x
a
c
y
x
a
c
z
InserimentoL’algoritmo di inserimento di un nodo x in unalbero Rosso-Nero:
• Inserisce il nuovo nodo nell’albero secondoil tradizionale algoritmo di inserimento per alberibinari di ricerca
• Verifica se l’albero risultante viola le proprietàdegli alberi Rosso-Neri
• In caso di violazione, si risale l’albero sino allaradice operando opportunamente rotazioni ecambiamenti di colore
InserimentoL’algoritmo di inserimento che presenteremodistingue tre possibili casi di intervento perripristinare le proprietà degli alberi Rosso-Neripiù altri tre simmetrici
RB-Insert(T,x)RB-Insert(T,x)
Tree-Insert(T,x)color[x] REDWhile 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] = REDthen color[p[x]] = BLACKcolor[y] = BLACKcolor[p[p[x]]] = REDx 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
65
42 73
32 51 NIL NIL
26
NIL NIL
NILNILNIL
Inseriamo nell’albero corrente l’elemento x = 24
Un esempio 2/3
65
42 73
32 51 NIL NIL
26
NIL
NIL
NILNILNIL
24
NIL
x
p[x]
p[p[x]]
Ci troviamo nel terzo caso della proceduradi ribilanciamento
Un esempio 3/3
65
42 73
32
51 NIL NIL26
NIL NIL
NILNIL
NIL
24
NIL
x
CancellazioneL’algoritmo di cancellazione di un nodo x da unalbero Rosso-Nero opera secondo la stessafilosofia dell’algoritmo di inserimento:
• Cancella il nodo dall’albero secondo iltradizionale algoritmo di cancellazione peralberi binari di ricerca
• Verifica se l’albero risultante viola le proprietàdegli alberi Rosso-Neri
• In caso di violazione, si risale l’albero sino allaradice operando opportunamente rotazioni ecambiamenti di colore
Cancellazione• L’algoritmo di cancellazione prevede quattropossibili casi di intervento più altri quattrosimmetrici
• La complessità di tale algoritmo è di ordineO(h)
Un esempio
65
42
73
32 51
NIL NIL
26
NIL
NIL NILNILNIL
24
NILx
Top Related