Algoritmi e Strutture Dati
Anteprima
ESTRATTO DOCUMENTO
Pila
Una Pila (o Stack) è una lista lineare a lunghezza variabile, dove inserimenti ed estrazioni vengono
effettuate solo in un estremo, detto testa (o top) della pila.
Si basa sul principio del “last in first out”, LIFO, ossia che l’ultimo elemento ad essere inserito è poi
il primo ad essere estratto. Operazioni su una Pila
push(e) Operazione di inserimento.
Viene inserito un elemento e al top della pila.
pop() Operazione di estrazione.
Viene estratto l’elemento in quel momento presente al top della pila.
isEmpty() Operazione di controllo se la pila è vuota (restituisce true) o meno (restituisce false).
Una Pila può essere implementata sia tramite una catena, con le operazioni di push e pop che
avverranno in testa alla catena, che tramite un vettore.
Per quanto riguarda l’implementazione attraverso un vettore, è necessario stabilire a priori la
dimensione n massima della pila e sarà necessario tenere conto della posizione dell’elemento top
attraverso un contatore, che sarà l’elemento nella posizione non vuota più a destra nel vettore.
x x x x x
0 1 2 3 top n-1
Assumendo che top = -1 indichi la pila vuota, le due operazioni di inserimento ed estrazione
possono essere schematizzate come segue:
Operazione di inserimento: push(e) Costo Algoritmo
top = top + 1;
se top ≥ n
allora overflow; O(1)
altrimenti
v[top] = e;
Operazione di estrazione: pop() Costo Algoritmo
se top = -1
allora underflow;
altrimenti O(1)
restituisci v[top];
top = top - 1;
Espressioni Infisse e Postfisse con una Pila
Attraverso una Pila è possibile trasformare una espressione infissa in una espressione postfissa
(ossia un’espressione scritta con l’operatore dopo i suoi operandi) e valutare, inoltre, quest’ultima.
Entrambi i processi di trasformazione e valutazione sono illustrati qui sotto.
Infissa a Postfissa Esempio
→
se “(“ niente;
→
se operando scrivi nel risultato;
→
se operatore push(operatore); Risultato:
→ ·
se ”)” scrivi(pop()) nel risultato; + +
·
· · ·
Valutazione Postfissa Esempio
→
se operando push(operando);
→
se operatore push(pop () operatore pop ());
2 1 6
8 4 24 7
9 415
17 17 408
5 5 5 5 5 2075
Coda
Una coda (o Queue) è una lista lineare, dove l’inserimento viene effettuato ad un estremo fondo (o
real) e l’estrazione dall’altro estremo testa (o front).
Si basa sul principio del “first in first out”, FIFO, ossia che il primo elemento ad essere inserito è poi
anche il primo ad essere estratto. Operazioni su una Coda
put(e) Operazione di inserimento.
Viene inserito un elemento e al rear della coda.
get() Operazione di estrazione.
Viene estratto l’elemento in quel momento presente al front della coda.
isEmpty() Operazione di controllo se la coda è vuota (restituisce true) o meno (restituisce false).
Come una Pila, anche una Coda può essere facilmente implementata attraverso un vettore.
Dunque, è necessario stabilire a priori la dimensione n massima della coda e sarà necessario
tenere conto della posizione nel vettore del front (testa) e del rear (fondo), attraverso due contatori
F e R.
F è, quindi, l’indice della posizione del vettore contenente la testa della coda; se la coda è vuota il
valore di F sarà uguale ad R (F = R).
R è, invece, l’indice della prima posizione libera del vettore, ossia dove verrà effettuato il
successivo inserimento.
Inizialmente viene posto F = R = 0, per indicare che la coda è vuota.
Ad ogni inserimento, R deve essere incrementato per indicare la posizione successiva libera.
Invece, ad ogni estrazione, F deve essere incrementato per indicare l’elemento testa successivo
della coda.
Questo tipo di implementazione presenta un problema: dopo molti inserimenti e cancellazioni, la
parte occupata dagli elementi della coda tende a spostarsi verso il fondo del vettore e, quando
R = n-1, non è più possibile inserire nuovi elementi, anche se si effettuassero delle estrazioni.
x x x
0 1 2 F R n-1
Per potere allora sfruttare sempre tutte le n posizioni del vettore, conviene pensare il vettore
stesso come una struttura circolare, in cui il primo elemento segue logicamente l’ultimo.
x x x x x x x
0 1 R F n-1
Questa modifica però presenta un problema, dato che nel caso in cui F = R non si è in grado di
distinguere il caso in cui la coda sia vuota da quello in cui la coda sia piena.
La soluzione che si può prendere in considerazione è quella di sacrificare una posizione del
vettore, quindi in un vettore di n elementi se ne potranno memorizzare n-1, e richiede di
incrementare subito R quando si vuole fare un inserimenti, in modo che se dopo l’incremento di R
risulta F = R, allora vuol dire che la coda contiene già n-1 elementi ed è quindi piena (overflow).
Se, invece, vi era F = R prima dell’incremento, cioè il vettore è vuoto, dopo l’incremento risulterà
F ≠ R.
Di seguito sono illustrati gli algoritmi di inserimento ed estrazione in una coda Q.
Operazione di inserimento: put(e) Costo Algoritmo
se R = n-1
allora A = 0;
altrimenti
A = R + 1;
se F = A O(1)
allora overflow;
altrimenti
Q[R] = e;
R = A;
Operazione di estrazione: get() Costo Algoritmo
se F = R
allora underflow;
altrimenti
restituisci Q[R];
se F = n-1 O(1)
allora F = 0;
altrimenti
F = F + 1;
Anche una Coda, comunque, può essere implementata attraverso le liste concatenate, in modo da
risolvere il problema di dover stabilire a priori il numero massimo di elementi inservibili nella coda
stessa.
Il front della coda, in questo caso, coinciderà con la testa della lista, mentre il rear coinciderà con la
coda della lista.
Per mantenere un riferimento alla posizione della testa e delle coda della lista si fa uso di due
puntatori head e tail.
Una Coda può anche essere memorizzata in un anello, con un puntatore all’ultimo elemento in
modo che in un solo passo si possa accedere alla testa.
Coda con Priorità
Una Coda con Priorità è un tipo di coda i cui elementi hanno associato un valore, detto priorità, in
base al quale sono vincolate le estrazioni.
Elementi con priorità maggiore vengono estratti per primi, mentre elementi con pari priorità
vengono estratti secondo il loro ordine di inserimento nella coda.
Si basa sul principio del “largest in first out”, LIFO, ossia che il primo elemento ad essere estratto è
quello ad avere priorità più alta. Operazioni su una Pila
construct Operazione di costruzione di una coda con priorità a partire da n dati.
Può essere realizzata da una serie di n insert.
insert Operazione di inserimento.
remove Operazione di estrazione.
replace Operazione di sostituzione dell’elemento con priorità maggiore con un elemento
qualsiasi.
Può essere realizzata combinando insert e remove.
change Operazione di modifica della priorità di un elemento.
Può essere realizzata combinando delete e insert.
delete Operazione di cancellazione di un elemento specifico.
join Operazione di fusione di due code con priorità.
L’implementazione più semplice di una coda con priorità è quella attraverso un vettore, che può
essere disordinato od ordinato in base alla priorità dei suoi elementi.
Di seguito sono illustrati gli algoritmi di inserimento ed estrazione in una coda con priorità Q,
implementata con un vettore disordinato, usando un contatore m per tenere memorizzata la
posizione dell’ultimo elemento inserito.
x x x x x
0 1 2 m n-1
Operazione di inserimento: insert(e) Costo Algoritmo
se m = n
allora overflow;
altrimenti O(1)
Q[m] = e;
m = m + 1;
Operazione di estrazione: remove() Costo Algoritmo
se m = 0
allora underflow;
altrimenti
max = 0;
per j = 1, …, n-1 O(m)
se Q[j] > Q[max]
allora max = j;
restituisci Q[max];
m = m - 1;
Q[max] = Q[m];
Di seguito sono, invece, illustrati gli algoritmi di inserimento ed estrazione in una coda con priorità
Q, implementata con un vettore ordinato in base alla priorità dei suoi elementi, usando un
contatore m per tenere memorizzata la posizione dell’ultimo elemento inserito.
Operazione di inserimento: insert(e) Costo Algoritmo
se m = n
allora overflow;
altrimenti
j = m - 1;
finché j ≥ 0 e Q[j] > e O(m)
Q[j+1] = Q[j];
j = j - 1;
Q[j+1] = e;
m = m + 1;
Operazione di estrazione: remove() Costo Algoritmo
se m = 0
allora underflow;
altrimenti O(1)
restituisci Q[m-1];
m = m - 1; Inserimento Cancellazione
Vettore Disordinato O(1) O(m)
Vettore Ordinato O(m) O(1)
Heap
Lo Heap è una struttura dati rappresentata da un vettore, occupato a partire dalla posizione di
indice 1, che soddisfa la condizione di heap.
La condizione di heap dice che per ogni j, 1 ≤ j ≤ n/2, la chiave in posizione j deve essere maggiore
delle due chiavi in posizione 2j e 2j+1.
L’elemento in posizione j viene chiamato padre, dei due figli rappresentati dagli elementi in
posizione 2j e 2j+1.
Uno Heap è dunque un vettore non completamente ordinato, in cui però la chiave più grande di
tutte si trova sempre nella prima posizione del vettore.
Se una coda con priorità venisse implementata attraverso uno Heap, tutte le sue operazioni
verrebbero eseguite in tempo logaritmico.
Questo accade poiché in uno Heap contenente m elementi, ogni volta che si passa dal padre ai
figli si raddoppia l’indice dell’elemento; partendo dall’elemento di indice 1 si può al massimo
raddoppiare log m volte, dopodiché si raggiunge la fine dello heap.
2
Allo stesso modo, partendo dall’elemento di indice m e saltando verso il padre si dimezza m e
questo può ripetersi al massimo log m volte, dopodiché si è raggiunta la cima dello heap.
2
In uno Heap, gli algoritmi agiscono apportando semplici modifiche strutturali, che però spesso
portano a violare la condizione di heap, ma in un secondo momento lavorano a ripristinare questa
condizione.
Alcuni algoritmi operano dalla cima verso il fondo dello heap, altri dal fondo verso la cima.
Di seguito sono descritte le operazioni di inserimento e di estrazione in uno heap H, di dimensione
n, con m dati già inseriti in esso.
Operazione di inserimento: insert(e) Costo Algoritmo
se m ≤ n-1 O(log m)
2
allora m = m + 1;
H[m] = e; Nell’operazione di inserimento, l’elemento e viene
upheap(m); inserito nella prima posizione libera dopo l’ultimo
altrimenti elemento nel vettore.
overflow;
upheap(k) Nell’algoritmo di inserimento insert(e) viene
temp = H[k]; richiamato il metodo upheap(k), che è responsabile
H[0] = +∞; del ripristino della condizione di heap, muovendosi
finché H[K/2] ≤ temp dal fondo verso la cima del vettore.
H[k] = H[k/2] Viene confrontato il padre dell’elemento inserito con
k = k/2; l’elemento e se esso risulta essere minore, essi
H[k] = temp; vengono sostituiti di posizione.
Operazione di estrazione: remove() Costo Algoritmo
se m > 0 O(log m)
2
restituisci H[1];
H[1] = H[m]; Nell’operazione di estrazione, viene restituito
m = m - 1; l’elemento in posizione 1 del vettore e,
downheap(1); successivamente, in quella posizione, viene inserito
altrimenti l’ultimo elemento presente nel vettore.
underflow; Infine, viene ripristinata la condizione di heap.
downheap(k)
temp = H[k]; Nell’algoritmo di estrazione remove() viene
finché k ≤ m/2 richiamato il metodo downheap(k), che è
j = 2·k; responsabile del ripristino della condizione di heap,
se (j < m) e (H[j] < H[j+1]) muovendosi dalla cima verso il fondo del vettore.
allora j = j + 1; Viene confrontato l’elemento in posizione k con i
se temp < H[j] suoi figli, se uno dei due risulta maggiore del padre,
allora H[k] = H[j]; quest’ultimo viene sostituito dal figlio maggiore.
k = j;
H[k] = temp;
Alberi
Gli Alberi sono delle strutture dati bidimensionali, consentono di rappresentare relazioni 1:n.
Esistono diversi tipi di alberi, tra i quali troviamo in ordine decrescente di generalità:
- Alberi (o Alberi Liberi)
- Alberi con Radice
- Alberi Ordinati
- Alberi m-ari (e Alberi Binari)
Un Albero T è una coppia di insiemi T = (N, A), dove V è l’insieme dei nodi (o vertici) ed A è
l’insieme degli archi (o rami) che collegano i nodi.
L’insieme A = { (x,y) | x,y N } è un insieme di coppie di elementi di N, detti archi, tali che per ogni
∈
coppia di nodi dell’albero esiste uno ed uno solo cammino che li unisce.
Un nodo (o vertice) è un oggetto contenente un’informazione.
Un arco (o ramo) è una connessione tra due nodi e, quindi, esprime una relazione tra i due.
Un cammino in un albero è una sequenza di nodi (v , v , …, v ), solitamente indicata dal simbolo π.
0 1 k
Quindi, ad esempio, il cammino da x ad y risulta essere π = (v , v , …, v ), con v = x e v = y, tali
0 1 k 0 k
∀
che (v , v ) A i = 1, …, k-1.
∈
i i+1
Si definisce lunghezza del cammino il numero di archi che lo compongono: l(π) = k.
Se alcune coppie di nodi sono unite da più cammini o non sono unite da alcun cammino, la
struttura non risulterà essere un albero, ma un grafo.
Un insieme disgiunto di alberi viene detto foresta.
Un albero con radice è un albero in cui un nodo viene scelto come radice dell’albero.
In questo modo esiste un elemento che non dipende da nessun altro ed ogni altro elemento
dipende da uno ed uno solo elemento.
In un albero con radice, ogni nodo è radice di un sottoalbero costituito dal nodo stesso e dai nodi
sotto di esso.
Ciascun nodo, esclusa la radice, ha esattamente un nodo al di sopra, detto padre, mentre i nodi al
di sotto vengono detti figli.
I nodi senza figli sono detti foglie.
Un albero ordinato è un albero con radice, in cui è significativo l’ordine con cui compaiono i figli di
ciascun nodo.
Un albero m-ario è un albero ordinato, in cui ogni nodo ha uno specifico numero m di figli (detto
arietà dell’albero).
Alberi Binari
Il più semplice albero m-ario è l’albero binario.
Un albero binario è un albero ordinato, formato da due tipi di nodi: i nodi esterni, che non hanno
figli, e i nodi interni, che hanno esattamente due figli, che, essendo ordinati, vengono chiamati figlio
sinistro e figlio destro.
La rappresentazione di un albero binario maggiormente usata è quella attraverso una struttura
concatenata con due puntatori per ogni nodo interno, dove il puntatore sinistro punta alla radice del
sottoalbero sinistro, mentre il puntatore destro punta al sottoalbero destro.
Per ogni albero ordinato esiste un albero binario corrispondente.
Per passare dall’albero ordinato all’albero binario viene seguita la rappresentazione in cui come
figlio sinistro dell’albero binario verrà scelto il primo figlio di un nodo dell’albero ordinato, mentre
come figlio destro il primo fratello.
PROPRIETÀ DEGLI ALBERI BINARI:
Un albero binario con n nodi interni ha n+1 nodi esterni.
• Il livello della radice è zero, il livello di ogni altro nodo è il livello del padre più uno.
• L’altezza di un albero è il massimo livello dei suoi nodi.
• La lunghezza di un cammino è il numero di archi di cui è composto il cammino.
• La lunghezza del cammino interno di un albero binario, è la somma delle lunghezze dei cammini
• che collegano la radice a tutti i nodi interni, cioè la somma dei livelli di tutti i nodi interni
dell’albero: ogni livello viene moltiplicato per quanti nodi contiene e la somma di tutti dà il
cammino interno.
Allo stesso modo, la lunghezza del cammino esterno di un albero binario è la somma delle
lunghezze dei cammini che collegano la radice a tutti i nodi esterni, cioè la somma dei livelli di
tutti i nodi esterni dell’alberi.
Considerando un albero binario con n nodi interni (e, quindi, n+1 nodi esterni), ed indicando con
• I la lunghezza del cammino interno e con E la lunghezza del cammino esterno, esiste la
n n
seguente relazione: E = I + 2n.
n n
Considerando un albero binario di altezza h con n nodi interni:
• Considerando un albero binario con n nodi interni:
• Un albero binario, se degenera in una lista, avrà altezza n, ossia il numero dei suoi nodi interi.
•
Attraversamento degli Alberi
Esistono due criteri di attraversamento per gli alberi ordinati: l’attraversamento anticipato e
l’attraversamento posticipato.
Per gli alberi binari, esiste anche l’attraversamento simmetrico.
Attraversamento Anticipato: attraversa(R) Descrizione
visita(R); L’attraversamento anticipato consiste nel visitare la
attraversa(left(R)); radice R e poi nell’attraversare in ordine anticipato
attraversa(right(R)); tutti i suoi sottoalberi, da sinistra a destra.
Attraversamento Posticipato: attraversa(R) Descrizione
attraversa(left(R)); L’attraversamento posticipato consiste
attraversa(right(R)); nell’attraversare in ordine posticipato tutti i
visita(R); sottoalberi, da sinistra a destra, ed infine visitare la
radice R.
Attraversamento Posticipato: attraversa(R) Descrizione
L’attraversamento simmetrico consiste
attraversa(left(R)); nell’attraversare in ordine simmetrico il sottoalbero
visita(R); sinistro, poi visitare la radice R e, quindi,
attraversa(right(R)); attraversare in ordine simmetrico il sottoalbero
destro.
Di seguito, viene illustrata l’implementazione dell’attraversamento anticipato di un albero con
radice R attraverso una pila astratta.
Attraversamento Anticipato: attraversa(R)
attraversa(R)
push(tree(R));
finchè(!empty())
x = pop();
se x = node(y) allora visita(y) attraversamento posticipato
se x = tree(y) allora push(tree(right(Y)))
push(tree(left(y)))
push(node(y)) attraversamento simmetrico
Di seguito sono illustrati alcuni esempi di attraversamento di alberi:
• ESEMPIO 1 (CON PILA ASTRATTA):
A
B C Attraversamento Anticipato: A B D C E F
D E F
node(A) node(B)
tree(B) tree(D) node(N) node(C) node(E)
tree(A) tree(C) tree(C) tree(C) tree(E) tree(F) node(E)
• ESEMPIO 2 (CON TRASFORMAZIONE IN AB):
Attraversamenti:
- Anticipato: A B E H F I J K C D G
- Posticipato: H K J I F E G D C B A
- Simmetrico: H E I J K F B C G D A
Alberi Binari di Ricerca
Un Albero Binario di Ricerca (ABR) è un albero binario che ha una chiave associata ad ogni suo
nodo e soddisfa la seguente proprietà: per ogni suo nodo, la chiave in esso memorizzata è
maggiore di tutte le chiavi memorizzare nei nodi del suo sottoalbero sinistro e minore di tutte le
chiavi memorizzate nei nodi del suo sottoalbero destro.
K
≤K ≥K
Le operazioni effettuabili su un albero binario di ricerca sono di carattere locale, come la ricerca di
un nodo, l’inserimento, la cancellazione, o di carattere globale, come l’ordinamento.
L’inserimento di un nodo avviene dopo aver ricercato la posizione che gli compete nell’albero,
ovvero confrontando inizialmente il nodo con la radice e poi proseguendo nel sottoalbero sinistro o
destro a seconda del valore della chiave del nodo.
Se la ricerca termina con successo, significa che il nodo è già presente nell’albero, altrimenti si
raggiunge un nodo il cui sottoalbero sinistro o destro è vuoto e, quindi, si può inserire il nodo come
figlio sinistro o destro del nodo.
La cancellazione di un nodo è, invece, più complessa: se il nodo da cancellare è una foglia, il
problema è banale.
Se, invece, il nodo da cancellare ha un sottoalbero destro o sinistro vuoto, basta, una volta
cancellato, sostituirlo con la radice del suo sottoalbero.
Se, però, il nodo da cancellare ha entrambi i sottoalberi non vuoti, per mantenere l’ordinamento è
necessario sostituirlo con il valore immediatamente successivo, che si trova come elemento più a
sinistra del sottoalbero destro del nodo da cancellare.
Per quanto riguarda l’ordinamento delle chiavi memorizzate in un ABR, è sufficiente elencare gli
elementi secondo l’attraversamento simmetrico per ottenerne l’ordine preciso.
Ogni albero binario di ricerca può essere costruito a partire dalle n! possibili permutazioni delle n
chiavi.
La complessità della ricerca in un ABR è strettamente legata alla forma dell’albero: se l’albero è
completo, ci saranno circa log n nodi in ogni cammino dalla radice ad un nodo esterno, ma se
2
l’albero degenera in una lista, si può avere anche un cammino di lunghezza n.
L’altezza di un ABR equivale al costo della ricerca nel caso pessimo, mentre la lunghezza del
cammino interno e di quello esterno sono correlate al costo medio, rispettivamente, della ricerca
con successo e senza successo.
Le operazioni di ricerca con successo, inserimento e ricerca senza successo in un ABR hanno un
costo medio di 2lnn ≈ 1.39log n.
2
Il costo medio per l’inserimento di una chiave è pari a .
Infatti il numero medio dei confronti fatti per inserire una chiave n si trova dividendo la lunghezza
media del cammino interno dell’albero per il numero totale dei suoi nodi.
Il costo medio per la ricerca con successo è pari a .
Infatti, il costo per la ricerca con successo di una chiave è uguale al costo per il suo inserimento,
più il confronto con se stessa.
Il costo medio per la ricerca senza successo è pari a .
Infatti il costo di una ricerca senza successo è pari alla lunghezza del cammino esteso, diviso il
numero n + 1 dei nodi esterni.
Ma, essendo E = I + 2n, dunque, si ha il risultato indicato.
n n
Le n! permutazioni di n chiavi generalo solo alberi binari distinti.
Alberi 2-3
Gli Alberi 2-3 sono dei particolari alberi binari, con la particolarità che crescono dalla parte della
radice e mantengono le foglie tutte sullo stesso livello.
Un Albero 2-3 è composto da nodi 2-3.
Un Nodo 2-3 è un insieme ordinato contenente due chiavi k e k , in ordine crescente, e tre
1 2
puntatori p , p e p , tali che:
0 1 2
p punta al sottoalbero contenente chiavi k tali che k < k .
• 0 1
p punta al sottoalbero contenente chiavi k tali che k < k < k .
• 1 1 2
p punta al sottoalbero contenente chiavi k tali che k > k .
• 2 2
k k
1 2
p p p
0 1 2
k < k k > k
k < k < k
1 2
1 2
Inoltre, gli Alberi 2-3 verificano le seguenti proprietà:
le foglie sono tutte sullo stesso livello;
• ogni nodo ha al più tre figli.
•
La ricerca di una chiave k in un Albero 2-3 avviene confrontando la chiave da ricercare con il
contenuto di un nodo a partire dalla radice.
In questo caso, però, in ciascun nodo ci possono essere due chiavi ed e dunque necessario
eseguire una successione di confronti:
se k < k , allora la ricerca prosegue nel sottoalbero indicato da p ;
• 1 0
se k = k , allora la ricerca termina con successo;
• 1
se nel nodo c’è una sola chiave, la ricerca prosegue nel sottoalbero indicato da p .
• 1
Invece, se nel nodo ci sono due chiavi, è necessario eseguire ulteriori confronti;
se k < k < k , allora la ricerca prosegue nel sottoalbero indicato da p .
• 1 2 1
se k = k , allora la ricerca termina con successo;
• 2
se k > k , allora la ricerca prosegue nel sottoalbero indicato da p .
• 2 2
L’inserimento di una nuova chiave avviene dopo aver eseguito una ricerca senza successo, ossia
una ricerca che si arresta su un nodo dal quale dovrebbe proseguire tramite un puntatore vuoto.
Le azioni successive dipendono dal nodo di arresto: se contiene una sola chiave, la nuova chiave
viene inserita nel nodo stesso, ordinata con quella precedente.
Se, invece, il nodo contiene già due chiavi, si considera l’insieme ordinato (k , k , k ) costituito
1 2 3
dalle due chiavi del nodo e dalla nuova chiave.
Il nodo di arresto viene suddiviso in due nodi contenenti rispettivamente k e k , mentre k viene
1 3 2
inserito nel padre del nodo di arresto, assieme ai due puntatori ai nodi contenenti k e k .
1 3
Questa operazione può ripetersi a ritroso fino alla radice e, nel caso in cui sia necessario
suddividere anche la radice, l’altezza dell’albero viene incrementata di una unità.
La cancellazione è un’operazione piuttosto complessa e consiste nel ricompattare gli eventuali
nodi interessati.
Spesso si preferisce effettuare una cancellazione logica delle chiavi, che risulta essere meno
complessa.
Questa consiste nell’associare ad ogni chiave un indicatore che vale 0 per tutti gli elementi
effettivamente presenti nell’albero e 1 per quelli cancellati.
In questo modo, cancellare una chiave significa mettere a 1 il suo indicatore, senza apportare
modifiche all’albero.
L’altezza h di un Albero 2-3 con n è così limitata: log (n+1) ≤ h ≤ log (n+1).
3 2
Dimostrazione:
Il numero minimo di chiavi presenti in un Albero 2-3 di altezza h corrisponde al caso in cui ogni nodo contiene una sola
chiave e, dunque, ha solo due figli. 2 h-1 h-1
Perciò, indicato con n il numero di chiavi dell’albero, risulta: n ≥ 1+2+2 +…+2 = 2 .
Il numero massimo di chiavi, invece, lo si ha quando in ogni nodo ci sono due chiavi e, dunque, ogni nodo ha tre figli,
2 h-1 2 h-1 h
perciò: n ≤ 2+2·3+2·3 +…+2·3 = 2(1+1·3+1·3 +…+1·3 ) = = 3 - 1.
Passando ai logaritmi, si ottiene il risultato sopracitato.
L’altezza dell’albero costituisce una limitazione superiore al costo delle operazioni di ricerca, di
inserimento e di cancellazione fisica.
Ad esempio, la complessità massimo della ricerca è cerca 1.5log (n+1).
2
Di seguito sono illustrati alcuni esempi di attraversamento di alberi:
• ESEMPIO 1: 5 11 27 42 1 14 33 7 3 89 40 12
5 — 11 — 27 14 — 27 — 42
5 11 11 11
5 27 42 1 5 27 42
1 — 5 — 7
11 27 11 27
1 5 14 42 1 5 14 33 42 33 — 24 — 39
11
5 27
1 3 7 14 33 42
11
5 27 42
1 3 7 14 33 89
11
5 27 42
1 3 7 12 14 33 40 89
• ESEMPIO 2: 10 30 20 35 25 27 22
10 — 20 — 30 25 — 30 — 35
10 30 20 20 30
10 30 35 10 25 27 35
22 — 25 — 27 25
20 30
10 22 27 35
• ESEMPIO 3: 70 76 37 82 29 56 42 47 21 41 85 35
37 — 70 — 76
70 76 70 70
37 76 82 29 37 76 82
29 — 37 — 56 37 70 37 70 42 — 47 — 56
29 56 76 82 29 42 56 76 82
47 47
37 70 37 70
29 42 56 76 82 21 19 41 42 56 76 82
76 — 82 — 85 21 — 29 — 35
47
37 70 82
21 29 41 42 56 76 85
47
29 70 82
37
21 41 42 56 76 85
35
Alberi Bilanciati (o AVL)
Un Albero Bilanciato (o AVL) è un albero di ricerca, i cui nodi hanno fattori di bilanciamento 0, 1
oppure -1.
Per fattore di bilanciamento di un nodo si intende la differenza tra l’altezza del suo sottoalbero
destro e l’altezza del suo sottoalbero sinistro.
Le operazioni di inserimento e cancellazione possono portare allo sbilanciamento dell’albero e,
quindi, devono essere accompagnate da alcune operazioni che consentano di ripristinare la
proprietà degli alberi AVL.
Le operazioni che ripristinano le proprietà di bilanciamento sono dette rotazioni.
Le rotazioni sono di due tipi: semplici (a destra o a sinistra), oppure doppie (a destra o a sinistra).
Di seguito sono illustrate le rotazioni in dei casi basilari, molto semplici.
Rotazione semplice a destra:
• -1 -2
A A A
0 -1 0
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 trasformazione in valori numerici.
Metodi per la risoluzione delle collisioni
I metodi di risoluzione delle collisioni possono essere suddivisi in due categorie: quelli che
sfruttano strutture concatenate per memorizzare i sinonimi e quelli che calcolano nuovi indirizzi.
Catene Separate: questo metodo di risoluzione di collisioni organizza la tabella in modo che i
• suoi elementi contengano solo puntatori a catene: in ciascuna catena vengono inseriti tutti i dati
tra di loro sinonimi, quindi quelli per i quali la funzione hash ha calcolato come indirizzo la
posizione della tabella contenente il puntatore alla testa della catena.
L’inserimento di una nuova chiave k avviene calcolando h(k) e inserendo k nella catena indicata
dal puntatore che si trova nella posizione h(k) della tabella.
La ricerca avviene in modo simile, accedendo ad una catena tramite il valore della funzione
hash e, poi, scorrendola sequenzialmente.
Questo è l’unico caso di tabella hash in cui è possibile memorizzare un numero n di elementi
maggiore della lunghezza m della tabella.
Esempio:
h(k) = (k mod 11) 1 19 5 12 18 3 8 9 14 7 16 24 23 13 27 34 38
0 34
1 12 23
1 1 13
2 3 14
3
4 38
5 16 27
5
6 18 7
7 19 8
8
9 9
10
Catene Unite: ogni elemento della tabella è formato da due campi, uno contenente la chiave e
• l’altro un indice.
Ogni elemento viene inserito nella posizione che gli spetta secondo il valore della funzione hash
se essa risulta essere libera e viene posto l’indice a -1.
Se, invece, si dovesse verificare una collisione, la chiave k viene inserita nella prima posizione
(successiva alla posizione h(k)) della tabella e l’indice della h(k) assume il valore di questa
posizione, ossia indica la posizione di un sinonimo della chiave presente in h(k).
Ha il vincolo n ≤ m, dove n è il numero di chiavi ed m la dimensione della tabella.
Esempio:
h(k) = (k mod 11) 1 19 5 12 18 3 8 23 14 7 17
Chiave Indice
0 14 -1
1 1 2
2 12 4
3 3 0
4 23 -1
5 5 -1
6 17 -1
7 18 10
8 19 9
9 8 -1
10 7 -1
Indirizzamento Aperto (o Hash Lineare): simile al metodo delle catene unite, nell’Hash Lineare
• però vengono soppressi gli indici e viene scelto di effettuare la ricerca dei sinonimi di una chiave
k in modo sequenziale, partendo dalla posizione h(k).
Questo metodo aumenta il numero di confronti necessari per la ricerca, ma risparmia lo spazio
necessario alla memorizzazione degli indici.
La ricerca termina senza successo solo quando viene trovata una posizione vuota nella tabella.
Il costo della ricerca dipende dal rapporto n/m, detto fattore di caricamento della tabella.
Algoritmo di Inserimento L’inserimento di una chiave k nella tabella v[0, …,
x = h(k); m-1] viene realizzato attraverso un ciclo, in cui viene
finché v[x] != -1 supposto che gli elementi vuoti di v abbiamo valore
x = (x+1) % m; -1.
v[x] = k; La tabella viene considerata circolare.
Il valore della posizione in cui viene inserita la chiave k dipende dal valore calcolato dalla funzione
hash h (k), ma anche dal numero di passi che serve fare prima di inserire k nella tabella.
0
Viene indicata con h (k) la posizione esaminata al passo i-esimo, dove h (k) = (h (k) + i) mod m.
i i 0
Quando le collisioni vengono risolte con l’Hash Lineare, il numero di tentativi richiesti per ricercare
un elemento in un tabella hash di dimensione m che contiene n = αm chiavi è:
per ricerche con successo.
per ricerche senza successo.
Il valore viene detto fattore di caricamento della tabella, poiché indica il rapporto fra il
numero di posizioni occupate della tabella stessa e il numero di posizioni totali.
Tanto più è basso il fattore di caricamento della tabella, tanto migliori saranno le prestazioni del
metodo hash.
L’Hash Lineare presenta però due inconvenienti:
se per due chiavi distinte k e k si ha h (k ) = h (k ), allora anche h (k ) = h (k ) per ogni
1. 1 2 0 1 0 2 i 1 i 2
valore di i, ovvero la ricerca di due sinonimi procede esaminando sempre le stesse
posizioni.
Questo fenomeno viene detto agglomerazione primaria.
se anche due chiavi non sono sinonimi, si può verificare che h (k ) = h (k ) per un certo i ≠ j.
2. i 1 j 2
Anche in questo caso, i passi successivi per la ricerca delle due chiavi coincidono, quindi
h (k ) = h (k ) per ogni valore di r > 0.
i+r 1 j+r 2
Questo fenomeno viene detto agglomerazione secondaria.
Questi due fenomeni di aggregazione significano che ci vogliono molti confronti per trovare sia k
1
che k .
2
Tanto più grande è un gruppo di chiavi, tanto maggiore è la possibilità che esso cresca
ulteriormente, provocando un deterioramento delle prestazioni della tabella per le operazioni di
inserimento e ricerca.
Per risolvere questi problemi sono state introdotte alcune tecniche, come:
Hash Casuale:
• h (k) = (h (k) + r ) mod m
i 0 i
Dove r sono numeri casuali dipendenti solo da i.
i
Risolve solo l’agglomerazione secondaria.
Hash Doppio:
• ’ ’’
h (k) = (h (k) + ih (k)) mod m
i ’ ’’
Risolve sia l’agglomerazione primaria che l’agglomerazione secondaria, purché h e h siano
scelte in modo opportuno.
Quando le collisioni sono risolte con l’hash doppio, il numero medio di tentativi per la ricerca di una
chiave in una tabella hash di dimensione m che contiene n = αm chiavi è:
per ricerche con successo.
per ricerche senza successo.
Il costo per inserire la prima chiave è pari al costo di una ricerca senza successo in una tabella con
n = 0 chiavi, dunque è pari ad 1.
Il costo per inserire la seconda chiave è pari al costo di una ricerca senza successo in una tabella
con n = 1 chiavi, dunque è pari a .
Il costo per inserire la terza chiave è pari al coso di una ricerca senza successo in una tabella con
n = 2 chiavi, dunque è pari a .
Continuando così, il costo medio di una ricerca con successo risulta essere appunto .
Esempio (con indirizzamento aperto):
1 19 5 20 18 3 8 9 14 7 24 43 39 13 16 12 62
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
19 1 20 3 39 5 24 7 8 9 43 62 12 13 14 16 18
Per quanto riguarda l’operazione di cancellazione all’interno delle Tabelle Hash, essa dipende dal
metodo usato per la risoluzione delle collisioni.
Per le tecniche che usano catene, la cancellazione avviene nel modo tipico delle catene.
Nelle altre situazioni si preferisce l’uso della cancellazione logica, per evitare eventuali
malfunzionamenti nelle operazioni di ricerca.
Confronto fra i vari metodi di ricerca
Spazio Ricerca Inserimento Cancellazione Ordinamento
Vettore n elementi O(log n) O(n) O(n) O(n)
2
Ordinato
Catena n elementi + n O(n) O(1) O(1) O(n)
Ordinata puntatori
n elementi + 2n
Alberi AVL O(log n) O(1) O(1) O(n)
2
puntatori
Tabelle Hash m > n elementi O(1) O(1) O(1) O(n log n)
2
Le Tabelle Hash sono da preferirsi agli Alberi perché sono più semplici e presentano tempi di
ricerca molto buoni.
Gli Alberi, però, presentano dei vantaggi rispetto alle Tabelle Hash: sono dinamici (non è
necessario conoscere a priori quante chiavi verranno inserite) e mantengono l’ordinamento delle
chiavi.
Selection Sort
Il metodo di ordinamento per selezione, noto come Selection Sort, è di tipo quadratico ed agisce
su un vettore di dati, lavorando sul posto.
Viene cercato inizialmente il più piccolo elemento del vettore stesso e viene scambiato con quello
che si trova nella prima posizione; viene cercato poi il secondo elemento più piccolo del vettore e
viene scambiato con quello che si trova nella seconda posizione e continua in questo modo finché
tutto il vettore non risulta essere ordinato.
Selection Sort Costo Algoritmo
per i = 0 a i = n-2
min = i;
per j = i+1 a n-1
se a[j] < a[min] 2
Sono richiesti circa n / 2 confronti e n - 1 scambi
min = j; per ordinare un vettore di n elementi.
temp = a[min];
a[min] = a[i];
a[i] = temp;
L’algoritmo di ordinamento per selezione non è stabile, quindi non conserva l’ordine relativo di
chiavi uguali.
Esempio (in rosso l’elemento più piccolo, in grigio la parte ordinata ad ogni giro):
503 87 512 61 908 170 897 275 653 426
503 87 512 61 908 170 897 275 653 426
61 87 512 503 908 170 897 275 653 426
61 87 512 503 908 170 897 275 653 426
61 87 170 503 908 512 897 275 653 426
61 87 170 275 908 512 897 503 653 426
61 87 170 275 426 512 897 503 653 908
61 87 170 275 426 503 897 512 653 908
61 87 170 275 426 503 512 897 653 908
61 87 170 275 426 503 512 653 897 908
61 87 170 275 426 503 512 653 897 908
61 87 170 275 426 503 512 653 897 908
Insertion Sort
Il metodo di ordinamento per inserzione, noto come Insertion Sort, è un metodo di ordinamento di
tipo quadratico.
Considerando un gruppo di dati contenuti in un vettore a, si considerano in successione gli
elementi e per ogni valore di un indice i, tra 1 e n-1, si inserisce l’elemento a[i] nella giusta
posizione tra gli elementi a[0, …, n-1].
L’inserimento avviene spostando gli elementi più grandi di una posizione a destra e poi inserendo
l’elemento nella posizione rimasta vuota.
Insertion Sort Costo Algoritmo
per i = 0 a i = n-1
v = a[i];
j = i; 2
L’algoritmo richiede circa n / 4 confronti ed
finché a[j-1] > v altrettanti spostamenti per ordinare un vettore di n
a[j] = a[j-1]; dati.
j = j-1;
a[j] = v;
L’algoritmo di ordinamento per inserzione è stabile.
Esempio (in verde l’elemento inserito, in rosso gli elementi spostati per l’inserimento, in grigio gli
elementi ancora non considerati):
20 35 18 8 14 41 3 39
20 35 18 8 14 41 3 39
20 35 18 8 14 41 3 39
18 20 35 8 14 41 3 39
8 18 20 35 14 41 3 39
8 14 18 20 35 41 3 39
8 14 18 20 35 41 3 39
3 8 14 18 20 35 41 39
3 8 14 18 20 35 39 41
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher sc1512 di informazioni apprese con la frequenza delle lezioni di Algoritmi e strutture dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Firenze - Unifi o del prof Verri Maurizio.
Acquista con carta o conto PayPal
Scarica il file tutte le volte che vuoi
Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato