RB-alberi
(Red-Black trees)
Proprietà degli RB-alberi
Rotazioni
Inserimento
Rimozione
Proprietà degli RB-alberi
• Un RB-albero (Red-black tree) è un albero binario di
ricerca dove ogni nodo ha in aggiunta un campo per
memorizzare il suo colore: RED (rosso) o BLACK
(nero).
• La colorazione avviene mediante regole precise, che
assicurano che nessun cammino dalla radice ad una
foglia risulti lungo più del doppio di qualsiasi altro.
• Si ottiene così che l’albero è abbastanza bilanciato.
• Ciascun nodo dell’albero contiene i campi color, key,
left, right, e p.
Proprietà degli RB-alberi
•
Un RB-albero (red-black tree) soddisfa le seguenti
proprietà:
1. Ciascun nodo è rosso o nero.
2. Ciascuna foglia (NIL) è nera.
3. Se un nodo è rosso allora entrambi i suoi figli sono neri.
4. Ogni cammino da un nodo ad una foglia sua
discendente contiene lo stesso numero di nodi neri.
Dalla proprietà 4 si definisce la b-altezza di un nodo x.
bh(x) = numero di nodi neri su un cammino da un nodo
x, non incluso, ad una foglia sua discendente.
Nota: Un nodo nero può avere figli rossi o neri.
Tutti i nodi interni hanno due figli.
Red-Black Albero
root[T]
9
5
15
4
7
12
19
NIL
2
NIL
NIL
8
6
NIL
NIL
NIL
NIL
11
NIL
NIL
13
NIL
NIL
NIL
NIL
Altezza di RB-albero
Un RB-albero con n nodi interni ha un’altezza di
al più 2 lg(n+1).
Dim.:
Si ha che ogni sottoalbero con radice in x contiene almeno
2bh(x)-1 nodi interni.
Dimostrazione per induzione:
Se bh(x)=0, x è una foglia e si ha 20-1=1-1=0.
Supponiamo vera per bh(x)=k-1, allora consideriamo un
nodo x con bh(x)=k e k>0. x è un nodo interno (k>0) e ha
due figli con b-altezza bh(x) o bh(x)-1.
Allora i nodi interni nel sottoalbero con radice in x sono
almeno (2bh(x)-1-1)+(2bh(x)-1-1)+1= 2bh(x)-1.
Altezza di RB-albero
Dim. (prosegue):
Sia h l’altezza del RB-albero.
Per la proprietà 3 almeno metà dei nodi sono neri. Quindi la
b-altezza della radice è almeno h/2.
Dunque, i nodi interni n sono almeno 2h/2-1.
2h/2-1 ≤ n
h ≤ 2 lg(n+1).
Operazioni su un RB-albero
•Le operazioni di SEARCH, PREDECESSOR, MINIMUM e
MAXIMUM sono quelle viste per un albero binario di ricerca.
Possono essere eseguite in un RB-albero con un tempo pari
a O(h) = O(lg(n)).
•Le operazioni di INSERT e DELETE si complicano, poiché
devono tener conto delle proprietà aggiuntive del RB-albero.
Più precisamente si devono effettuare dei cambiamenti in
modo da ripristinare le regole di colorazione dei nodi.
•Tuttavia, RB-INSERT() e RB-DELETE() possono essere
eseguite in tempo O(lg(n)).
Rotazioni
• Le rotazioni sono delle operazioni che
cambiano la struttura dei puntatori di due
nodi (padre e figlio).
• E’ un’operazione locale dell’albero di ricerca che
non modifica l’ordinamento delle chiavi.
• Questa operazione sono utilizzate da INSERT e
DELETE per ripristinare le proprietà violate
degli RB-alberi mantenendo l’albero sempre un
albero binario di ricerca.
Rotazioni
y
x
c
a
b
x
RIGHT-ROTATE(T,y)
LEFT-ROTATE(T,x)
a≤x≤b≤y≤c
y
a
b
c
I due nodi interni x e y potrebbero essere ovunque
nell’albero. Le lettere a, b e c rappresentano sottoalberi
arbitrari.
Un’operazione di rotazione mantiene l’ordinamento delle
chiavi secondo la visita inorder.
Rotazioni
LEFT-ROTATE(T,x)
1. y ← right[x]
2. right[x] ← left[y]
3. if left[y] ≠ NIL
4.
then p[left[y]] ← x
5. p[y] ← p[x]
6. if p[x] = NIL
7.
then root[T] ← y
8.
else if x = left[p[x]]
9.
then left[p[x]] ← y
10.
else right[p[x]] ← y
11. left[y] ← x
12. p[x] ← y
// inizializzazione di y
// inizio rotazione: sposta b
// metti y al posto di x
// se x era la radice
// modifica puntatore di p[x]
// metti x a sinistra di y
Si opera solo sui puntatori lasciando inalterati gli altri
campi.
RIGHT-ROTATE() è un procedura simmetrica. Entrambe le
procedure sono eseguite in un tempo costante, quindi O(1).
Inserimento
RB-INSERT(T,x)
1. TREE-INSERT(T,x)
2. color[x] ← RED
// ins. come albero b. di ricerca
// la proprietà 3 potrebbe
essere violata p[x] = RED
Si usa la procedura TREE-INSERT per inserire il nodo x nel
RB-albero, visto che è un albero binario.
Il nodo x viene colorato di rosso (i due figli NIL sono neri).
Proprietà 1 e 2 sono soddisfatte: il nuovo nodo è rosso e ha
due figli NIL neri.
Proprietà 4 si mantiene il nuovo nodo è rosso e non aumenta
la b-altezza fino ai suoi due figli neri.
Potrebbe essere violata la proprietà 3, che dice che un
nodo rosso non può avere figli rossi.
Inserimento
3. while x ≠ root[T] and color[p[x]] = RED // finché prop. 3 violata
4.
do if p[x] = left[p[p[x]]]
// 3 casi: p[x] sinistra di p[p[x]]
5.
then y ← right[p[p[x]]]
6.
if color[y] = RED
// caso 1: p[x] e fratello y RED
7.
then color[p[x]] ← BLACK // y “zio” di x
8.
color[y] ← BLACK
9.
color[p[p[x]]] ← RED
10.
x ← p[p[x]]
Il ciclo while continua ad essere eseguita finché la proprietà
3 risulta invariata: x e p[x] sono entrambi RED.
Lo scopo è quello di far “risalire” nell’albero questa
violazione, mentre tutte le altre proprietà rimangono valide.
Dopo ogni iterazione: o il puntatore x risale l’albero o viene
eseguita qualche rotazione ed il ciclo termina.
Inserimento
Ci sono 3 casi + altri 3 simmetrici (la linea 4 li suddivide).
Caso 1: y il fratello di p[x] è esso stesso RED. Quindi p[p[x]]
è BLACK.
Possibile nuova violazione tra p[p[x]]
e suo padre: se entrambi RED!
p[p[x]]
p[x]
x
p[p[x]]
y
p[x]
x
y
Inserimento
11.
12.
13.
else if x = right[p[x]]
// caso 2: zio y BLACK
then x ← p[x]
// e x a destra di p[x]
LEFT-ROTATE(T,x)
Caso 2: lo zio di x è BLACK e x è figlio destro di p[x].
Quindi, p[p[x]] è BLACK (unica violazione: tra x e p[x]!).
bh(a) = bh(b) = bh(c)
p[p[x]]
Caso 3
x ← p[x]
y
p[x]
x
LEFT-ROTATE(T,x)
y
x
y
a
c
x
b
c
a
b
Inserimento
color[p[x]] ← BLACK // caso 3: zio y BLACK
color[p[p[x]]] ← RED // e x a sinistra di p[x]
RIGHT-ROTATE(T,p[p[x]])
14.
15.
16.
Caso 3: lo zio y di x è BLACK e x (RED) è figlio sinistro di
p[x] (RED). Quindi, p[p[x]] è BLACK (unica violazione: tra x
e p[x]!).
p[p[x]]
color[p[x]] ← B
p[p[x]]
color[p[p[x]]] ← R
p[x]
RIGHT-ROTATE(T,p[p[x]])
p[x]
y
p[x]
p[p[x]]
y
x
c
x
a
b
c
x
a
a
b
c
b
bh(a) = bh(b) = bh(c) = bh(y)
y
Inserimento
Il Caso 2 si trasforma nel Caso 3. La proprietà 4 si
preserva.
A questo punto (Caso 3) si deve effettuare alcuni
cambiamenti di colore ed una rotazione destra che
preserva la proprietà 4.
Dopo il Caso 3 il ciclo while non è più ripetuto, in quanto
p[x] è nero.
A questo punto tutte le proprietà sono rispettate.
Inserimento
17.
else (altri 3 Casi simmetrici: scambia “right” e “left”)
18. color[root[T]] ← BLACK
// nel caso x risalga fino alla
radice
La linea 17 è l’inizio degli altri 3 Casi simmetrici. Il codice
risulta uguale, basta scambiare “right” con “left” e
viceversa.
L’ultima riga è importante: la radice risulta sempre nera.
Se x non è la radice e p[x] risulta rosso, allora p[x] non è
esso stesso la radice dell’albero e, quindi, esiste p[p[x]].
Questa condizione è fondamentale per il corretto
funzionamento dell’algoritmo.
Inserimento
RB-INSERT(T,x)
1. TREE-INSERT(T,x)
// ins. come albero b. di ricerca
2. color[x] ← RED
// la proprietà 3 violata?
3. while x ≠ root[T] and color[p[x]] = RED // finché prop. 3 violata
4.
do if p[x] = left[p[p[x]]]
// 3 casi: p[x] sinistra di p[p[x]]
5.
then y ← right[p[p[x]]]
6.
if color[y] = RED
// caso 1: p[x] e fratello y RED
7.
then color[p[x]] ← BLACK // y “zio” di x
8.
color[y] ← BLACK
9.
color[p[p[x]]] ← RED
10.
x ← p[p[x]]
11.
else if x = right[p[x]]
// caso 2: zio y BLACK
12.
then x ← p[x]
// e x a destra di p[x]
13.
LEFT-ROTATE(T,x)
14.
color[p[x]] ← BLACK // caso 2: zio y BLACK
15.
color[p[p[x]]] ← RED // e x a sinistra di p[x]
16.
RIGHT-ROTATE(T,p[p[x]])
17.
else (altri 3 Casi simmetrici: scambia “right” e “left”)
18. color[root[T]] ← BLACK
// nel caso x risalga fino alla radice
Inserimento
Analisi del tempo di esecuzione:
• Dato che l’altezza di un RB-albero di n nodi è O(lg(n)),
la chiamata TREE-INSERT() costa tempo O(lg(n)).
• Il ciclo while è ripetuto solo se si esegue il Caso 1 con il
conseguente spostamento verso la radice di x.
• Per cui il numero massimo di volte che il ciclo while può
essere ripetuto è O(lg(n)).
• Ogni ciclo while è eseguito in tempo costante.
• Quindi, RB-INSERT() impiega un tempo totale pari a
O(lg(n)).
Inserimento
Un esempio pratico
root[T]
RB-INSERT(T,x)
key[x] = 5
11
4
5
15
3
13
NIL
2
NIL
7
8
6
NIL
NIL
NIL
NIL
NIL
NIL
19
NIL
NIL
NIL
Inserimento
Un esempio pratico
root[T]
Caso 1
11
4
15
3
Proprietà 3
violata
13
y
NIL
2
NIL
7
8
6
NIL
x
5
NIL
NIL
NIL
NIL
NIL
NIL
19
NIL
NIL
NIL
Inserimento
Un esempio pratico
root[T]
Caso 2
11
y
4
Proprietà 3
violata
x
3
7
13
NIL
2
NIL
15
8
6
NIL
5
NIL
NIL
NIL
NIL
NIL
NIL
19
NIL
NIL
NIL
Inserimento
Un esempio pratico
root[T]
Caso 3
Proprietà 3
violata
11
y
7
15
x
8
4
3
6
NIL
5
2
NIL
NIL
NIL
NIL
NIL
NIL
13
NIL
NIL
19
NIL
NIL
NIL
Inserimento
Un esempio pratico
Nota: l’albero è
più bilanciato!
root[T]
7
4
11
3
NIL
2
NIL
6
NIL
5
NIL
8
NIL
NIL
NIL
15
13
NIL
NIL
19
NIL
NIL
NIL
Rimozione
La rimozione di un nodo da un RB-albero è un po’ più
complicata dell’inserimento.
Per semplificare il codice si fa uso di una sentinella nil[T]
al posto di ogni foglia NIL. Il colore di nil[T] è BLACK,
mentre gli altri campi (p, left, right, key) sono arbitrari. Tutti i
puntatori a NIL sono sostituiti con puntatori a nil[T].
Il vantaggio è quello di poter trattare nil[T] come un nodo
e poter quindi assegnare il valore p[nil[T]] necessario per il
corretto funzionamento dell’algoritmo.
Rimozione
RB-DELETE(T,z)
1. if left[z] = nil[T] o right[z] = nil[T]
2.
then y ← z
// z ha 0 o 1 figlio
3.
else y ← TREE-SUCCESSOR(z) // z ha due figli, trova succ(z)
4. if left[y] ≠ nil[T]
// x punta ad eventuale
5.
then x ← left[y]
// unico figlio di y, altrimenti a nil[T]
6.
else x ← right[z]
7. p[x] ← p[y]
// taglia fuori y
8. if p[y] = nil[T]
9.
then root[T] ← x
// se y è la radice
10. else if y = left[p[y]]
// altrimenti
11.
then left[p[y]] ← x
// completa eliminazione di y
12.
else right[p[y]] ← x
13. if y ≠ z
// se y è il successore
14.
then key[z] ← key[y]
// copia y in z
15.
copia anche altri attributi di y in z
16. if color[y] = BLACK
// chiama fixup se proprietà 4
17.
then RB-DELETE-FIXUP(T,x)
// risulta violata
18. return y
Inserimento
Un esempio pratico
root[T]
RB-DELETE(T,x)
con key[x] = 2
7
4
11
3
z=y
2
6
8
5
15
13
NIL
19
Inserimento
Un esempio pratico
root[T]
RB-DELETE(T,x)
con key[x] = 2
7
4
11
3
6
8
5
15
13
NIL
19
Rimozione
La rimozione di un nodo da un RB-albero è una semplice
modifica della procedura TREE-DELETE.
Dopo aver rimosso il nodo y, si chiama RB-DELETE-FIXUP
se color[y] è BLACK. Questo perché viene eliminato un
nodo interno nero e la proprietà 4 sulla b-altezza non è più
valida.
In RB-DELETE-FIXUP(T,x) si considera che x abbia un
colore nero “doppio”, cioè pari a 2. La proprietà 4 risulta
cosi soddisfatta.
Lo scopo è di spostare il colore nero di troppo verso la
radice in modo da eliminarlo.
Rimozione
RB-DELETE-FIXUP(T,x)
1. while x ≠ root[T] and color[x] = BLACK
2.
3.
4.
5.
6.
7.
8.
// spingi su BLACK
extra verso radice
// 4 casi se x = left[p[x]]
do if x = left[p[x]]
then w ← right[p[x]]
if color[w] = RED
then color[w] ← BLACK
color[p[x]] ← RED
LEFT-ROTATE(T, p[x])
w ← right[p[x]]
Nero per
color[w]
Caso 1
B
x
c
C
C
A
f
a
E
w
x
E
d e
D
B
D
b
Caso 2, 3 o 4
Nero
doppio
w
A
a
Nero
doppio
// caso 1
// fratello RED
b
c
e
d
f
Rimozione
9.
10.
11.
if color[left[w]] = BLACK and color[right[w]] = BLACK
then color [w] ← RED
// caso 2: w BLACK
x ← p[x]
// figli di w BLACK
Se il nuovo p[x] è RED il ciclo while termina. Per esempio,
se si passa dal Caso 1 al Caso 2, il nuovo x (p[x]) è RED.
Aggiungi
colore
nero
Caso 2
B
D
A
b
Nero
doppio
c
B
w
x
a
nuovo x
C
E
d
D
A
e
a
f
b
c
C
E
d
e
f
Rimozione
12.
13.
14.
15.
16.
else if color [right[w]] = BLACK
// caso 3: w BLACK, left[w] RED
then color[left[w]] ← BLACK // right[w] BLACK
color[w] ← RED
RIGHT-ROTATE(T,w)
w ←right[p[x]]
Si è trasformato il Caso 3 nel Caso 4.
Caso 4
Caso 3
B
b
Nero
doppio
c
a
C
E
d
e
C
A
D
A
nuovo w
x
w
x
a
B
Nero
doppio
f
b
c
D
d
E
e
f
Rimozione
color[w] ← color[p[x]]
// caso 4: w BLACK
color[p[x]] ← BLACK
// right[w] RED
color[p[x]] ← BLACK
LEFT-ROTATE(T,p[x])
x ← root[T]
// per terminare il ciclo
e assicurarsi che root sia BLACK
17.
18.
19.
20.
21.
Caso 4
cpx = color[p[x]]
B
D
w
x
a
b
Nero
doppio
c
C
e
E
A
E
d
w
B
D
A
color ← cpx
due neri
f
a
C
b
c
e
d
f
nuovo x =
root[T]
Rimozione
RB-DELETE-FIXUP(T,x)
1. while x ≠ root[T] and color[x] = BLACK
// spingi su BLACK
extra verso radice
// 4 casi se x = left[p[x]]
2. do if x = left[p[x]]
3.
then w ← right[p[x]]
4.
if color[w] = RED
// caso 1: w RED
5.
then color[w] ← BLACK
// fratello RED
6.
color[p[x]] ← RED
7.
LEFT-ROTATE(T, p[x])
8.
w ← right[p[x]]
9.
if color[left[w]] = BLACK and color[right[w]] = BLACK
10.
then color [w] ← RED
// caso 2: w BLACK
11.
x ← p[x]
// figli di w BLACK
Rimozione
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
else if color [right[w]] = BLACK
// caso 3: w BLACK
then color[left[w]] ← BLACK
// right[w] BLACK
color[w] ← RED
RIGHT-ROTATE(T,w)
w ←right[p[x]]
color[w] ← color[p[x]]
// caso 4: w BLACK
color[p[x]] ← BLACK
// right[w] RED
color[p[x]] ← BLACK
LEFT-ROTATE(T,p[x])
x ← root[T]
// per terminare il ciclo
e assicurarsi che root sia BLACK
22.
else (analogo con “right” e “left” scambiati)
23. color[x] ← BLACK
Rimozione
In tutti i quattro casi (+ gli i 4 simmetrici) la proprietà 4 si
mantiene dopo le modifiche, ossia il numero di nodi neri
dalla radice a ognuno dei sottoalberi a, b, c ,d , e ed f rimane
identico dopo la trasformazione.
Tempo di esecuzione:
Data l’altezza dell’albero è pari a O(lg(n)), la chiamata di RBDELETE() senza considerare RB-DELETE-FIXUP() ha un
costo di O(lg(n)) (vedi rimozione in un albero binario).
In RB-DELETE-FIXUP(), il Caso 1 si riconduce ai Casi 2, 3 o
4 in tempo costante. I Casi 3, e 4 fanno terminare la
procedura dopo l’esecuzione di un numero costante di passi.
Rimozione
Il Caso 2 è l’unico per il quale si potrebbe ripetere
l’esecuzione del ciclo while. Questo può avvenire al più
O(lg(n)) volte.
Quindi la procedura RB-DELETE-FIXUP() impegna un
tempo O(lg(n)) ed esegue al più tre rotazioni.
Il tempo di esecuzione complessivo della procedura RBDELETE() risulta O(lg(n)).
Su un RB-albero le operazioni di SEARCH,
PREDECESSOR, MINIMUM, MAXIMUM, INSERT e
DELETE sono tutte O(lg(n)).