Programmazione e Strutture Dati

INSERIMENTO

Inserimento di 15

Codice:

void insertBST(BST *t, Item it){

if (isEmptyBST(*t))

{ *t = malloc(sizeof(struct node));

(*t) -> value = it;

(*t) -> left = NULL;

(*t) -> right = NULL;

}

else if (cmpItem(it, getItem(*t)) < 0)

insertBST(&((*t) -> left), it);

else if (cmpItem(it, getItem(*t)) > 0)

insertBST(&((*t) -> right), it);

}

Su questa funzione va fatto un po' di ragionamento.

I due else if servono per scorrere tutto l’albero fino al punto in cui si deve inserire l’elemento, se è

minore della radice viene chiamata ricorsivamente la funzione sul sottoalbero sinistro, se è

maggiore sul destro, altrimenti significa che sono uguali e che quindi non bisogna aggiungerlo

perché già c’è. Se invece l’albero è vuoto significa che quello è il punto dove inserire l’elemento.

Bisogna capire innanzitutto perché si passa il puntatore all’albero. Se noi passassimo l’albero come

abbiamo sempre fatto non potremmo modificarlo.

ESEMPIO:

Nel momento in cui viene creata una variabile, il suo valore viene salvato in un indirizzo di

memoria e il compilatore associa quell’indirizzo di memoria alla variabile.

int i = 40;

Il compilatore sceglie un indirizzo di memoria, esempio $15 e ci scrive dentro 40.

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

40

Ora se viene invocata una funzione il numero 40 viene copiato in un altra locazione di memoria.

funzione(int a)

{ …

}

Ipotizziamo che venga copiato nella locazione $10.

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

40 40

Qualunque modifica del valore nella funzione rimane inalterato il valore della variabile nel main,

perché i numeri sono uguali ma salvati in due locazioni di memoria differenti.

Ora dichiariamo una variabile puntatore

Int *b = malloc(sizeof(int));

*b = 50;

In questo caso il valore della variabile non è più un intero, ma un indirizzo di memoria.

L’indirizzo di memoria viene scelto dal compilatore, noi vogliamo che questo spazio sia della

grandezza di un intero.

Il compilatore sceglie l’indirizzo $18.

ATTENZIONE! $18 è il valore della variabile b. La variabile b a sua volta è salvata in un altro

indirizzo di memoria, per esempio $17.

$17 = indirizzo in cui è salvato il valore della variabile b.

$18 = valore della variabile b.

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

40 40 $18 50

Ora cosa succede se io passo il puntatore alla funzione?

funzione(int *a)

{ …

}

Così come prima, il valore della variabile che passiamo viene copiato in un altra locazione.

Questa volta in $10 viene salvato il valore della variabile b.

Qual è il valore della variabile b? $18.

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

$18 40 $18 50

Se ora la funzione modifica il valore di *a, verrà modificato il contenuto di $18, cioè 50.

*a = 100;

Ora in $18 ci sarà scritto 100.

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

$18 40 $18 100

Se invece utilizziamo l’operatore & a cambiare sarà il valore della locazione $10.

&a = malloc(sizeof(int));

Viene scelto un altro indirizzo grande quanto un intero e assegnato a $10. Esempio $12

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

$12 40 $18 100

Ora modificando la variabile a della funzione con l’operatore * sarà cambiato il contenuto della

locazione di memoria $12.

Adesso cerchiamo di capire perché la funzione utilizza BST *t.

Il tipo BST è uno *void, quindi BST *t è di tipo **void.

Ripetiamo il procedimento.

BST t = newBst();

a t viene assegnato un indirizzo di memoria, per esempio $17. Il suo contenuto però è un indirizzo

di memoria, esempio $18. In $18 ci sono le informazioni dell’albero.

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

$18 albero

Se noi passassimo l’albero senza puntatore, il valore di $17 verrebbe copiato in un altra variabile

esempio $13.

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

$18 $18 albero

A questo punto, con questa riga

t = malloc(sizeof(struct node));

verrebbe reallocata la memoria per t, cioè per $13, ma la memoria a disposizione per l’albero che ci

interessa, cioè quello nel main rimarrebbe uguale. Ipotizziamo che la nuova locazione sia $15.

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

$15 $18 albero

Se invece passiamo il puntatore cosa succede:

BST *t = malloc(sizeof(struct node));

*t è un puntatore a puntatore, cioè il suo contenuto è un puntatore, e il contenuto del suo contenuto

è un puntatore.

$16 = indirizzo in cui è salvato il valore di *t

$17 = valore di $16, cioè indirizzo in cui è salvato l’indirizzo dell’albero

$18 = informazioni albero

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

$17 $18 albero

Durante la chiamata della funzione verrà copiato il valore di $16, quindi verrà passata una copia

dell’indirizzo $17.

Adesso con la chiamata

(*t) = malloc(sizeof(struct node)); $15 = copia della variabile

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

$17 $17 $18 albero

Ad essere reallocata è l’indirizzo $18, cioè quello dell’albero che abbiamo nel main. Questo perché

*t preleva il valore di $15, cioè prende l’indirizzo $17 e gli assegna un nuovo indirizzo.

Ipotizzando che il nuovo indirizzo sia $19, il risultato sarà questo.

$10 $11 $12 $13 $14 $15 $16 $17 $18 $19

$17 $17 $19 albero

Il nostro intento era quello di assegnare un nuovo indirizzo di memoria all’albero e ci siamo riusciti.

Funzione delete

Item delete(BST *t, Item it){

if (isEmptyBST(*t))

return NULL;

if (cmpItem(it, getTreeRoot(*t)) > 0)

return delete(&(*t) -> right, it);

if (cmpItem(it, getTreeRoot(*t)) < 0)

return delete(&(*t) -> left, it);

else

{ if (!getRight(*t))

{ Item returned = getTreeRoot(*t);

*t = getLeft(*t);

return returned;

}

else if (!getLeft(*t))

{ Item returned = getTreeRoot(*t);

*t = getRight(*t);

return returned;

}

else

{ Item massimo = max(getLeft(*t));

Item returned = getTreeRoot(*t);

(*t) -> value = massimo;

delete(&(*t) -> left, massimo);

return returned;

}

}

}

Per lo stesso motivo di prima dobbiamo passare un puntatore all’albero anche per questa funzione.

Per l’eliminazione ci sono quattro casi:

L’albero è vuoto

• L’elemento è maggiore dell’etichetta dell’albero

• L’elemento è minore dell’etichetta dell’albero

• L’elemento è uguale all’etichetta

•

Se l’albero è vuoto viene restituito molto semplicemente NULL.

Se l’elemento è maggiore della radice viene chiamata ricorsivamente la funzione sul sottoalbero

destro.

Se l’elemento è minore viene chiamata ricorsivamente la funzione sul sottoalbero sinistro.

Se invece gli elementi sono uguali significa che l’elemento è presente nell’albero e deve essere

cancellato.

Se è presente ci sono altre tre condizioni:

Non c’è il sottoalbero destro

• Non c’è il sottoalbero sinistro

• Ci sono tutti e due i sottoalberi

•

Non c’è bisogno di distinguere il caso in cui sia una foglia, vediamo perché.

Nel caso in cui non ci sia il sottoalbero destro, ci salviamo il valore dell’etichetta dell’albero, e

cambiamo l’indirizzo dell’albero con quello del suo sottoalbero sinistro. Se neanche il sottoalbero

sinistro c’è, allora significa che è una foglia è che deve essere eliminata, gli verrà quindi assegnato

comunque il valore del suo sottoalbero sinistro, cioè NULL. Restituiamo l’elemento eliminato.

Se invece c’è il sottoalbero destro ma non il sinistro, ci salviamo il valore dell’etichetta in una

variabile, cambiamo l’indirizzo dell’albero con quello del suo sottoalbero destro e restituiamo il

valore eliminato. Anche in questo caso se è una foglia gli verrà assegnato NULL perché tutti e due i

sottoalberi di una foglia sono NULL, cioè alberi vuoti.

Se invece ci sono tutti e due i sottoalberi, possiamo decidere o di prendere l’elemento massimo dal

sottoalbero sinistro, o l’elemento minimo dal sottoalbero destro. Nel codice viene preso il massimo

dal sottoalbero sinistro, viene salvato il valore dell’etichetta dell’attuale albero in una variabile,

viene cambiato il valore dell’attuale etichetta con il massimo, e viene chiamata ricorsivamente

delete() sul massimo, in modo tale da rimuoverlo da dov’era prima.

ALTRI ALGORITMI DI ORDINAMENTO (QUICKSORT E MERGE SORT)

I seguenti ordinamenti ordinano per confronti

selection sort

• insert sort

• bubble sort

•

E sono algoritmi di ordinamento semplici con un numero di operazioni quadratico rispetto all’input

2

(n ).

Il quicksort e il merge sort sono algoritmi di ordinamento più efficienti.

Merge sort (Von Neumann, 1945) ha un numero di operazioni rispetto alla taglia in input di

O(n log n).

Quicksort invece (Hoare, 1961)

O (n log n) nel caso medio

• quadratico nel caso peggiore

• Nome Migliore Medio Peggiore Memoria Stabile In loco

2 2 2

Selection sort O(n ) O(n ) O(n ) O(1) No Si

2 2

Insertion sort O(n) O(n ) O(n ) O(1) Si Si

2 2

Quicksort O(n) O(n ) O(n ) O(1) Si Si

2

Bubble sort O(n log n) O(n log n) O(n ) O(n)* No Si

Merge sort O(n log n) O(n log n) O(n log n) O(n) Si No

*Spazio aggiuntivo dovuto alla gestione della ricorsione.

Sia il quicksort che il merge sort sono due algoritmi di ordinamento del tipo divide et impera.

Divide: si procede alla suddivisione dei problemi in sottoproblemi minori;

Impera: I problemi vengono risolti in modo ricorsivo. Quando arrivano ad una dimensione

sufficientemente piccola, vengono risolti con il caso base.

Combina: si combina il risultato ottenuto dalle altre chiamate ricorsive per avere il risultato finale.

Vediamo come funziona il quicksort.

Scegliamo un elemento dal quale partire, il cosiddetto pivot, dopodichè facciamo in modo che tutti

gli elementi ≤ stiano alla sua sinistra e tutti quelli > alla sua destra.

11 15 34 21 38 17 10 22

Possiamo scegliere come pivot, un numero qualsiasi, in questo caso scegliamo il primo.

↓ Pivot

11 15 34 21 38 17 10 22

↑ ↑

i j

Abbiamo due indici, i che punta al primo elemento e j che punta all’ultimo. Appena inizia il

processo, i avrà come valore -1 e j avrà come valore la lunghezza dell’array.

Nell’esempio l’array ha lunghezza 8, cioè da 0 a 7. La variab