Implementazione di dizionari

Implementazione di dizionari

Problema del dizionario dinamico

Scegliere una struttura dati in cui memorizzare dei record con un campo key e alcuni altri campi in cui sono memorizzati i dati associati alla chiave key.

Su tale struttura si devono poter eseguire in modo efficiente le operazioni:

Insert che aggiunge un nuovo record

Search che cerca un record di chiave key Delete che toglie un record dalla struttura

Tavole ad indirizzamento diretto

Funzionano bene quando le chiavi sono degli interi positivi non troppo grandi.

Ad esempio se le chiavi appartengono all’insieme U = {0,1,...,m-1} (con m non troppo grande)

possiamo usare un array T[0..m-1] in cui ogni

posizione (cella) T[k] corrisponde ad una chiave k.

Generalmente T[k] è un puntatore al record con chiave k.

Se la tavola non contiene un record con chiave k allora T[k] = nil.

La realizzazione delle operazioni in tempo costante O(1) è semplice:

Search(T,k) return T[k]

Insert(T,x)

T[x.key] = x Delete(T,x)

T[x.key] = nil

Con l’indirizzamento diretto occorre riservare memoria sufficiente per tante celle quante sono le possibili chiavi.

Se l’insieme U delle possibili chiavi è molto

grande l’indirizzamento diretto è inutilizzabile a causa delle limitazioni di memoria.

Anche quando la memoria sia sufficiente se le chiavi memorizzate nel dizionario sono soltanto una piccola frazione di U la maggior parte della memoria riservata risulta inutilizzata.

Inconvenienti

Tavole hash

Una tavola hash richiede memoria proporzionale al numero massimo di chiavi presenti nel

dizionario indipendentemente dalla cardinalità dell’insieme U di tutte le possibili chiavi.

In una tavola hash di m celle ogni chiave k viene memorizzata nella cella h(k) usando una funzione

h : U ® {0..m-1}

detta funzione hash.

Siccome |U| > m esisteranno molte coppie di chiavi distinte k₁ ≠ k₂ tali che h(k₁) = h(k₂).

Diremo in questo caso che vi è una collisione tra le due chiavi k₁ e k₂.

Nessuna funzione hash può evitare le collisioni.

Dovremo quindi accontentarci di funzioni hash che minimizzino la probabilità delle collisioni e, in ogni caso, dovremo prevedere qualche

meccanismo per gestire le collisioni.

k₁

k₃ k₅ k₄ k₂

U

Risoluzione delle collisioni con liste

Gli elementi che la funzione hash manda nella stessa cella vengono memorizzati in una lista

La tavola hash è un array T[0..m-1] di m puntatori alle cime delle liste

nil

nil

nil nil nil

nil

T

nil k₁

k₂ nil k₃ nil

h(k)

nil k₃

k₄

nil k₂

k₅

Delete(T,x)

“togli x dalla lista T[h(x.key)]”

La realizzazione delle operazioni è facile:

Search(T,k)

“cerca nella lista T[h(k)] un elemento x tale che x.key == k”

return x Insert(T,x)

“aggiungi x alla lista T[h(x.key)]”

Delete richiede una ricerca con Search dopo di che l’eliminazione dell’elemento dalla lista si può realizzare in tempo O(1)

Search richiede tempo proporzionale alla lunghezza della lista T[h(k)]

Insert si può realizzare in tempo O(1)

Analisi di hash con liste

Valutiamo la complessità media di Search in funzione del fattore di carico α = n/m.

Siccome n è compreso tra 0 e |U| 0 ≤ α ≤ |U|/m.

Una Search di un elemento con chiave k richiede tempo O(n) nel caso pessimo in cui tutti gli n

elementi stanno nella stessa lista h(k) della chiave cercata.

Supponiamo che la tavola hash T abbia m celle e che in essa siano memorizzati n elementi.

“ogni elemento in input ha la stessa

probabilità di essere mandato in una qualsiasi delle m celle”

Supporremo che h(k) distribuisca in modo uniforme le n chiavi tra le m liste.

Più precisamente assumeremo la seguente

ipotesi di hash uniforme semplice.

Siano n

,n

,...,n

le lunghezze delle m liste.

La lunghezza attesa di una lista è

Proprietà: Nell’ipotesi di hash uniforme semplice la ricerca di una chiave k non

presente nella tavola hash richiede tempo Q (1+α) in media.

a

=

=

= å

=

m

n n n m

i

i j

1 0

] 1

E[

Nell’ipotesi di hash uniforme semplice E[n

]

= α e quindi l’algoritmo richiede tempo medio Q (1+α).

Dimostrazione:

La Search calcola j =h(k) (tempo Q (1)) e poi controlla tutti gli n

elementi della lista T[j]

(tempo Q (n

)).

Proprietà: Nell’ipotesi di hash uniforme

semplice la ricerca di una chiave k presente nella tavola hash richiede tempo Q (1+α) in media.

Dimostrazione:

Assumiamo che ogni chiave presente nella

tavola abbia la stessa probabilità di essere la

chiave cercata.

Una ricerca di un una chiave k presente nella tavola richiede il calcolo dell’indice j = h(k), il test sulle chiavi che precedono k nella lista T[j] e infine il test su k (numero operazioni = 2 + numero elementi che precedono k nella lista).

Le chiavi che precedono k nella lista T[j]

sono quelle che sono state inserite dopo di k.

Nell’ipotesi di hash uniforme semplice E(X

) = 1/m.

Supponiamo che k = k

sia l’i-esima chiave inserita nella lista.

Per j = i +1,...,n sia X

la variabile casuale

che vale 1 se k

viene inserita nella stessa lista di k e 0 altrimenti

î í ì

=

= ¹

) (

) (

se 1

) (

) (

se 0

,

i j

i j

j

i

h k h k

k h k

X h

Il valore atteso del numero medio di operazioni eseguite è

å å å å

= = +

= = +

+

=

+ ⁿ

i

n i j

j i n

i

n i j

j

i X

X n

n _{1 1} ^, 1 ₁ (2 ₁E[ ^, ]) ]

) 2

1 ( E[

Se n ≤ cm per qualche costante positiva c allora α

= O(1) e Q(1+α) = Q(1).

å å å

=

= = +

- +

= +

= ⁿ

i n

i

n i j

i nm n

m

n _{1 1} 1 ₁ ( )

2 1 )

2 1 (

2

) 1 (

2 1 2 1

1 0

+ -

= +

=

å

=

n n t nm

nm

n

t

) 1

2 ( 1 2 2

2

2 + -1 _{= +} a _{- = Q +}a

= m m

n

Funzioni hash

Essa dovrebbe soddisfare l’ipotesi di hash uniforme semplice:

“Ogni chiave ha la stessa probabilità 1/m di essere mandata in una qualsiasi delle m celle, indipendentemente dalle chiavi inserite

precedentemente”

Che proprietà deve avere una una buona

funzione hash?

Sfortunatamente l’ipotesi di hash uniforme semplice dipende dalle probabilità con cui vengono estratti gli elementi da inserire;

probabilità che in generale non sono note.

Ad esempio, se le chiavi sono numeri reali x estratti casualmente e indipendentemente da una distribuzione di probabilità uniforme in 0 ≤ x < 1 allora h(x) = ë mx û soddisfa tale

condizione.

Le funzioni hash che descriveremo assumono che le chiavi siano degli interi non negativi.

Questo non è restrittivo in quanto ogni tipo di

chiave è rappresentato nel calcolatore con una

sequenza di bit e ogni sequenza di bit si può

interpretare come un intero non negativo.

Metodo della divisione

h(k) = k mod m

Una buona scelta per m è un numero primo non troppo vicino ad una potenza di 2.

Ad esempio m = 701.

Difetto: non “funziona bene” per ogni m.

Ad esempio se m = 2^p è una potenza di due allora k mod m sono gli ultimi p bit di k.

In generale anche valori di m prossimi ad una potenza di 2 non funzionano bene.

Metodo della moltiplicazione

h(k) = ë m(kA mod 1) û

in cui A è una costante reale con 0 < A < 1 ed x mod 1 = x – ë x û è la parte frazionaria.

Vantaggi : la scelta di m non è critica e nella pratica funziona bene con tutti i valori di A

anche se ci sono ragioni teoriche per preferire

l’inverso del rapporto aureo

h(k) si calcola facilmente se si sceglie m = 2^p e A = q/2^w con 0 < q < 2^w dove w è la lunghezza di una parola di memoria.

k q

´

= r₁

w bit

h(k) p bit

r₀

ë

û

1 2 mod

2 2 2

)

( ⁰

kA m

kq k r

h ^p _w ^p _w

=

úû ê ú

ë

ê ÷

ø ç ö

è

= æ úûú êëê

=

Randomizzazione di funzioni hash

Più seriamente: per ogni funzione hash si possono trovare delle distribuzioni di

probabilità degli input per le quali la funzione non ripartisce bene le chiavi tra le varie liste della tavola hash.

Nessuna funzione hash può evitare che un

avversario malizioso inserisca nella tavola

una sequenza di valori che vadano a finire

tutti nella stessa lista.

Possiamo usare la randomizzazione per

rendere il comportamento della tavola hash indipendente dall’input.

L’idea è quella di usare una funzione hash

scelta casualmente in un insieme “universale”

di funzioni hash.

Questo approccio viene detto hash universale.

Un insieme H di funzioni hash che mandano un

insieme U di chiavi nell’insieme {0,1,...,m-1} degli indici della tavola hash si dice universale se:

“per ogni coppia di chiavi distinte j e k vi sono al più |H|/m funzioni hash in H tali che h(j) = h(k)”

Se scegliamo casualmente la funzione hash in un insieme universale H la probabilità che due chiavi qualsiasi j e k collidano è 1/m, la stessa che si

avrebbe scegliendo casualmente le due celle in cui mandare j e k.

Proprietà : Supponiamo che la funzione hash h sia scelta casualmente in un insieme universale H e

venga usata per inserire n chiavi in una tavola T di m celle e sia k una chiave qualsiasi.

La lunghezza attesa E[n_h(k)] della lista h(k) è α = n/m se k non è presente nella tavola ed è minore di α+1 se k è presente.

Quindi, indipendentemente dalla distribuzione degli input, una Search richiede tempo medio Q(1+α) che, se n = O(m), è Q(1).

Risoluzione delle collisioni con indirizzamento aperto

Con la tecnica di indirizzamento aperto tutti gli elementi stanno nella tavola.

La funzione hash non individua una singola cella ma un ordine in cui ispezionare tutte le celle.

L’inserimento di un elemento avviene nella prima cella libera che si incontra nell’ordine di ispezione.

Nella ricerca di un elemento si visitano le celle sempre nello stesso ordine.

La funzione hash è una funzione h(k,i) che al variare di i tra 0 ed m-1 fornisce, per ciascuna chiave k, una sequenza di indici

h(k,0), h(k,1),..., h(k,m-1) che rappresenta l’ordine di ispezione.

Siccome vogliamo poter ispezionare tutte le

celle, la sequenza deve essere una permutazione dell’insieme degli indici 0,1,..., m-1 della tavola.

La realizzazione delle operazioni è:

Insert(T, k) i = 0

repeat

j = h(k, i)

if T[ j ] == nil T[ j ] = k return j i = i +1

until i == m

“Errore : tavola piena”

La realizzazione di Delete è più complicata

Non possiamo infatti limitarci a porre nil nella cella!!! Perché ???

Search(T, k) i = 0

repeat

j = h(k, i)

if T[ j ] == k return j i = i +1

until i == m or T[ j ] == nil

Delete(T, i)

T[ i ] = deleted

La Delete si limita ad assegnare alla chiave

dell’elemento da togliere un particolare valore diverso da ogni possibile chiave:

La Search continua a funzionare invariata:

Search(T, k) i = 0

repeat

j = h(k, i)

if T[ j ] == k return j i = i +1

until i == m or T[ j ] == nil

La Insert deve essere modificata:

Insert(T, k) i = 0

repeat

j = h(k, i)

if T[ j ] == nil

or T[ j ] == deleted T[ j ] = k

return j i = i+1

until i == m

“Errore: tavola piena”

Con l’indirizzamento aperto la funzione hash fornisce una sequenza di ispezione.

In questo caso l’ipotesi di hash uniforme diventa:

“Ogni chiave ha la stessa probabilità 1/m! di

generare una qualsiasi delle m! possibili sequenze di ispezione”

Vi sono tre tecniche comunemente usate per determinare l’ordine di ispezione:

1. Ispezione lineare

2. Ispezione quadratica 3. Doppio hash

Nessuna delle tre genera tutte le m! sequenze di ispezione.

Le prime due ne generano soltanto m e l’ultima ne genera m².

Ispezione lineare

La funzione hash h(k,i) si ottiene da una funzione hash ordinaria h'(k) ponendo

L’esplorazione inizia dalla cella h(k,0) = h'(k) e continua con le celle h'(k)+1, h'(k)+2, ecc. fino ad arrivare alla cella m-1, dopo di che si continua con le celle 0,1,ecc. fino ad aver percorso circolarmente tutta la tavola.

m i

k h

i k

h ( , ) = [ ' ( ) + ] mod

L’ispezione lineare è facile da implementare ma soffre del problema dell’addensamento primario:

“i nuovi elementi inseriti nella tavola tendono ad addensarsi attorno agli elementi già presenti”

Una cella libera preceduta da t celle occupate ha

probabilità (t +1)/m di venir occupata dal prossimo elemento inserito.

Quindi sequenze consecutive di celle occupate tendono a diventare sempre più lunghe.

Ispezione quadratica

La funzione hash h(k, i) si ottiene da una funzione hash ordinaria h'(k) ponendo

I valori di m, c₁ e c₂ non possono essere qualsiasi ma debbono essere scelti opportunamente in modo che la sequenza di ispezione percorra tutta la tavola.

Un modo per fare ciò è suggerito nel problema 11-3 del libro.

dove c₁ e c₂ sono due costanti con c₂ ≠ 0.

m i

c i

c k

h i

k

h ( , ) = [ ' ( ) +

+

] mod

Osserviamo che se h'( j) = h'(k) anche le due sequenze di ispezione coincidono.

Questo porta ad un fenomeno di addensamento secondario (meno grave dell’addensamento

primario).

L’addensamento secondario è dovuto al fatto che il valore iniziale h'(k) determina univocamente la

sequenza di ispezione e pertanto abbiamo soltanto m sequenze di ispezione distinte.

Problema 11-3 del libro:

Consideriamo la seguente procedura:

j = h'(k) i = 0

while i < m and “T[j] non è la cella cercata”

i = i+1

j = ( j+ i ) mod m

Dimostrare che la sequenza delle j che viene

generata è una sequenza di ispezione quadratica.

Dobbiamo dimostrare che esistono due costanti c₁ e c₂ con c₂ ≠ 0 tali che

sia una invariante del ciclo.

Per i = 0 Per i = 1 Per i = 2 Per i = 3

Calcoliamo i primi valori di h:

m i

c i

c k

h i

k h

j = ( , ) = [ '( ) + ₁ + ₂ ² ]mod

) ( ' k h

j =

m k

h

j = [ '( ) +1]mod

m k

h

j = [ '( ) +1+ 2]mod

m k

h

j = [ '( ) +1+ 2 + 3]mod

e in generale

Quindi

m i

i k

h

i m k i

h j

2 mod 1

2 ) 1

( '

2 mod ) 1 ) (

( '

2 úûù êëé + +

=

úûù

êëé +

+

=

Doppio hash

La funzione hash h(k,i) si ottiene da due funzione hash ordinarie h₁(k) ed h₂(k) ponendo

Perché la sequenza di ispezione percorra tutta la tavola il valore di h₂(k) deve essere relativamente primo con m (esercizio 11.4-3 del libro).

Possiamo soddisfare questa condizione in diversi modi.

m k

ih k

h i

k

h ( , ) = [

( ) +

( )] mod

Possiamo scegliere m = 2^p potenza di 2 ed h₂(k) = 2 h'(k) + 1

con h'(k) funzione hash qualsiasi per una tavola di dimensione m' = m/2 = 2^p-1.

Un altro modo è scegliere m primo e scegliere h₂(k) che ritorna sempre un valore minore di m.

Un esempio è:

h₁(k) = k mod m e h₂(k) = 1 + (k mod m') dove m' è minore di m (di solito m' = m-1).

Con l’hash doppio abbiamo Q(m²) sequenze di ispezione distinte.

Questo riduce notevolmente i fenomeni di

addensamento e rende il comportamento della funzione hash molto vicino a quello ideale

dell’hash uniforme.

Analisi dell’indirizzamento aperto

Valutiamo la complessità media di Search in funzione del fattore di carico α = n/m.

Assumiamo l’ipotesi di hash uniforme, ossia che ogni permutazione di 0,1,..., m-1 sia ugualmente probabile come ordine di ispezione.

Notiamo che con l’indirizzamento aperto n ≤ m e quindi 0 ≤ α ≤ 1.

Proprietà: Assumendo l’ipotesi di hash uniforme, il numero medio di celle ispezionate nella ricerca di una chiave k non presente in una tavola hash con indirizzamento aperto è m se α = 1 e al più 1/(1-α) se α < 1.

Dimostrazione: Se α = 1 non ci sono celle vuote e la ricerca termina dopo aver ispezionato tutte le m celle.

Se α < 1 la ricerca termina con la prima cella vuota incontrata durante la sequenza di ispezione.

Siccome ci sono n celle occupate la probabilità che la prima cella ispezionata risulti occupata e che quindi si debba ispezionare anche la

successiva è α = n/m.

Per l’ipotesi di hash uniforme la prima cella

ispezionata può essere con uguale probabilità una qualsiasi delle m celle.

La probabilità che si debba ispezionare una terza cella è la probabilità α = n/m che la prima cella risulti occupata moltiplicata per la probabilità (n-1)/(m-1) che anche la seconda cella risulti occupata, ossia

In generale la probabilità che si debba ispezionare la i-esima cella della sequenza è

2

1

1 < a

-

× - m

n m

n

Dunque noi ispezioniamo una prima cella con

probabilità 1, una seconda cella con probabilità α, una terza cella con probabilità minore di α², una quarta con probabilità minore di α³ e così via.

Il numero atteso di celle ispezionate è quindi minore di

Conseguenza : Assumendo l’ipotesi di hash

uniforme, il numero medio di celle ispezionate

quando inseriamo una nuova chiave in una tavola hash con indirizzamento aperto è m se a = 1 e al più 1/(1-α) se α < 1.

Proprietà: Assumendo l’ipotesi di hash uniforme, il numero medio di celle ispezionate nella ricerca di una chiave k presente in una tavola hash con indirizzamento aperto è (m+1)/2 se α = 1 e al più 1/α ln [1/(1-α)] se α < 1.

Dimostrazione: Se α = 1 la chiave cercata può trovarsi, con uguale probabilità, nella prima,

seconda, ..., ultima cella e quindi il numero medio di celle ispezionate è

2 1 2

) 1 (

1 1

1

= +

× +

å

=

m m

m i m

m

m i

Se α < 1 la ricerca ispeziona le stesse celle visitate quando la chiave cercata è stata inserita nella tavola.

Supponiamo che la chiave cercata sia stata inserita dopo altre i chiavi.

Il numero medio di celle ispezionate è al più 1/(1-α) =1/(1-i/m), ossia m/(m – i).

Mediando su tutte le n chiavi presenti nella tavola otteniamo:

å å

å

-

= -

=

- = - =

m n m k n

i n

i

n m i k

m i

m m

n

1 0 1

0

1 1

1 1

a

Possiamo maggiorare la sommatoria con un integrale ottenendo

a a

a a a a

= -

= -

- -

=

£ ò

å

=

1 ln 1 ln 1

1

)) ln(

1 (ln

1 1

1 1

1

n m

m

n m

m x dx k

m

n m m

n m k

Ecco una tavola dei valori di 1/α ln [1/(1-α)]

α 1/a ln [1/(1-a)]

0.3 1.19

0.9 2.56

0.95 3.15

0.7 1.72

0.5 1.39

0.99 4.65

Alberi

Alberi radicati : alberi liberi in cui un vertice è stato scelto come radice.

Alberi liberi : grafi non orientati connessi e senza cicli.

Alberi ordinati : alberi radicati con un ordine tra i figli di un nodo.

f

c h

e a

d

g b

=

f c

h e a

d

g

libero b _f

c h

a e

d

g b

radicato

f

c h

a e

d

g b

1

1 2 3

1

1 2

ordinato

1 2 3

1 1 1 2

f

c h

e a

d

g b

≠

Alberi binari

Alberi posizionali : alberi radicati in cui ad ogni figlio di un nodo è associata una posizione.

Le posizioni che non sono occupate da un nodo sono posizioni vuote (nil).

Alberi k-ari : alberi posizionali in cui ogni posizione maggiore di k è vuota.

Alberi binari : alberi k-ari con k = 2.

Il figlio in posizione 1 si dice figlio sinistro e quello in posizione 2 si dice figlio destro.

c

b d

a e

…

… …

posizionale

c

b d

a e

k-ario (k = 4)

…

…

f

…

Alberi binari

Il modo più conveniente per descrivere gli alberi binari è mediante la seguente.

Definizione ricorsiva di albero binario:

a) l’insieme vuoto Ø è un albero binario;

b) se T_s e T_d sono alberi binari ed r è un nodo allora la terna ordinata (r, T_s ,T_d ) è un albero binario.

L’albero vuoto Ø si rappresenta graficamente con quadratino nero

Per rappresentare l’albero T = (r, T_s , T_d) si

disegna un nodo etichettato r e sotto di esso le due rappresentazioni dei sottoalberi T_s e T_d , con T_s alla sinistra di T_d

r

T_s T_d

L’albero:

T = (c, (b, (d, Ø, Ø), (a, (f, Ø, Ø), Ø)), (g, (e, Ø, Ø), Ø))

si rappresenta graficamente:

c

b g

a d

f

e

Nella memoria l’albero:

T = (c, (b, (d, Ø, Ø), (a, (f, Ø, Ø), Ø)), (g, (e, Ø, Ø), Ø)) si rappresenta nel modo seguente:

p

left right

nilc

key g

nil b

enil a nil

nil fnil

nil dnil

nil

Alberi binari di ricerca

Un albero binario di ricerca è un albero binario in cui la chiave di ogni nodo è maggiore o uguale

delle chiavi dei nodi del sottoalbero sinistro e minore o uguale delle chiavi dei nodi del

sottoalbero destro.

Ad esempio: ⁷

3 9

6 1

4

8

Operazioni sugli alberi binari di ricerca

Stampa della lista ordinata dei nodi:

Stampa(x) if x ≠ nil

Stampa(x.left) print x

Stampa(x.right)

Complessità:

T(0) = c

T(n) = T(k)+b+T(n-k-1)

Verifichiamo per sostituzione che T(n) = (c + b) n + c

T(0) = c = (c + b)0 + c

T(n) = T(k) + b + T(n-k-1) =

= (c + b)k +c+b+(c + b)(n-k-1)+c

= (c +b)n +c

Ricerca di una chiave:

Search(x, k)

if x == nil or k == x.key return x

if k < x.key

return Search(x.left, k) else

return Search(x.right, k)

Complessità O(h) dove h è l’altezza dell’albero.

Si può anche fare iterativa:

Search(x, k)

while x ≠ nil and k ≠ x.key if k < x.key

x = x.left else x = x.right return x

Complessità O(h) dove h è l’altezza dell’albero.

Ricerca del minimo e del massimo:

Minimum(x) // x ≠ nil while x.left ≠ nil

x = x.left return x

Complessità O(h) dove h è l’altezza dell’albero.

Maximum(x) // x ≠ nil while x.right ≠ nil

x = x.right return x

Ricerca di successivo e precedente Successor(x)

if x.right ≠ nil

return Minimum(x.right) y = x.p

while y ≠ nil and x == y.right x = y, y = y.p

return y

Complessità O(h) dove h è l’altezza dell’albero.

Il precedente si ottiene cambiando right in left e Minimum in Maximum.

Inserzione di un nuovo elemento

Insert(T, z) // z.left = z.right = nil x = T.root, y = nil // y padre di x

while x ≠ nil // cerco dove mettere z y = x

if z.key < y.key x = y.left

else x = y.right

z.p = y // metto z al posto della foglia x if y == nil

T.root = z

elseif z.key < y.key y.left = z

else y.right = z

Complessità O(h) dove h è l’altezza dell’albero.

Eliminazione di un elemento

Si riporta una versione semplificata, dove si spostano chiavi tra nodi diversi. Questo

potrebbe rendere inconsistenti altri puntatori, a tali nodi.

A lezione, discussa una versione che non soffre di questo problema. Vedi Libro

Paragrafo 12.3

Eliminazione di un elemento:

Delete(T, z) // z ≠ nil if z.left == nil or z.right == nil // tolgo z

y = z // che ha al più un solo figlio else // tolgo il successore di z che non ha

// sottoalbero sinistro

y = Successor(z), z.key = y.key

// cerco l’eventuale unico figlio x di y if y.left == nil

x = y.right else

x = y.left

// metto x al posto di y if x ≠ nil

x.p = y.p if y.p == nil

T.root = x

elseif y == y.p.left y.p.left = x

else

y.p.right = x

Complessità O(h) dove h è l’altezza dell’albero.

Alberi rosso-neri

Le operazioni sugli alberi binari di ricerca hanno complessità proporzionale all’altezza h dell’albero.

Gli alberi rosso-neri sono alberi binari di ricerca in cui le operazioni Insert e Delete sono opportunamente

modificate per garantire un’altezza dell’albero h = O(log n)

Bisogna aggiunge un bit ad ogni nodo: il colore che può essere rosso o nero.

Oltre ad essere alberi binari di ricerca, gli alberi rosso-neri soddisfano le proprietà:

1. ogni nodo è o rosso o nero;

2. la radice è nera;

3. le foglie (nil) sono tutte nere;

4. i figli di un nodo rosso sono entrambi neri;

5. per ogni nodo x i cammini da x alle foglie sue discendenti contengono tutti lo stesso numero bh(x) di nodi neri: l’altezza nera di x;

Notare che il nodo x non viene contato in bh(x) anche se è nero.

26

17 41

47 30

38 35 39 28

21

23 19

20 14

16

12 15

10

7 3

Esempio di albero rosso-nero:

nilc

gnil b

enil a nil

nil fnil

nil dnil

nil

26

17 41

47 30

38 35 39 28

21

23 19

20 14

16

12 15

10

7 3

E’ utile usare una sentinella al posto di nil

?

c

b g

a e

f d

?

T.nil

Proprietà: Un albero rosso-nero con n nodi interni ha altezza

h ≤ 2 log₂(n+1)

Dimostrazione: Osserviamo che i nodi rossi in un cammino dalla radice r alle foglie possono essere al più bh(r) e quindi h ≤ 2 bh(r).

Basta quindi dimostrare che bh(r) ≤ log₂(n+1) ossia che n ≥ 2^bh(r) - 1

Dimostriamo

n ≥ 2^bh(r) – 1

per induzione sulla struttura dell’albero rosso-nero.

Se T = Ø la radice r è una foglia, bh(r) = 0 e n = 0 = 2^bh(r) – 1

Sia T = (r,T₁,T₂) e siano r₁ ed r₂ le radici di T₁ e T₂ ed n₁ ed n₂ il numero di nodi interni di T₁ e T₂. Allora:

bh(r₁) ≥ bh(r)-1 bh(r₂) ≥ bh(r)-1

n = 1+ n₁ + n₂

1 2

1 2

1 2

1

1 2

1 2

1

1 1

2 1

-

= -

+ -

+

³

- +

- +

³

-

- ( ) ( )

) (

) ( )

(

r bh r

bh r

bh

r bh r

n

Per ipotesi induttiva

Conseguenza:

Su di un albero rosso-nero con n nodi interni le operazioni Search, Minimum, Maximum,

Successor e Predecessor richiedono tutte tempo O(log n)

Anche le operazioni Insert e Delete su di un albero rosso-nero richiedono tempo O(log n) ma siccome esse modificano l’albero possono introdurre delle violazioni alle proprietà degli alberi rosso-neri ed in tal caso occorre ripristinare le proprietà.

Per farlo useremo delle operazioni elementari, dette rotazioni, che preservano la proprietà di albero

binario di ricerca.

Left-Rotate(T, x)

y = x.right // y non deve essere la sentinella T.nil x.right = y.left, y.left.p = x

// y.left può essere T.nil 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

b g

a g

b a

Left-Rotate(T, x)

Complessità Q(1) x

y x

y

Right-Rotate(T, y)

x = y.left // x non deve essere la sentinella T.nil y.left = x.right, x.right.p = y

// x.right può essere T.nil 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 y.p = x, x.right = y

b g

a g

b a

Right-Rotate(T, y)

Complessità Q(1) x

y x

y

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

7 z.p.p

y z.p

z

5 9

3

7 z.p.p

y z.p

z

else if z == z.p.right // Caso 2 z = z.p

Left-Rotate(T, z)

3 9

5 7 z.p.p

y z.p

z

5 9

3

7 z.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

z.p.p 7

y z

z.p z

5 9

3

7 z.p.p

y z.p

a b

g d e

5

9

3 7

a b g

d e

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 a b

g d

5 9

e z

1 7

3

w x

a b

g d

5 9

e z

1

7 3

w x

a b g d 5

9 e z

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

w x

a b

g d

5 9

e z

1 7

3

w a b

g d

5 9

e z

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

w x

a b

g d

5 9

e z

1

7 w g

d 5

9 e z 3

x

a b

1 7

3

w x

a b

g d

5 9

e z

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

w x

a b

g d

5 9

e z

1 7

3

w x

a b

g d 5

e z

9 1

7 3

a b g d 5

9 e z

// quando termina il ciclo o x è la radice // oppure x è rosso

x.color = BLACK // Caso 0

Caso 0: x radice x

Caso 0: x rosso x 5 x 5

x 5 5

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.

key size

26

20

17

12

14

7

21

4

30

5

47

1

41

7

10

4

23

1

19

2

16

2

38

3

28

1

39

1

12

1

7

2

35

1

20

1

15

1

3

1

?

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)