Mappa

Dati e Algoritmi 1: A. Pietracaprina

Descrizione generale e applicaizoni

UnaMappa`e unacollezione di entry che permette di ricercare, inserire e rimuovere entry in base alle loro chiavi(come unindice).

APPLICAZIONI:

• Database. Ad es.,studentisu Uniweb:

- chiave: numero di matricola

- valore: tutte le informazioni dello studente

• Compilatori. Ad es., per il type checking di variabili:

- chiave: nome della variabile

- valore: tipo

• Motori di ricerca. Ad es., liste invertite:

- chiave: parola

- valore: lista di documenti (ad es., pagine web)

• Data analysis. Ad es., conteggio di frequenze dioggetti:

- chiave: oggetto

- valore: numero di occorrenze

Definizione e interfaccia

Definizione di Mappa

Mappa

: collezione di entry con

chiavi distinte

provenienti da un

universo

U

su cui `

e definito l’operatore “

=

”, che supporta i metodi

get, put, e remove specificati sotto (concetto analogo di indice).

int size();

boolean isEmpty(); V get (K key);

V put (K key, V value); V remove (K key); Iterable<K> keySet(); Iterable<V> values();

Iterable<Entry<K,V>> entrySet(); }

• get(K key): se∃ (key,x)restituiscexaltrimenti restituiscenull • put(K key, V value): se∃ (key,x) mettevalueal posto dixe

restituiscex, altrimenti inserisce l’entry(key, value)e restituisce

null

• remove(K key): se∃ (key,x) rimuove la entry e restituiscex,

altrimenti restituiscenull

• keySet(),values(),entrySet(): restituiscono strutture (Iterable) contenenti, rispettivamente, le chiavi, i valori e le entry della mappa che possono essere enumerate da iteratori (iterator).

N.B.: la mappa `e vista come associative array nel senso che la chiave

della entry `e usata come un “indice” di accesso alla mappa.

Osservazioni

• Universo delle chiavi: non necessariamente ordinato. Se ordinato,

si parla diMappa ordinata(Sorted Map in Inglese) e, in questo

caso, sono possibili implementazioni pi`u efficienti al caso pessimo.

• Chiavi distinte o replicate: la Mappa assume che le chiavi siano

tutte distinte. Una variante della Mappa, chiamataMultimap,

permette di avere pi`u entry con la stessa chiave.

Noi studieremo implementazioni basate su: • Tabelle hash(Mappa)

• Alberi di ricerca (binari e non)(Mappa ordinata) e discuteremo come implementare una Multimap.

Mappa in Java

In java.util: interface Map<K,V>

al suo interno `e definita una interfaccia statica Map.Entry<K,V>

• _{l’interfaccia Map.Entry pu`o essere usata ovunque l’interfaccia Map}

sia visibile

• _{dichiarare Entry all’interno di Map serve solo per comunicare}

all’utente che verr`a usata solo nel contesto dell’uso di Map

• Entry `e statica nel senso che `e associata alla classe Map e non a

singoli oggetti di quella classe. In realt`a tutte le interfacce nested

sono static per default.

Esercizio

SiaDun documento diN parole, rappresentato da un array

D[0], D[1], . . . , D[N − 1]. Progettare un algoritmo che, usando una Mappa d’appoggio, restituisca la parola con il massimo numero di

occorrenze inD. Se ne esistono pi`u di una, l’algoritmo ne restituisce una

arbitraria tra esse.

L’uso della Mappa deve essere fatto tramite i metodi dell’interfaccia Map.

L’analisi della complessit`a sar`a effettuata in un altro esercizio, dopo aver

studiato le possibili implementazioni della Mappa.

Osservazione

Contare le frequenze delle parole `e una primitiva importante per l’analisi

statistica di documenti, utilizzata ad esempio per classificare i documenti in catergorie.

Implementazioni semplici ma inefficienti della Mappa

Si considerino le seguenti implementazioni di unaMappa di n entry:

• _{Lista (position-based): i metodi get, put, remove richiedono}

tempoΘ (n)al caso pessimo, in quantorichiedono tutti la ricerca di

una chiave (anche put) per assicurare il vincolo dellechiavi distinte. (INEFFICIENTE in TEMPO)

• Array di taglia |U|(assumendo di avere un mapping 1-1 tra chiavi e celle dell’array): i metodi get, put, remove richiedono tempo Θ (1), al caso pessimo, ma lo spazio occupato `eΘ (|U|), che potre

essere molto elevato se |U|  n. (INEFFICIENTE in SPAZIO)

Implementazione della Mappa

tramite Tabella Hash

Tabella Hash

Una Tabella Hash `

e definita dai seguenti

3 ingredienti

principali:

•

_{Funzione hash}

_h

h : U = {chiavi} → [0, N − 1]

pi`

u in particolare (convenzione Java):

h : k

−−−−−−−−−−−→ Z

−−−−−−−−−−−−→ [0, N − 1]

•

Bucket Array

A

di capacit`

a

N

.

A[i ]

rappresenta l’

i

-esimo

bucket al quale vengono associate tutte le entry

< k, v >

tali

che

h(k) = i

(

0 ≤ i < N

)

•

_{Metodo di risoluzione delle collisioni che sono costituite da}

chiavi distinte associate allo stesso bucket dalla funzione hash.

Tabelle Hash (continua)

Idea: usare il bucket

A[i ]

per memorizzare tutte le entry

< k, v >

con

h(k) = i

gestendo opportunamente le collisioni.

La scelta della funzione hash (nelle sue 2 componenti) diventa

cruciale. In particolare:

•

_h

_{deve “assomigliare” il pi`}

_{u possibile a un processo random}

(

uniform hashing

) che associa a ogni chiave in

U

un intero su

[0, N − 1]

tale che

∀k 6= k

_{∈ U}

_e

_{∀i , j ∈ [0, N − 1]}

_:

• Pr[h(k) = i ] = _N1

• Pr[h(k) = i |h(k0) = j ] = Pr[h(k) = i ] = _N1

Metodo HashCode in Java

•

metodo hashCode() della classe Object restituisce un int

che dipende dalla rappresentazione in memoria dell’oggetto.

Non assicura che l’hashCode di un oggetto rimanga inalterato

in diverse esecuzioni di un programma o in diverse

implementazioni di Java

⇒

non `

e un mapping “puro” da

U

a int

Il metodo hashCode pu`

o essere riscritto in vari modi a

seconda del tipo delle chiavi, restituendo sempre un int

Hash code per chiavi numeriche

Vediamo come trasformare in Java tipi numerici in int (Z ≡int):

• byte, short, char, intk →(int)k

• float (32 bit) k →Float.floatToIntBits(k)

• long (64 bit)k →(int) ((k >> 32)+(int k))

- “k >> 32”: 32 bit pi`u significativi

- “(int)k”: 32 bit meno significativi

N.B. solo“(int)k” perde l’informazione di met`a dei bit

• double (64 bit) k →(int) Double.doubleToLongBits(k)

- Double.doubleToLongBits(k): di tipo long

Hash code per stringhe di char

S ≡ s

s

. . . s

•

_{h(S ) =}

X

s

Oss. Non `e un buon hashcode: es.,h(stop) = h(spot) = h(tops)

•

_{Polynomial hash code}

h(S ) =

k−1

X

i =0

s

· a

Oss. Per parole inglesi vanno benea = 31, 33, 37, 39, 41. La classe

String in Java implementa il metodo hashCode in questo modo cona = 31

Hash code per stringhe di char

•

Cyclic Shift: si sommano i singoli caratteri applicando dopo

ogni addizione un cyclic shift alla somma parziale (shift di 5

posizioni va bene in pratica)

Compression Function

•

_{Division Method Dato}

_i

_{= intero prodotto dall’hash code:}

i → i mod N

dove

N

= capacit`

a del Bucket Array

Osservazione. Per una migliore distribuzione degli hash code tra gli

indici del Bucket Arrayconviene scegliere N primo e distante da una

potenza di 2.

Scelte di Npoco adeguate:

- N = 2p ⇒i mod N equivale a prendere ipbit meno

significativi dii, mentre `e meglio chei mod N dipenda da

tutti i bit dii.

- N = 10p _{⇒i mod N equivale a prendere lepcifre meno}

significative dii in base 10. Come prima non dipende da tutta

Compression Function

•

Multiply-Add-Divide (MAD) Method

i → [(ai + b) mod p] mod N

dove

• p > N conpprimo

• a, b ∈ [0, p − 1]scelti a caso,a > 0

Osservazione: il metodo MAD, leggeremente

pi`

u costoso dal

punto di vista computazionale

, assicura una

migliore distribuzione

degli hash code tra gli indici del Bucket Array

.

Risoluzione delle collisioni

Collisione:

< k

, v

>

,

< k

, v

>

con

k

6= k

e

h(k

) = h(k

)

Separate Chaining: ogni bucket `

e visto come una Map pi`

u piccola

implementata tramite lista

Open Addressing: non fa ricorso a strutture ausiliarie ma

memorizza le entry direttamente nelle celle del Bucket Array. In

questo modo si risparmia spazio ma si complica la gestione delle

collisioni. Noi non studiamo questo approccio.

Implementazione dei metodi della Mappa

Si consideri l’

implementazione di una Mappa tramite una tabella

hash (A, h) con separate chaining

.

•

_{Metodo get(}

_k

₎

if (

∃

una entry (

k

,

x

) in

A[h(k)]

) then return

x

;

else return null;

•

Metodo put(

k

,

v

)

if (

∃

una entry (

k

,

x

) in

A[h(k)]

) then

sostituisci

x

con

v

;

return

x

;

else

inserisci (

k

,

v

) in coda al bucket

A[h(k)]

;

incrementa di

1

la size della tabella;

return null;

Implementazione dei metodi della Mappa

•

_{Metodo remove(}

_k

₎

if (

∃

una entry (

k

,

x

) in

A[h(k)]

) then

rimuovi (

k

,

x

) da

A[h(k)]

;

decrementa di

1

la size della tabella;

return

x

;

Esempio

Load Factor

Definizione: Load Factor

Per una tabella hash con

n

entry si definisce il

load factor λ

come:

λ =

n

N

,

ovvero la lunghezza media di un bucket

Il load factor ha un impatto significativo sull’efficienza

computazionale di una tabella hash.

Complessit`

a di get, put e remove

Studieremo:

•

_Complessit`

_{a al caso pessimo, in funzione del numero di entry}

presenti nella tabella hash

•

_Complessit`

_{a al caso medio (definito meglio dopo), in funzione}

del load factor

λ

della tabella hash.

Assumeremo sempre che il calcolo della funzione hash per un dato

valore k della chiave richieda O (1) operazioni.

Complessit`

a al caso pessimo

Si consideri una tabella hash contenentenentry.

La complessit`a al caso pessimo di get, put, remove `e Θ (n), ed `e

dominata dalla ricerca della entry con chiavek, necessaria per tutti e tre

i metodi.

• O (n): banale

• Ω (n): (istanza cattiva) tutte le entry nello stesso bucket e chiavek assente.

Esercizio (R-10.9 [GTG14])

Stimare asintoticamente il numero di operazioni richiesto al caso migliore

(best-case) e al caso pessimo (worst-case) per l’inserimento dinentry in

una Mappa implementata tramite Tabella Hash con separate chaining,

inizialmente vuota. (Si assumaN > n.)

Complessit`

a al caso medio

Il seguente teorema dimostra che al caso medio le prestazioni della

tabella hash sono molto buone, e questo `e il motivo del suo successo e

del largo impiego.

Teorema

Sotto l’ipotesi di hashing uniform, in una tabella hash con separate

chaining e load factorλlacomplessit`a al caso medio di get, put,

remove `e O (1 + λ). Tale complessit`a vale per:

• qualsiasi chiavek non presente: in questo caso la media `e fatta su

tutti i possibili valori dih(k), che sono equiprobabili sotto l’ipotesi

di uniform hashing.

• chiavek presente: in questo caso la media `e fatta su tutte le

possibili chiavik presenti nella tabella che si assumono inserite una

dopo l’altra senza cancellazioni.

Osservazione. In pratica si suggerisce di mantenereλ < 0.9

(java.util.HashMap usa separate chaining conλ = 0.75come default)

Rehashing

Si esegue quandoλsopra la soglia prefissata (ad es., λ > 0.75):

1 creazione di un nuovo bucket array di capacit`aN0≥ 2N.

2 scelta di una nuova funzione hash.

3 trasferimento delle delle entry dalla vecchia alla nuova tabella hash.

Osservazioni:

• Il trasferimento dinentry da una tabella all’altra pu`o essere

implementato in tempoΘ (n)al caso pessimo (non serve ricercare una

entry prima di inserirla, si sa gi`a che le chiavi sono distinte).

• Dato che un rehash si esegue quandoλsupera una data costante, e la

capacit`a del bucket array almeno raddoppia, il rehash dinentry `e

preceduto daΩ (n)put senza rehash⇒il costo del rehash viene

ammortizzato (ovvero nascosto) da quello aggregato dei put.

• In un rehash pu`o essere necessario cercare un numero primo≥ 2N, che

PROS & CONS delle Hash Table

PROS

•

_{facile implementazione}

•

buone prestazioni (al caso medio)

•

_{non richiede che le chiavi vengano da un universo ordinato}

CONS

•

_complessit`

_{a elevata al caso pessimo}

•

alea dovuta alla bont`

a della funzione hash

•

_{spreco di spazio (per mantenere un basso load factor)}

Altri usi importanti delle funzioni hash: firma digitale

Consideriamo lafirma digitaledi un documentomcheAdeve

trasmettere via rete aB.

Requisiti:

• Autenticazione: il destinatario deve poter verificare l’identit`a del mittente

• Non ripudio: al mittente non deve essere permesso di disconoscere un documento da lui firmato

• Integrit`a: deve essere possibile accertare la conformit`a del documento ricevuto con quello inviato

• Privacy: a un soggetto terzo non deve poter leggere il documento Strumenti:

• Chiavi pubbliche/private: Kpub(A), Kpriv(A), Kpub(B), Kpriv(B)

• Funzione hashhin grado di mappare un messaggiomin un

Altri usi importanti delle funzioni hash: firma digitale

Implementazione della Mappa

tramite Alberi di Ricerca

•

_{Assumiamo che le chiavi provengano da un universo ordinato}

•

_{Strutture basate su alberi:}

• Albero Binario di Ricerca • Multi-Way Search Tree • (2,4)-Tree

Definizione

Definizione: Albero Binario di Ricerca

UnAlbero Binario di Ricerca`e un albero binario proprio i cui nodi interni memorizzano entry con chiavi provenienti da un universo ordinato, tale

che per ogni nodo internov la cui entry ha chiavek:

• le chiavi nel sottoalbero sx div sono< k

• le chiavi nel sottoalbero dx div sono> k

Esempio (solo chiavi)

TreeSearch

SiaT un Albero Binario di Ricerca

Algoritmo TreeSearch(k, v)

Input: chiavek, nodov ∈ T

Output: nodo diTv con chiavek, o foglia in posizione ”giusta” perk

if (T.isExternal(v) OR (v.getElement().getKey()=k)) then

returnv;

if (k < v.getElement().getKey()) then

return TreeSearch(k, T.left(v)); else

return TreeSearch(k, T.right(v))

Osservazioni

• Per ricercare in tutto l’albero si parte conv = T.root().

• Correttezza: banale

Complessit`

a di TreeSearch

Complessit`

a di TreeSearch

Analizziamo l’albero della ricorsione per TreeSearch(k,T.root()):

• L’albero ha≤ h + 1 nodi, dato che ciascuna invocazione ricorsiva di

TreeSearch scende di un livello inT.

• Ogni invocazione esegue Θ (1)operazioni, oltre a un’eventuale

chiamata ricorsiva.

• _{Esistono istanze per cui TreeSearch scende effettivamente lungo}

un cammino di lunghezzaΘ (h)(quando restituisce la foglia pi`u

profonda).

⇒complessit`aΘ (h)

Implementazione dei metodi della Mappa:

get

•

_get(

k

)

w ←

TreeSearch(

k

,

T

.root());

if

T

.isExternal(

w

) then return

null

;

else return

w

.getElement().getValue();

Complessit`

a:

Θ (h)

dominata da TreeSearch

Implementazione dei metodi della Mappa:

put

•

_put(

_k

_,

_x

₎

w ←TreeSearch(k,T.root());

if T.isInternal(w) then

y ← w.getElement().getValue();

sostituiscix ay nella entryw.getElement();

returny

trasformaw in nodo interno contenentee = (k, v )con 2 figli foglia;

e" w" w"

incrementa numero di entry di T di1;

returnnull

Complessit`

a:

Θ (h)

dominata da TreeSearch

N.B.: In [GTG14] mancano le istruzioni di return, e per trasformarew

Esempio (solo chiavi)

Esercizio R-11.1 [GTG14]

Inserire in un albero binario di ricerca vuoto 8 entry con chiavi

30, 40, 24, 58, 48, 26, 11, 13, e far vedere l’albero risultante dopo ciascun inserimento.

Esercizio

Se nell’esercizio precedente le stesse entry fossero inserite in un ordine diverso, alla fine si otterrebbe lo stesso albero? Motivare la risposta.

Implementazione dei metodi della Mappa:

remove

•

_remove(

k

)

w ←

TreeSearch(

k

,

T

.root());

if

T

.isExternal(

w

) then return

null

;

else

value

← w

.getElement().getValue();

decrementa numero di entry in

T

di 1;

if ((

T

.isExternal(

T

.left(

w

)) OR

(

T

.isExternal(

T

.right(

w

))) then

/*

w

interno e padre di almeno 1 foglia

*/

esegui Caso 1 (vedi lucidi successivi);

else

/*

w

interno e padre di 2 nodi interni

*/

esegui Caso 2 (vedi lucidi successivi);

return value;

Caso 1:

w

interno e padre di almeno 1 foglia

k"

w"

v"

u"

v"

u"

•

_se

_w

_{era radice}

⇒

u

diventa radice;

Caso 2:

w

interno e padre di 2 nodi interni

k’#

k

w#

y#

u#

z#

k’#

u#

•

_y

_{= predecessore “interno” di}

_w

_{nella visita inorder}

⇒

k

predecessore di

k

nell’ordine crescente delle chiavi

Complessit`

a di remove

•

_{Θ (h)}

_{per TreeSearch (con}

_h

_{l’altezza di}

_T

₎

•

O (h)

per trovare il predecessore interno di

w

nella visita

inorder;

•

_{O (1)}

_{per fare l’update dei nodi}

Esempio

Esercizio

Scrivere una versione iterativa di TreeSearch con la stessa specifica.

Esercizio

Progettare un algoritmo (iterativo o ricorsivo) che, dato un albero binario

di ricercaT contenete entry con chiavi reali e un intervallo[A, B],

restituisca un nodow ∈ T contenente una entry con chiavek ∈ [A, B],

se esiste, altrimenti una foglia nella posizione giusta per una chiave in [A, B], e analizzarne la complessit`a.

Esercizio

Progettare un algoritmo non ricorsivo che, dato un albero binario di

ricercaT contenete entry con chiavi reali distinte, determina la pi`u

piccola chiave positiva presente inT, e analizzarne la complessit`a. Se in

T non esistono chiavi positive, l’algoritmo deve restituire ’no positive

key’.

Esercizio

SiaT un albero binario di ricerca dove ogni nodov ∈ T memorizza in

una variabilev .sizeil numero di entry inTv (inclusa quella inv).

Progettare un algoritmo ricorsivo che conti quante entry inT hanno

Esercizio

Risolvere l’esercizio del Lucido 57 modificato per contare quante entry

hanno chiave≥ k.

Esercizio

Risolvere l’esercizio del Lucido 57 usando un algoritmo iterativo.

Esercizio

Analizzare la complessit`a dell’algoritmo sviluppato per l’esercizio del

Lucido 57 assumendo che al posto della variabile v.size si abbia a

disposizione un metodoT .size(v)che restituisce il numero di entry in

Tv, con complessit`a lineare nel valore restituito. (Suggerimento:

esprimere la complessit`a come somma di due termini, uno dei quali `e il

costo aggregato di tutte le invocazioni del metodo size.)

Esercizio

Come cambia l’algoritmo sviluppato per l’esercizio del Lucido 57 se non si hanno a disposizione le variabili size?

Esercizio

SiaT un albero binario di ricerca le cui entry rappresentano studenti di

un’universit`a. Ogni studente `e associato a una entry(k, x ), dovek `e la

matricola, ex indica se lo studente `e straniero (x = 1) o italiano (x = 0).

Per ogni nodov ∈ T esiste un interov.numStr che riporta il numero di

studenti stranieri inTv (sottoalbero con radicev). Progettare un

algoritmo ricorsivo MinMatStraniero(T , v )che dato un nodov ∈ T

restituisce la pi`u piccola matricola di uno studente straniero inTv, e

analizzarne la complessit`a. Se non ci sono studenti stranieri inTv

l’algoritmo restituisce null.

Multi-Way Search Tree (MWS-Tree)

I MWS-Tree generalizzano gli Alberi Binari di Ricerca permettendo ai

nodi di contenere pi`u entry, cosa che rende pi`u agevole il bilanciamento

(variante (2,4)-Tree)

Definizione

UnMWS-Tree T `e un albero ordinato tale che

• ogni nodo interno ha≥ 2figli

• ogni nodo interno con d ≥ 2figliv1, v2, . . . , vd (d-node) soddisfa le

seguenti propriet`a:

• memorizzad − 1entry: (k1,x1),(k2,x2),...,(kd −1,xd −1) dove

k1< k2< · · · < kd −1

• per1 ≤ i ≤ d vale che la chiave di ogni entrye memorizzata

in un nodo diTvi soddisfa la relazione

ki −1< e.getKey() < ki (assumendok0= −∞ekd = +∞).

N.B.: come per gli alberi binari di ricerca, per convenzione le foglie non memorizzano entry

Esempio di MWS-Tree (solo chiavi)

Proposizione (11.2 [GTG14])

Osservazione

Se tutti i nodi interni fossero dei

d

-node l’ MWS-Tree

T

sarebbe

un albero

d

-ario. Detto

x

il numero di nodi interni e

y

il numero di

foglie di

T

sappiamo (Problema 8 della dispensa di esercizi sugli

alberi) che

y = (d − 1)x + 1

, che `

e coerente con la proposizione

precedente dato che l’albero in questo caso memorizzerebbe

n = (d − 1)x

entry.

Ricerca in un MWS-Tree

T

(In [GTG14] l’algoritmo `e descritto solo a parole)

Algoritmo MWTreeSearch(k,v)

Input: chiavek, nodov ∈ T

Output: nodo diTv contenente una entry con chiavek, se esiste, o

foglia in posizione “giusta” perk

if (T.isExternal(v)) then returnv;

Siano(k1, x1),...,(kd −1, xd −1)le entry in v, con k1< · · · < kd −1;

(k1,x1)''''''…''''(kd*1,xd*1)'' v1' v2' vd*1' vd'

Trovai tale che ki −1< k ≤ ki (si assumak0= −∞,kd= +∞);

if (k=ki) then returnv;

Esempio: MWTreeSearch(

12

,

T

.root())

Complessit`

a di MWTreeSearch

Implementazione dei metodi della Mappa:

get

get(

k

)

w ←

MWTreeSearch(

k

,

T

.root());

if (

T

.isExternal(

w

)) then return null;

else

trova

e ∈ w

tale che

e

.getKey()

= k

;

return

e

.getValue();

Complessit`

a:

`

e dominata dal quella di MWTreeSearch, ed `

e quindi

O (d

h)

, dove

d

`

e il massimo numero di figli di un nodo e

h

`

e

l’altezza dell’albero.

(2,4)-Tree

Definizione

Un

(2,4)-Tree

`

e un MWS-Tree tale che

•

_{ogni nodo interno `}

_{e un}

_d

_{-node con}

_{2 ≤ d ≤ 4}

_;

•

_{tutte le foglie hanno la stessa profondit`}

_a.

Osservazione: Si pu`

o definire un (2,3)-Tree con

2 ≤ d ≤ 3

per il

quale si applicano gli stessi algoritmi e le stesse complessit`

a. Il

vantaggio del (2,4)-Tree `

e che si generalizza al B-tree che `

e una

struttura dati molto usata per la realizzazione di indici in memoria

secondaria (ad es., nelle basi di dati).

Esempio di (2,4)-Tree

Altezza di un (2,4)-Tree

Proposizione 11.3 [GTG14]

Un (2,4)-Tree con

n > 0

entry ha altezza

Θ (log n)

.

Il seguente corollario `

e una conseguenza immediata della

proposizione e di quanto visto prima.

Corollario

In (2,4)-Tree con

n

entry, la complessit`

a di MWTreeSearch e del

metodo get della mappa `

e

Θ (log n)

.

Dimostrazione della proposizione

Esercizio R-11.17 [GTG14]

Disegnare due (2,4)-Tree con 15 entry le cui chiavi sono gli interi da 1 a 15. Il numero di nodi deve essere minimo in un albero e massimo nell’altro.

Implementazione dei metodi della Mappa: put

IDEA:

•

_{Se la chiave non presente inserisci la nuova entry}

_{(k, x )}

_nel

nodo giusto

per

k

ad altezza 1.

•

_{Gestisci l’eventuale}

_overflow

_{(4 entry in un nodo) sfruttando}

la flessibilit`

a, se pur limitata, sul numero di entry ammissibili

in un nodo.

•

_{Se necessario, propaga l’overflow verso l’alto, eventualmente}

arrivando alla radice e facendo crescere di 1 l’altezza

dell’albero.

Implementazione dei metodi della Mappa: put

put(k,x)

w ←MWTreeSearch(k,T.root());

if (T.isInternal(w)) then

trovae ∈ w tale chee.getKey()= k;

y ← e.getValue();

sostituiscix a y ine;

returny;

e ←(k,x);

if (T.isRoot(w)) then

trasforma w in nodo interno contenente e con 2 figli foglia else

u ← T.parent(w);

inserisci e in u aggiungendo una foglia w0;

if (u `e un 5-node) then Split(u); /* overflow */

incrementa il numero di entry inT di1;

Descrizione grafica delle operazioni in rosso del lucido precedente:

e" w" w"

inserisci e in u aggiungendo una foglia w0 (w non radice):

e’# #e’’# u# e’# ##e#######e’’# u#

w# w# w’#

N.B.e0 oppure e00 potrebbe non esistere

Esempio (senza split)

put(8,x))

nuovo)) inserimento)

split(

u

)

Descritta a parole in [GTG14]

Input: 5-node

u ∈ T

, unica violazione delle propriet`

a di

(2,4)-Tree

Output: Ripristino dele propriet`

a di (2,4)-Tree

Sia

Crea

. . .

e

e

####

e

####e

u#=##

u

u

u

u

u

e

e

####

u’#=##

u

u

u

e

u’’#=##

u

u

split(

u

)

. . .

if (

!T

.isRoot(

u

)) then

v ← T

.parent(

u

);

/* vedi figura sotto */

inserisci

e

in

v

tra

e

ed

e

;

assegna

u

, u

come figli di

v

a sx e dx di

e

;

cancella

u

;

if (

v

`

e un 5-node) then split(

v

);

else

/* u `

e radice */

crea una nuova radice contenente

e

e con 2 figli

u

, u

;

cancella

u

;

…

"

e’""""e’’

""

"…"

v"=""

u

…

"

e’""""

e

""""e’’

"

"…"

v"=""

u’

u’’

Esempio

put(5,*))

split)

Esempio

put(17,*)*

split*

Complessit`

a di put

Proposizione

Per una mappa connentry implementata tramite un (2,4)-Tree la

complessit`a di put `eΘ (log n).

Esercizio (R-11.18.a [GTG14])

Inserire in un (2,4)-Tree inizialmente vuoto entry con chiavi 5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1, nell’ordine dato.

Implementazione dei metodi della Mappa: remove

IDEA:

•

Si rimuovono solo entry in nodi ad altezza 1.

•

Se la entry da rimuovere `

e in un nodo ad altezza

> 1

,

sostituiscila con una in un nodo ad altezza 1 e rimuovi quella.

•

_{Gestisci l’eventuale}

_underflow

_{(0 entry in un nodo) sfruttando}

la flessibilit`

a, se pur limitata, sul numero di entry ammissibili

in un nodo.

•

_{Se necessario, propaga l’underflow verso l’alto, eventualmente}

arrivando alla radice e facendo diminuire di 1 l’altezza

dell’albero.

Implementazione metodi della mappa: remove

remove(

k

)

w ←MWTreeSearch(k,T.root());

if (T.isExternal(w)) then return null;

else

trovae ∈ w tale chee.getKey() =k;

y ← e.getValue();

if (altezza(w)=1) then Delete(e,w,R);

else

siav il figlio diw a sx die;

z ←ultimo nodo interno nella visita in preorder diTv;

e0 ←entry con chiave max inz;

metti una copia die0 al posto die inw;

Delete(e0,z,R);

decrementa di1 il numero di entry inT;

Osservazione: quando il nodo

w

restituito da MWTreeSearch `

e ad

altezza

> 1

, la entry

e

che si sostituisce al posto di

e

in

w

`

e il

predecessore di

e

nella sequenza delle entry ordinate per chiave.

e" v" w"

e’" z"

Delete(

e

,

u

,

α

)

Descritta a parole in [GTG14]

Input: entryenel nodou ∈ T tale che il figlio a sx (α = L) o a dx

(α = R) della entry `e cancellabile

Output: rimozione die daT ripristinando le propriet`a di (2,4)-Tree

SianoA,Z i figli diu discriminati dae doveZ `e quello cancellabile;

e" u"" A"" Z"" e" u"" Z"" A"" oppure&& rimuovieeZ;

if (u non ha pi`u entry) then /* underflow */

Caso 1:

u

radice

imposta

A

come nuova radice del (2,4)-Tree;

return;

Caso 2:

u

ha un fratello

u

a sx che `

e un

d

-node, con

d ≥ 3

Esegui la seguente operazione:

…"""e’"""…

v""

A""

u

""

B""

…"""e’’"""e’’’

C"" D""

u""

…"""e’’’"…

v""

D""

u

""

B""

…"""e’’

C""

u""

e’

A""

return;

Caso 3:

u

ha un fratello

u

a dx che `

e un

d

-node, con

d ≥ 3

Esegui la seguente operazione:

…"""e’"""…

v""

A""

u""

B""

"e’’"""e’’’"…

C"" D""

u

…"""e’’""…

v""

C""

u""

A""

"""e’

B""

u

""

e’’’"…

D""

return;

Caso 4:

u

ha un fratello

u

a sx che `

e un

2

-node

Esegui la seguente operazione:

…"""e’"""…

v""

A""

u

""

B""

"""e’’

C""

u""

…"""e’"""…

v""

A""

u

""

B""

"""e’’"""e’

C""

u""

Delete(

e

,

v

,

R

);

/* propagazione verso l’alto */

return;

Caso 5:

u

ha un fratello

u

a dx che `

e un

2

-node

Esegui la seguente operazione:

…"""e’"""…

v""

A""

u

""

B""

"""e’’

C""

u""

…"""e’"""…

v""

A""

u

""

B""

"""e’"""e’’

C""

u""

Delete(

e

,

v

,

L

);

return;

Proposizione

Per una mappa connentry implementata tramite un (2,4)-Tree la

Multimap

Definizione e metodi caratterizzanti

Definizione: unaMultimap`e una Map che ammette la presenza di> 1

entry con la stessa chiave. Questa differenza richiede una modifica della specifica dei metodi caratterizzanti.

Metodi caratterizzanti:

• get(k): restituisce una collezione (eventualmente vuota) con tutti i

valori associati alle entry con chiave k

• put(k,v): inseriscesempreuna nuova entry(k, v )senza intaccare

altre entry con chiavek gi`a presenti. Non restituisce alcun output.

• remove(k,v): rimuove una entry con chiavek e valorev, se tale

entry esiste. Restituisce un boolean: yes se si `e rimossa la entry e

Implementazione

Una Multimap pu`o essere implementata tramiteuna Mappa in cui le

entry sono costituite da coppie (k, Lk), dove k `e una chiave, e Lk una

lista, non vuota, di valori associati alla chiave.

SeLk = {v1, v2, . . . , v`}, allora(k, Lk)rappresenta, in modo compatto, le

`entry(k, v1), (k, v2), . . . , (k, v`).

Implementazione dei metodi:

• get(k): se esiste una entry(k, Lk)restituisceLk, altrimenti

restituisce una collezione vuota.

• put(k, v ): se esiste una entry(k, Lk)si aggiunge semplicemente il

valore v aLk, altrimenti si aggiunge la entry (k, Lk = {v })alla

struttura.

• remove(k, v ): se esiste una entry(k, Lk)eLk contiene solo il valore

v, si rimuove la entry(k, Lk)dalla mappa, altrimenti si rimuove

(un’occorrenza di)v daLk.

Riepilogo complessit`

a per la Mappa

Si consideri unaMappa con n entry:

Metodo Tabella Hash ABR (2,4)-Tree

get(k) Θ (1 + λ) Θ (h) Θ (log n)

put(k, v) Θ (1 + λ) Θ (h) Θ (log n)

remove(k) Θ (1 + λ) Θ (h) Θ (log n)

N.B.:

• Per l’ABR, h`el’altezza dell’albero chepu`o assumere valori

compresi tra Θ (log n) e Θ (n).

• Le complessit`a per la Tabella Hash sono al caso medio eλ`e ilload

factor.

Riepilogo complessit`

a per la Multimap

Si consideri unaMultimap con n entry:

Metodo Tabella Hash ABR (2,4)-Tree

get(k) Θ (1 + λ) Θ (h) Θ (log n)

put(k, v) Θ (1 + λ) Θ (h) Θ (log n)

remove(k, v) Θ (s + 1 + λ) Θ (s + h) Θ (s + log n)

N.B.:

• Per l’ABR, h`el’altezza dell’albero chepu`o assumere valori

compresi tra Θ (log n) e Θ (n).

• Il termines nelle complessit`a di remove indica il massimo numero di

entry con la stessa chiave.

• Nelle complessit`a per la Tabella Hash, il termine1 + λ(doveλload

factor) si riferisce al tempo medio di ricerca della chiave, mentre, nel

Esercizio

Progettare e analizzare un algoritmo iterativo efficiente che determini l’altezza di un (2,4)-Tree.

Esercizio

SiaT un (2,4)-Tree dove ogni nodov ∈ T memorizza in una variabile

v .sizeil numero di entry inTv (incluse quelle inv). Progettare un

algoritmo ricorsivo che conti quante entry inT hanno chiave≤ k, e

analizzarne la complessit`a.

Esercizio

Risolvere l’esercizio precedente tramite un algoritmo iterativo.

Esercizio

Analizzare l’algoritmo 24CountLE assumendo che al posto della variabile v .sizesi abbia a disposizione un metodoT .size(v)che restituisce il

numero di entry inTv, con complessit`a lineare nel valore restituito.

Esercizio

SianoT eU due (2,4)-Tree di altezzahe tali che la massima chiave in

T `e minore della minima chiave inU.

1 Progettare un algoritmo di complessit`a O (h)per fondereT eU in

un unico (2,4)-TreeTU.

Esercizio

SianoT eU due (2,4)-Tree contenenti rispettivamentenedmentry e

tali che la massima chiave inT `e minore della minima chiave inU.

Progettare un algoritmo di complessit`aO (log n + log m)per fondereT e

U in un unico (2,4)-TreeTU.

Suggerimento: Se i due alberi hanno altezze diverse, fondere l’albero di altezza minore con un opportuno sottoalbero dell’altro di uguale altezza (utilizzando l’algoritmo sviluppato per l’esercizio del Lucido 121), e sostituirlo a tale sottoalbero.

Esercizio

Analizzare la complessit`a dell’algoritmo sviluppato per l’esercizio del

Lucido 7, scegliendo una opportuna implementazione per la Mappa.

Riepilogo

•

Mappa: definizione come ADT

•

_{Tabelle Hash:}

• Ingredienti principali

• Funzione hash: hash code e compression function

• Risoluzione delle collisioni tramite chaining

• _{Implementazione dei metodi della Mappa e loro complessit`a al}

caso medio sotto l’ipotesi di uniform hashing

• Load factor e rehashing

•

_{Alberi Binari di Ricerca}

• Definizione

• Metodo TreeSearch

Riepilogo

•

_(2,4)-Tree

• _{Definizione di Multi-Way Search (MWS) Tree}

• Relazione tra numero di entry e foglie in un MWS-Tree

• Metodo MWTreeSearch

• Definizione di (2,4)-Tree

• Altezza di un (2,4)-Tree

• Implementazione dei metodi della Mappa

•

_{Implementazione di una Multimap}