RB-alberi(Red-Black trees)

Proprietà degli RB-alberiRotazioniInserimentoRimozione

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

2 6 8

9

15

74

5

19

1311

12

root[T]

NIL NIL NIL NIL NIL NIL NIL NIL

NIL NILNIL

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

x

y

a b

cy

x

a

b c

RIGHT-ROTATE(T,y)

LEFT-ROTATE(T,x)

a ≤ x ≤ b ≤ y ≤ 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.

RotazioniLEFT-ROTATE(T,x)1. y ← right[x] // inizializzazione di y2. right[x] ← left[y] // inizio rotazione: sposta b3. if left[y] ≠ NIL 4. then p[left[y]] ← x5. p[y] ← p[x] // metti y al posto di x6. if p[x] = NIL 7. then root[T] ← y // se x era la radice8. else if x = left[p[x]] // modifica puntatore di p[x]9. then left[p[x]] ← y 10. else right[p[x]] ← y11. left[y] ← x // metti x a sinistra di y12. p[x] ← ySi 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).

InserimentoRB-INSERT(T,x)1. TREE-INSERT(T,x) // ins. come albero b. di

ricerca2. color[x] ← RED // la proprietà 3 potrebbe

essere violata p[x] = REDSi 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.

Inserimento3. while x ≠ root[T] and color[p[x]] = RED // finché prop. 3 violata4. 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

RED7. then color[p[x]] ← BLACK // y “zio” di x8. color[y] ← BLACK9. color[p[p[x]]] ← RED10. 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.

x

p[x] y

p[p[x]]

x

p[x] y

p[p[x]]

Possibile nuova violazione tra p[p[x]] e suo padre: se entrambi RED!

Inserimento11. else if x = right[p[x]] // caso 2: zio y

BLACK12. then x ← p[x] // e x a destra di p[x]13. 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]!).

x

p[x] y

p[p[x]]

LEFT-ROTATE(T,x)

x

yx y

x ← p[x]

a

b c a b

c

Caso 3bh(a) = bh(b) = bh(c)

Inserimento14. color[p[x]] ← BLACK // caso 3: zio y BLACK15. color[p[p[x]]] ← RED // e x a sinistra di p[x]16. RIGHT-ROTATE(T,p[p[x]])

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]]

RIGHT-ROTATE(T,p[p[x]])

x

y

color[p[x]] ← B

color[p[p[x]]] ← R

p[x]

p[p[x]]

x

yp[x]p[p[x]]

x

y

p[x]

c c

c

bh(a) = bh(b) = bh(c) = bh(y)a b a b

a b

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

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.

17. else (altri 3 Casi simmetrici: scambia “right” e “left”)18. color[root[T]] ← BLACK // nel caso x risalga fino alla

radice

InserimentoRB-INSERT(T,x)1. TREE-INSERT(T,x) // ins. come albero b. di

ricerca2. color[x] ← RED // la proprietà 3 violata?3. while x ≠ root[T] and color[p[x]] = RED // finché prop. 3 violata4. 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

RED7. then color[p[x]] ← BLACK // y “zio” di x8. color[y] ← BLACK9. color[p[p[x]]] ← RED10. x ← p[p[x]]11. else if x = right[p[x]] // caso 2: zio y BLACK12. 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 BLACK15. 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)).

InserimentoUn esempio pratico

2 6 8

11

73

4

root[T]

NIL NIL NIL NIL

NIL

NIL NIL

RB-INSERT(T,x)key[x] = 5

5 15

1913

NIL NIL NIL NIL

InserimentoUn esempio pratico

2 6 8

11

73

4

root[T]

NIL NIL NIL

NIL

NIL NIL

Caso 1

5

NIL NILProprietà 3

violata

x

15

1913

NIL NIL NIL NILy

InserimentoUn esempio pratico

2 6

11

15

73

4

1913

root[T]

NIL NIL NIL

NIL NIL NIL NILNIL

NIL NIL

Caso 2

5

NIL NIL

Proprietà 3 violata

x

y

8

InserimentoUn esempio pratico

2

6

11

157

3

4 1913

root[T]

NIL

NIL NIL NIL NIL NIL NIL

NIL

NIL NIL

Caso 3

5

NIL NIL

Proprietà 3 violata

x

y

8

InserimentoUn esempio pratico

2

6

11

15

7

3

4

1913

root[T]

NIL NIL NIL

NIL NIL NIL NIL

NIL

NIL NIL

Nota: l’albero è più bilanciato!

5

NIL NIL

8

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.

RimozioneRB-DELETE(T,z)1. if left[z] = nil[T] o right[z] = nil[T]2. then y ← z // z ha 0 o 1 figlio3. else y ← TREE-SUCCESSOR(z) // z ha due figli, trova

succ(z)4. if left[y] ≠ nil[T] // x punta ad eventuale5. then x ← left[y] // unico figlio di y, altrimenti a nil[T]6. else x ← right[z] 7. p[x] ← p[y] // taglia fuori y8. if p[y] = nil[T] 9. then root[T] ← x // se y è la radice10. else if y = left[p[y]] // altrimenti11. then left[p[y]] ← x // completa eliminazione di

y12. else right[p[y]] ← x13. if y ≠ z // se y è il successore14. then key[z] ← key[y] // copia y in z15. copia anche altri attributi di y in z16. if color[y] = BLACK // chiama fixup se proprietà

417. then RB-DELETE-FIXUP(T,x) // risulta violata18. return y

InserimentoUn esempio pratico

2

6

11

15

7

3

4

1913

root[T]

NIL

RB-DELETE(T,x)con key[x] = 2

5

8

z = y

InserimentoUn esempio pratico

6

11

15

7

3

4

1913

root[T]

NIL

RB-DELETE(T,x)con key[x] = 2

5

8

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.

RimozioneRB-DELETE-FIXUP(T,x)1. while x ≠ root[T] and color[x] = BLACK // spingi su BLACK

extra verso radice2. do if x = left[p[x]] // 4 casi se x = left[p[x]]3. then w ← right[p[x]]4. if color[w] = RED // caso 15. then color[w] ← BLACK // fratello RED6. color[p[x]] ← RED7. LEFT-ROTATE(T, p[x])8. w ← right[p[x]]

A Dx

B

C E

w

Caso 1

a b

c d e f

Nero per color[w]

A

D

xB

C

Ew

a b c d

e f

Nero doppio

Nero doppio

Caso 2, 3 o 4

Rimozione9. if color[left[w]] = BLACK and color[right[w]] = BLACK10. then color [w] ← RED // caso 2: w BLACK11. x ← p[x] // figli di w BLACK

Caso 2

A Dx

B

C E

w

a b

c d e fNero doppio

A D

nuovo xB

C Ea b

c d e f

Aggiungicolore nero

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.

Rimozione12. else if color [right[w]] = BLACK // caso 3: w BLACK, left[w]

RED13. then color[left[w]] ← BLACK // right[w] BLACK14. color[w] ← RED15. RIGHT-ROTATE(T,w)16. w ←right[p[x]]

Caso 3

A Dx

B

C E

w

a b

c d e fNero doppio

A C

B

E

Da b

e f

d

c

Si è trasformato il Caso 3 nel Caso 4.

xnuovo wCaso 4

Nero doppio

Rimozione17. color[w] ← color[p[x]] // caso 4: w BLACK18. color[p[x]] ← BLACK // right[w] RED19. color[p[x]] ← BLACK20. LEFT-ROTATE(T,p[x])21. x ← root[T] // per terminare il ciclo

e assicurarsi che root sia BLACK

Caso 4

A Dx

B

C E

w

a b

c d e fNero doppio

EB

due neriD

A C

w

e f

a b c d

cpx = color[p[x]]color ← cpx

nuovo x = root[T]

Rimozione

RB-DELETE-FIXUP(T,x)1. while x ≠ root[T] and color[x] = BLACK // spingi su BLACK

extra verso radice2. do if x = left[p[x]] // 4 casi se x = left[p[x]]3. then w ← right[p[x]]4. if color[w] = RED // caso 1: w RED5. then color[w] ← BLACK // fratello RED6. color[p[x]] ← RED7. LEFT-ROTATE(T, p[x])8. w ← right[p[x]]9. if color[left[w]] = BLACK and color[right[w]] = BLACK10. then color [w] ← RED // caso 2: w BLACK11. x ← p[x] // figli di w BLACK

Rimozione12. else if color [right[w]] = BLACK // caso 3: w BLACK13. then color[left[w]] ← BLACK // right[w] BLACK14. color[w] ← RED15. RIGHT-ROTATE(T,w)16. w ←right[p[x]]17. color[w] ← color[p[x]] // caso 4: w BLACK18. color[p[x]] ← BLACK // right[w] RED19. color[p[x]] ← BLACK20. LEFT-ROTATE(T,p[x])21. x ← root[T] // per terminare il ciclo

e assicurarsi che root sia BLACK22. 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 RB-DELETE() 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 RB-DELETE() risulta O(lg(n)).

Su un RB-albero le operazioni di SEARCH, PREDECESSOR, MINIMUM, MAXIMUM, INSERT e DELETE sono tutte O(lg(n)).