Algoritmi e Strutture Dati

B B B

0 0

0

C A

C

Situazione iniziale: Inserimento a Rotazione semplice

l’albero è bilanciato sinistra nel a destra per

sottoalbero sinistro ribilanciare l’albero

Rotazione doppia a destra:

• 0

-1 -2 C

A A 0

0

0 +1 B A

B

B 0 C

C

Situazione iniziale: Inserimento a destra Rotazione doppia a

l’albero è bilanciato nel sottoalbero destra per

sinistro ribilanciare l’albero

Rotazione semplice a sinistra:

• +1 +2

A A A

0 0 0

B B B

0 0 0

C A C

Situazione iniziale: Inserimento a destra Rotazione semplice

l’albero è bilanciato nel sottoalbero a sinistra per

destro ribilanciare l’albero

Rotazione doppia a sinistra:

• 0

+1 +2 C

A A 0

0

0 -1 A B

B B

0 C

C

Situazione iniziale: Inserimento a Rotazione doppia a

l’albero è bilanciato sinistra nel sinistra per

sottoalbero destro ribilanciare l’albero

Lo sbilanciamento può, però, verificarsi in altri casi più complessi e non unicamente alla radice

dell'albero, ma anche alle radici dei suoi sottoalberi.

Di seguito sono mostrate le rotazioni in dei casi più generici.

Rotazione semplice a destra:

• -1 -2 0

A A B 0

0 -1 A

B B

h h h+1

S S

3 3 S

1

h h

h h h+1 h S

S S S S S 3

1 2 1 2 2

Situazione iniziale: l’albero Inserimento di e Rotazione semplice a destra

è bilanciato seguente sbilanciamento per ribilanciare l’albero

Rotazione doppia a destra:

• -1 -2

A A

0 +1

B B

h h

S S

2 2

0 -1

C C

h h

S S

1 1

h-1 h h-1

S S S S

3 4 3 4

Situazione iniziale: l’albero è Inserimento di e seguente

bilanciato sbilanciamento

0

C

0 1

B A

h h h-1 h

S

S S S

3

1 4 2

Rotazione doppia a destra per

ribilanciare l’albero

Rotazione semplice a sinistra:

• 1 2 0

A A B

0 0 0

B B A h+1

h h S

3

S S

1 1

h h h h+1 h h

S S

S S S S

2 2

3 3 1 2

Inserimento di e Rotazione semplice a sinistra

Situazione iniziale: l’albero seguente sbilanciamento per ribilanciare l’albero

è bilanciato

Doppia rotazione a sinistra:

• 1 2

A A

0 0

B B

h h

S S

1 1

0 0

C C

h h

S S

4 4

h

h-1 h-1

S S S S

2 3 2 3

Situazione iniziale: l’albero è Inserimento di e seguente

bilanciato sbilanciamento

0

C

0 1

A B

h h h-1 h

S S S S

1 2 3 4

Rotazione doppia a sinistra per

ribilanciare l’albero

• ESEMPIO 1: 37 70 76 29 56 42 21 25

• ESEMPIO 2: 1 2 3 4 5 6 7

• ESEMPIO 3: 5 20 13 70 56 43 9 3

Alberi di Ricerca Digitale (chiavi binarie)

Gli Alberi di Ricerca Digitale sono una struttura identica agli alberi binari (anche l’algoritmo di

ricerca è lo stesso), ad eccezione del fatto che la scelta di proseguire nel sottoalbero destro o

sinistro non è fatta in base al risultato del confronto tra chiavi, ma in base al valore di un

determinato bit della chiave da ricercare.

Inizialmente viene esaminato il bit più significativo: si prosegue nel sottoalbero sinistro se il bit vale

0, nel sottoalbero destro se il bit vale 1.

Si prosegue allo stesso modo su tutti gli altri bit della sequenza, finché non si trova la chiave,

oppure finché non si raggiunge un nodo esterno.

Il codice di ricerca è, quindi, lo stesso che vale per gli alberi binari, con la sola differenza che i

confronti fra chiavi sono sostituiti dalla chiamata della funzione bit(x, k), che restituisce il k-esimo

bit da destra della sequenza di bit x.

Ad esempio, data la tabella rappresentante una codifica delle chiavi con codici a 5 bit, dopo tutti gli

inserimenti si ottiene il seguente albero di ricerca digitale:

bit 4 3 2 1 0

1 0 1 0 1

U 0 1 1 1 0

N

E 0 0 1 0 1

S 1 0 0 1 1

0 1 1 0 1

M 1 0 0 0 0

P

I 0 1 0 0 1

O 0 1 1 1 1

0 0 1 0 0

D 1 0 0 1 1

R

C 0 0 0 1 1

A 0 0 0 0 1

L’inserimento avviene ricercando il nodo da inserire, finché non si raggiunge un nodo esterno.

A quel punto viene inserito il nodo.

In un Albero Digitale costruito con n chiavi, ciascuna di b bit, presenta i seguenti costi per le

operazioni di ricerca, inserimento e cancellazione di un elemento:

caso pessimo: b confronti.

• Infatti nessun cammino sarà più lungo del numero di bit di cui sono composte le chiavi.

caso medio: log n.

• 2

In generale, gli alberi digitali sono quasi bilanciati, visto che il successivo bit di una chiave

casuale ha uguale probabilità di essere 0 o 1.

Trie

Un Trie è un albero binario che ha una chiave associata a ciascuno dei suoi nodi esterni.

Risulta essere composto da due tipi di nodi: quelli interni, che contengono solo puntatori, e quelli

esterni, che contengono solo chiavi.

• Il Trie associato ad un insieme vuoto di chiavi è un albero vuoto.

• Il Trie associato ad una sola chiave è un nodo esterno contenente la chiave.

• Il Trie associato ad un insieme di chiavi di cardinalità maggiore di uno è un nodo interno, con

puntatore sinistro che punta al Trie associato alle chiavi il cui bit iniziale è 0 ed un puntatore

destro che punta al Trie associato alle chiavi il cui bit iniziale è 1.

La ricerca di un dato avviene attraversando l’albero in base al bit della chiave di ricerca, senza

però effettuare confronti finché non viene raggiunto un nodo esterno.

A questo punto viene effettuato il confronto della chiave di ricerca con la chiave del nodo e viene,

quindi, determinato il successo o il fallimento della ricerca.

L’inserimento di una nuova chiave prevede di fare una ricerca senza successo:

se il nodo esterno di arresto è vuoto, la nuova chiave viene inserita nello stesso nodo di

• arresto;

se il nodo d’arresto contiene già una chiave, esso viene sostituito da un nodo interno (o da più

• nodi interni, in base a quanti sono i bit che coincidono nella chiave cercata con quelli della

chiave d’arresto della ricerca) e dai nodi esterni vuoti in cui terminano i rami di ricerca senza

successo.

I costi di ricerca e di inserimento nei Trie sono analoghi a quelli degli alberi digitali di ricerca.

Per ogni insieme di chiavi esiste un unico Trie, infatti la sua struttura è indipendente dall’ordine di

inserimento delle chiavi.

Inoltre, a differenza di quello che accade negli alberi di ricerca digitale, le chiavi nei Trie appaiono

in ordine, leggendo le foglie da destra a sinistra.

4 3 2 1 0

bit

U 1 0 1 0 1

N 0 1 1 1 0

0 0 1 0 1

E 1 0 0 1 1

S

M 0 1 1 0 1

P 1 0 0 0 0

0 1 0 0 1

I 0 1 1 1 1

O

D 0 0 1 0 0

R 1 0 0 1 1

0 0 0 1 1

C 0 0 0 0 1

A

Alberi Digitali a Più Vie

Gli Alberi Digitali a Più Vie sono un modo per accorciare i cammini di un Trie, dato che una

caratteristica negativa di questi è rappresentata dai lunghi cammini in comune che possono avere

chiavi che hanno un prefisso molto lungo di bit uguali.

Chiavi che differiscono solo nell’ultimo bit, producono un

cammino lungo quanto la lunghezza delle chiavi stesse, anche

se loro fossero le due sole chiavi dell’albero, come in figura.

bit 5 4 3 2 1 0

1 0 1 0 1 0

U

N 0 1 1 1 0 0

E 0 0 1 0 1 0

1 0 0 1 1 0

S 0 1 1 0 1 0

M

P 1 0 0 0 0 0

I 0 1 0 0 1 0

0 1 1 1 1 0

O 0 0 1 0 0 0

D

R 1 0 0 1 1 0

C 0 0 0 1 1 0

0 0 0 0 1 0

A

Ricerca Casuale

La Ricerca Casuale è una tecnica di ricerca non basata sui confronti, che ha costo di ricerca

costante, indipendente dal numero di dati su cui viene effettuata la ricerca.

Questi metodi sono basati su trasformazioni delle chiavi in indirizzi e si basano sulla seguente

idea: date delle chiavi intere, distinte e comprese tra 1 e N, allora potremmo memorizzare il dato di

chiave i nella posizione i-esima di una tabella, rendendo l’accesso ai dati immediato.

I metodi Hash sono una generalizzazione di queste situazione, visto che le chiavi non soddisfano

sempre tali ottime proprietà.

Un metodo di ricerca Hash consiste nel calcolare una funzione hash che trasforma la chiave di

ricerca in un indirizzo di tabella in cui sono memorizzati i dati.

→

Questa funzione h è tale che h : K [0, …, m-1], dove K è l’insieme delle chiavi e ‘0, …, m-1’

sono gli indirizzi delle posizioni della tabella.

Idealmente a chiavi diverse k ≠ k dovrebbero corrispondere a due indirizzi differenti h(k ) ≠ h(k ),

1 2 1 2

purtroppo però, difficilmente, una funzione hash è invettiva e, quindi, due o più chiavi possono

produrre lo stesso indirizzo.

Quando per k ≠ k si ha h(k ) ≠ h(k ), si dice che si è verificata una collisione e che k e k sono

1 2 1 2 1 2

sinonimi.

Avendo una funzione hash h ed un metodo M per la risoluzione delle collisioni, la ricerca di una

chiave k funziona così:

si calcola h(k) e si controlla l’elemento in quella posizione;

1. se esso ha chiave k, la ricerca si conclude con successo.

2. In caso contrario, non si può sapere se k non è presente nella tabella, oppure, se al

momento di inserire k si era verificata una collusione e, dunque, k è stato posto in un’altra

posizione della tabella;

si applica a k il metodo M e, o si trova k, oppure si conclude che k non è presente.

3.

Se h è una buona funzione e produce poche collisioni, in un solo passo e con un solo confronto si

riesce ad accedere alla maggior parte dei dati.

In caso di collisioni, se M è un buon metodo, il numero di accessi è estremamente ridotto e,

dunque, il tempo complessivo di ricerca è quasi costante.

Le Funzioni Hash

Una funzione Hash deve trasformare chiavi (interi, stringhe) in interi compresi tra 0 e m-1, dove m

è il numero di elementi della tabella.

Una buona funzione hash ha le seguenti proprietà:

deve essere facile da calcolare, per non appesantire le operazioni ulteriori alla ricerca;

1. deve generare valori distribuiti uniformemente nell’intervallo [0, …, m-1].

2.

Una funzione Hash invettiva da K a [0, …, m-1] si dice perfetta.

Per insiemi di chiavi di tipo numerico, le funzioni hash più semplici sono del tipo h(k) = k mod m,

dove [0, …, m-1] è l’intervallo di distribuzione.

Per chiavi alfabetiche è necessario vi sia una regola di trasformazio