RB-insert(T, z) // z.left = z.right = T.nil Insert(T, z) z.color = RED // z è rosso. L’unica violazione // possibile delle proprietà degli alberi // rosso-neri è che z sia radice (prop. 2) // oppure che z.p sia rosso (prop. 4) RB-Insert-Fixup(T, z)

Inserimento di un nuovo elemento

RB-Insert-Fixup(T, z) while z.p.color == RED // violata la proprietà 4 if z.p == z.p.p.left // l’altro caso è simmetrico y = z.p.p.right if y.color == RED // Caso 1 z.p.color = y.color = BLACK z.p.p.color = RED z = z.p.p

5 9

3

7z.p.p

yz.p

z

5 9

3

7z.p.p

yz.p

z

else if z == z.p.right // Caso 2 z = z.p Left-Rotate(T, z)

3 9

5

7z.p.p

yz.p

z

5 9

3

7z.p.p

y

z

z.p

// z figlio sinistro // Caso 3 z.p.color = BLACK z.p.p.color = RED Right-Rotate(T, z.p.p) else // simmetrico con right e left scambiati // alla fine del ciclo l’unica proprietà violata può // essere soltanto la 2 T.root.color = BLACK // Caso 0

5 9

3

7z.p.p

y

z

z.p

z

5 9

3

7z.p.p

yz.p

5

9

3 7

Complessità.

Quindi RB-Insert ha complessità O(log n).

Ogni volta che si ripete il ciclo while il puntatore z risale di due posizioni.Quindi il ciclo può essere ripetuto al più h volte e la complessità di RB-Insert-Fixup è O(log n).

Rb-Delete(T, z) // z ≠ T.nil if z.left == T.nil or z.right == T.nil y = z else y = Successor(z), z.key = y.key // elimino y che ha almeno un sottoalbero vuoto if y.left == T.nil x = y.right else x = y.left // x sottoalbero di y, l’altro è sicuramente vuoto

Cancellazione di un elemento

// metto x al posto del padre y x.p = y.p if y.p == T.nil T.root = x elseif y == y.p.left y.p.left = x else y.p.right = x // Se y è rosso non ci sono violazioni if y.color == BLACK // Se y era nero l’unica violazione delle // proprietà degli alberi rosso neri è che // i cammini che passano per x contengano // un nodo nero in meno RB-Delete-Fixup(T, x)

RB-Delete-Fixup(T, x) while x ≠ T.root and x.color == BLACK if x == x.p.left // l’altro caso è simmetrico w = x.p.right if w.color == RED // Caso 1 w.color = BLACK x.p.color = RED Left-Rotate(T, x.p) w = x.p.right

x 1 7

3

w

5 9

1 7

3

wx

5 9

1

7

3

wx

5

9

// il fratello w è nero if w.left.color == BLACK and w.right.color == BLACK // Caso 2 w.color = RED x = x.p

1 7

3

wx

5 9

1 7

3

w

5 9

else if w.right.color == BLACK // Caso 3 w.left.color = BLACK w.color = RED Right-Rotate(T, w) w = x.p.right

1 7

3

wx

5 9

1

7

w

5

9

3

x

1 7

3

wx

5 9

// Caso 4 w.color = x.p.color x.p.color = w.right.color = BLACK Left-Rotate(T, x.p) x = T.root else // simmetrico con right e left scambiati

1 7

3

wx

5 9

1 7

3

wx

5

9 1

7

3

5

9

// quando termina il ciclo o x è la radice // oppure x è rosso x.color = BLACK // Caso 0

Caso 0: x radice x

5Caso 0: x rosso x 5x

5x5

Complessità di RB-Delete-Fixup.

Con i casi 0, 3 e 4 il ciclo while termina immediatamente e dunque essi richiedono tempo costante.Dopo aver eseguito il caso 1 viene eseguito una sola volta il caso 2 e poi uno dei casi 0, 3 o 4. Quindi anche il caso 1 richiede tempo costante. Solo il caso 2 può essere ripetuto sul padre di x.

Quindi il ciclo può essere ripetuto al più h volte e la complessità è O(log n).

Come aumentare gli alberi La soluzione di alcuni problemi algoritmici richiede la progettazione di una struttura dati appropriata.Spesso una tale struttura si può ottenere aumentando strutture dati note.Supponiamo ci serva una struttura dati su cui poter eseguire, oltre alle operazioni previste per gli alberi di ricerca, anche l’operazione di statistica ordinale Select(k) che ritorna il nodo con la chiave k-esima.

Un modo per farlo è aumentare gli alberi rosso-neri aggiungendo a ciascun nodo x un ulteriore campo intero x.size in cui memorizzare il numero di nodi interni del sottoalbero di radice x.

keysize

2620

1712

147

214

305

471

417

104

231

192

162

383

281

391

121

72

351

201

151

31

?0

Osservazione.

Se usiamo la sentinella T.nil e poniamo T.nil.size = 0 allora per ogni nodo interno x vale l’equazione

x.size = 1 + x.left.size + x.right.size

Possiamo realizzare facilmente Select: Select(x, k) // 1 ≤ k ≤ x.size // Trova il nodo con chiave k-esima // nel sottoalbero di radice x i = 1 + x.left.size if i == k return x elseif i > k return Select(x.left, k) else return Select(x.right, k-i)

Possiamo realizzare facilmente anche l’operazione inversa Rank(x) che trova la posizione k della chiave di x nella sequenza ordinata delle chiavi dell’albero Rank(T, x) // Trova la posizione k della chiave di x i = 1 + x.left.size y = x while y.p ≠ T.nil if y == y.p.right i = i + 1 + y.p.left.size y = y.p return i

RB-Insert ha due fasi.Nella prima si scende dalla radice fino ad una foglia che viene quindi sostituita con il nuovo nodo.Nella seconda si ripristinano le proprietà violate.

Naturalmente dobbiamo modificare RB-Insert e RB-Delete per mantenere aggiornato il campo size dei nodi

RB-Insert (T, z) // z.left = z.right = T.nil Insert (T, z) z.color = RED RB-Insert-Fixup (T, z)

Per la prima fase basta mettere 1 nel campo size del nuovo nodo z e aumentare di 1 il campo size di tutti i nodi incontrati scendendo verso la foglia che verrà sostituita con z.

Insert(T, z) z.size = 1 // istruzione aggiunta x = T.root, y = T.nil while x ≠ T.nil x.size = x.size + 1 // istruzione aggiunta y = x if z.key < y.key x = y.left else x = y.right z.p = y if y == T.nil T.root = z elseif key[z] < key[y] x.left = z else x.right = z

I campi size dei nodi diversi da x e y rimangono invariati.

Basta quindi ricalcolare i campi size dei due nodi x e y usando la relazione:

x.size = 1 + x.left.size + x.right.size

Left-Rotate(T, x)

Right-Rotate(T, y)

Nella seconda fase le modifiche alla struttura sono dovute alle rotazioni.

x

y

y

x

Left-Rotate(T, x) y = x.right x.right = y.left, y.left.p = x y.p = x.p if x.p == T.nil T.root = y elseif x == x.p.left x.p.left = y else x.p.right = y x.p = y, y.left = x y.size = x.size // istruzioni aggiunte x.size = 1 + x.left.size + x.right.size

LeftRot(T,x)

x

y

y

x