Lezione 10 Ordinamento ottimo Ricerca. Sommario Ordinamento Ottimo O(n lg n) Ordinamento O(n) Alberi...

Lezione 10

Ordinamento ottimo

Ricerca

Sommario

• Ordinamento Ottimo O(n lg n)• Ordinamento O(n)• Alberi e Grafi• Alberi Binari di Ricerca

Ordinamento Ottimo

• In un ordinamento per confronto si usa il confronto tra elementi per ottenere informazioni sull’ordine della sequenza degli elementi

• dati a e b per determinare l’ordine relativo fra questi si deve eseguire uno dei seguenti confronti: – a > b– a < b– a b– a b

• I confronti sono tutti equivalenti, nel senso che forniscono tutti la stessa informazione sull’ordinamento relativo tra a e b

• consideriamo pertanto solo a b

Albero di decisione

• Un algoritmo di ordinamento per confronto può essere rappresentato a livello astratto come un albero di decisione

• un albero di decisione rappresenta i confronti eseguiti da un algoritmo su di una sequenza di ingresso di data dimensione e indica sulle foglie la permutazione dell’ingresso che corrisponde alla sequenza ordinata dei dati in ingresso

Albero di decisione

• In un albero di decisione non si rappresenta niente altro che i confronti (niente istruzioni per il controllo, copia dati, etc)

• ogni nodo interno ha etichetta ai:aj con i,j nell’intervallo dei dati in ingresso

• ogni foglia ha una etichetta del tipo [3,5,1,...] con la quale indichiamo una permutazione degli elementi in ingresso (cioè in questo caso consideriamo come risultato prima il terzo elemento, poi il quinto, poi il primo, etc)

Albero di decisione

• Ad ogni nodo interno si compie un confronto: – se ai aj allora si va nel nodo sinistro, altrimenti destro

• L’esecuzione di un algoritmo consiste nel compiere un cammino nell’albero di decisione a partire dalla radice fino ad una foglia

• perché si abbia sempre una soluzione si deve garantire che ognuna delle n! permutazioni dell’ingresso sia rappresentato come una foglia dell’albero di decisione

Albero di decisione per Ordinamento

a1:a2

a2:a3 a1:a3

[1,2,3]a1:a3

[1,3,2][3,1,2]

[2,1,3] a2:a3

[2,3,1] [3,2,1]

Nota: 3 elementi, 3! combinazioni, 6 foglie

Limite inferiore

• Il cammino più lungo in un albero di decisione dalla radice ad una qualunque foglia rappresenta il numero di confronti che l’algoritmo deve eseguire nel caso peggiore

• questo è pari all’altezza dell’albero• un limite inferiore sull’altezza dell’albero di decisione

di un algoritmo è dunque un limite inferiore sul tempo di esecuzione di un algoritmo di ordinamento per confronti

Teorema sull’ordinamento ottimo

• Teorema:– qualunque albero di decisione che ordina n elementi ha

altezza (n ln n)

• Dimostrazione:– Dato che vi sono n! permutazioni di n dati ed ogni

permutazione rappresenta un possibile ordinamento allora l’albero binario di decisione deve avere n! foglie

– un albero binario di altezza h ha al più 2h foglie– pertanto: 2h n! (approssimazione di Stirling) nn – passando ai logaritmi: ln 2h ln nn – ovvero: h n ln n = (n ln n)

Conseguenze

• Un qualunque algoritmo di ordinamento per confronto non può fare asintoticamente meglio di n ln n

• Ne consegue che il merge sort e lo heap sort sono algoritmi ottimi in quanto limitati superiormente come O(n ln n)

Ordinamento O(n)

• E’ tuttavia possibile scrivere algoritmi di ordinamento che operano in tempo O(n)!!

• Per farlo si deve abbandonare il metodo di ordinamento per confronto

• Se le chiavi da ordinare sono interi in un intervallo prefissato allora si può utilizzare direttamente il valore della chiave per posizionare l’elemento nella giusta posizione nel vettore ordinato finale

Counting Sort

• Il Counting Sort si basa sull’ipotesi che ognuno degli n elementi in ingresso sia un intero nell’intervallo da 1 a k.

• Se k=O(n) allora il tempo di esecuzione del CountingSort è O(n).

• L’algoritmo prende in ingresso un vettore, restituisce un secondo vettore ordinato ed utilizza un vettore di appoggio per l’elaborazione

Spiegazione Intuitiva di Counting Sort

• Per ogni elemento x si determinano quanti elementi minori di x vi siano

• si usa questa informazione per assegnare ad x la sua posizione finale nel vettore ordinato

• se ad esempio vi sono 8 elementi minori di x allora x andrà messo nella posizione 9

• bisogna fare attenzione al caso in cui vi siano elementi coincidenti. In questo caso infatti non vogliamo assegnare a tutti la stessa posizione.

Counting Sort

CountingSort(A,B,k)

1 for i 1 to k

2 do C[i] 0

3 for j 1 to length[A]

4 do C[A[j]] C[A[j]]+1

5 for i 2 to k

6 do C[i] C[i]+C[i-1]

7 for j length[A] downto 1

8 do B[C[A[j]]] A[j]

9 C[A[j]] C[A[j]]-1

Visualizzazione

3 6 4 1 3 4 1 4

1 2 3 4 5 6 7 8

A 2 0 2 3 0 1

1 2 3 4 5 6

C 2 2 4 7 7 8

1 2 3 4 5 6

C

4

1 2 3 4 5 6 7 8B

2 2 4 6 7 8

1 2 3 4 5 6

C

1 4

1 2 3 4 5 6 7 8B

1 2 4 6 7 8

1 2 3 4 5 6

C

1 4 4

1 2 3 4 5 6 7 8B

1 2 4 5 7 8

1 2 3 4 5 6

C

1 1 3 3 4 4 4 6

1 2 3 4 5 6 7 8

B

Tempo di calcolo del Counting Sort

• Esaminando l’algoritmo si osserva che vi sono due cicli di lunghezza k e due di lunghezza n

• Si può far vedere che la complessità è (k+n)• se k= (n) allora la complessità del Counting Sort è

complessivamente (n)

Stabilità del Counting Sort

• L’algoritmo Counting Sort è un metodo di ordinamento stabile

• infatti elementi con lo stesso valore compaiono nel vettore risultato B nello stesso ordine che avevano nel vettore di ingresso A

Radix Sort

• Il Radix Sort è un algoritmo di ordinamento usato per ordinare record con chiavi multiple

• Un esempio di record con chiavi multiple è dato dalla data gg/mm/aaaa. Per ordinare per data si deve ordinare l’anno e a parità di anno si deve ordinare per mese e a parità di mese per giorno

• Un altro esempio di record a chiave multipla è dato dal considerare le cifre di un intero come chiavi separate. Per ordinare interi si ordina per la cifra di posizione maggiore e in caso di parità per quelle di ordine via via minore

Spiegazione intuitiva

• Il Radix Sort opera in modo contro intuitivo ordinando prima sulle cifre meno significative e poi su quelle via via più significative

• Supponiamo di dover ordinare una sequenza di numeri a 3 cifre

• Utilizzando un ordinamento di tipo stabile possiamo procedere ordinando prima per le unità, poi le decine e in ultimo le centinaia

• ad ogni passo la stabilità ci garantisce che le cifre precedenti sono già ordinate

Esempio

329

457

657

839

436

720

355

720

355

436

457

657

329

839

720

329

436

839

355

457

657

329

355

436

457

657

720

839

Sequenza in ingresso

PseudoCodice

Radix-Sort(A,d)

1 for i 1 to d

2 do metodo di ordinamento stabile su cifra i

Tempo computazionale

• Il tempo di esecuzione dipende dall’algoritmo di ordinamento stabile scelto per ordinare le singole cifre

• se si usa il Counting Sort si ha che per ognuna delle d cifre si impiega un tempo (k+n) pertanto si ha

(dk+dn)• se d è una costante rispetto a n• se k=(n)• allora per il radix sort si ha (n)

Nota sulle prestazioni

• Se vogliamo ordinare 10^6 numeri a 3 cifre – con il radix sort si effettua per ogni dato 3 chiamate al

counting sort– con algoritmi O(n lg n) per ogni dato si effettuano lg n=20

operazioni

• Andando a estrarre le costanti numeriche nascoste nella notazione asintotica si vede che il radix sort può essere conveniente

• Lo svantaggio sta nel fatto che il metodo non è un ordinamento in loco e ha bisogno di più del doppio della memoria dei metodi in loco

Definizioni per Grafi e Alberi

• Di seguito vengono date delle definizioni su grafi ed alberi che saranno utili per comprendere le strutture dati presentate successivamente

Grafi

• Un grafo orientato (o diretto) G è una coppia (V,E) dove V è un insieme finito detto dei vertici e E è una relazione binaria su V che forma l’insieme degli archi. Gli archi sono delle coppie ordinate di vertici.

1 2

4 5 6

3V={1,2,3,4,5,6}

E={(1,2),(2,2),(2,4),(2,5),(4,1),(4,5),(5,4),(6,3)}

Grafi

• Un grafo non orientato è un grafo in cui gli archi sono coppie non ordinate di vertici, cioè un arco fra i vertici u,v è un insieme di due elementi {u,v} piuttosto che una coppia (u,v)

• tuttavia si indica l’arco sempre con notazione (u,v)

1 2

4 5 6

3

Grafi

• Sia (u,v) è un arco di un grafo orientato, si dice che: – l’arco esce dal vertice u– l’arco entra nel vertice v

• un arco (u,v) di un un grafo non orientato si dice che è incidente sui vertici v e u

• si dice che v è adiacente a u– in un grafo non orientato la relazione di adiacenza è

simmetrica– in un grafo orientato v è adiacente a u, ma non è vero il

viceversa, e si indica con la notazione uv

Grafi

• Il grado di un vertice in un grafo non orientato è il numero di archi incidenti sul vertice

• in un grafo orientato il grado uscente (entrante) di un vertice è il numero di archi uscenti (entranti) dal vertice

Grafi

• Un cammino di lunghezza k da un vertice a ad un vertice b in un grafo G=(V,E) è una sequenza di vertici < v0, v1,…,vk> tali che – a= v0

– b= vk

– (vi-1 ,vi) E per i=1,…,k

• La lunghezza di un cammino è il suo numero di archi

• un cammino < v0, v1,…,vk> è un ciclo se v0= vk

• un grafo senza cicli si dice aciclico• un grafo non orientato è connesso se ogni coppia di vertici

è collegata con un cammino

Alberi

• Un albero è un grafo non orientato, connesso e aciclico.

• Un albero radicato è un albero in cui si distingue un vertice (chiamato radice) dagli altri vertici

• i vertici in un albero sono chiamati nodi• sia x un nodo di un albero con radice r: qualunque

nodo y sull’unico cammino da r a x è chiamato antenato di x e x si dice discendente di y

• il sottoalbero radicato in x è l’albero indotto dai discendenti di x, radicato in x

Alberi

• Se l’ultimo arco di un cammino dalla radice r ad un nodo x è l’arco (y,x) allora y è il padre di x e x è il figlio di y

• la radice è l’unico nodo che non ha padre• due nodi con lo stesso padre si dicono fratelli• un nodo senza figli si dice nodo esterno o foglia• un nodo non foglia è un nodo interno• il numero di figli di un nodo x è il grado di x

Alberi

• la lunghezza di un cammino da r a x è la profondità di x• la profondità massima di un qualunque nodo di un

albero è l’altezza dell’albero• un albero ordinato è un albero radicato in cui i figli di

ciascun nodo sono ordinati (cioè si distingue il primo figlio, il secondo, etc)

Alberi binari

• Un albero binario è una struttura definita su un insieme finito di nodi che:– non contiene nessun nodo, oppure– è composto da tre insiemi disgiunti di nodi: un nodo radice, un

albero binario chiamato sottoalbero sinistro e un albero binario chiamato sottoalbero destro

• un albero binario che non contiene nessun nodo è detto albero vuoto o albero nullo (denotato con NIL)

• se il sottoalbero sinistro (destro) non è vuoto allora la sua radice è detta figlio sinistro (destro)

• se un sottoalbero è l’albero nullo si dice che il figlio è assente o mancante

Alberi binari

• Un albero binario non è un albero ordinato con nodi con grado al più due: in un albero ordinato non si distingue fra figlio destro o sinistro (ma si considera solo il numero di figli)

Alberi

• in generale si parla di alberi posizionali per quegli alberi in cui i figli dei nodi sono etichettati con interi positivi distinti

• l’i-esimo figlio di un nodo è assente se nessun figlio è etichettato con l’intero i

• Un albero k-ario è un albero posizionale in cui per ogni nodo tutti i figli con etichetta più grande di k sono assenti

Alberi

• Un albero k-ario completo è un albero k-ario in cui tutte le foglie hanno la stessa profondità e tutti i nodi interni hanno grado k

• Il numero di foglie di un albero k-ario è:– la radice ha k figli a profondità 1– ognuno dei figli ha k figli a profondità 2 per un totale di k.k foglie– a profondità h si hanno kh foglie

• il numero di nodi interni di un albero k-ario completo di altezza h è:

1+k+ k2 + … +kh-1 = i=0..h-1 ki = (kh -1)/(k-1)

• quindi un albero binario ha 2h -1 nodi interni

Implementazione alberi binari

• Gli alberi si rappresentano ricorrendo agli stessi metodi usati per rappresentare le liste

• In genere si usano strutture dati con puntatori

• Per gli alberi binari si usano strutture dati per rappresentare i nodi che hanno un campo key e 2 o 3 puntatori ad altri nodi (si può non utilizzare il puntatore a padre)

struct Node{

int key;

Node* p;

Node * left, * right;

};

Implementazione alberi binari

• Se x è un nodo allora– se p[x]=NIL il nodo è la radice dell’albero– se left[x]=NIL (right[x]=NIL) allora il nodo non ha figlio

sinistro (destro)

• Si mantiene il puntatore alla radice dell’albero T memorizzandola nell’attributo root[T]– se root[T]=NIL l’albero è vuoto

Visualizzazione alberi binari

key p left right

Ø

ØØ

Ø Ø Ø Ø

2

25

4 3

2

5

4 3

2

Implementazione alberi • Se vogliamo rappresentare alberi con un numero illimitato di figli

potremmo pensare di riservare un numero max di link ai figli come:

• ma in questo modo dobbiamo porre un limite sul massimo grado di un nodo

• inoltre viene sprecato molta memoria per rappresentare i puntatori NIL

key p 1st 2nd 3rd 4th...

Ø2

Implementazione alberi

• Per rappresentare alberi con un numero illimitato di figli conviene usare la rappresentazione figlio-sinistro fratello-destro

• Ogni nodo conserva il campo key e puntatore a padre

• invece di avere un puntatore per ogni figlio i nodi hanno solo due puntatori: – puntatore al figlio più a sinistra– puntatore al fratello immediatamente a destra

Visualizzazione

2

35

4 3 4 6 9 8

4 3

2

35

4 3 4 6 9 8

4 3

Visualizzazione

2

35

4 3 4 6 9 8

4 3

2

35

4

3

4

6

9

8

4 3

Algoritmi su gli alberi binari: visite

• Dato un puntatore alla radice di un albero vogliamo scandire in modo sistematico tutti i nodi di tale albero

• In una lista abbiamo una unica possibilità: quella di seguire il link al nodo successivo

• Con un albero binario sono possibili 3 strategie:– preordine o ordine anticipato: si visita prima il nodo e poi i

sottoalberi sinistro e destro– inordine o ordine simmetrico: si visita prima il sottoalbero

sinistro e poi il nodo e poi il sottoalbero destro– postordine o ordine posticipato: si visita prima il sottoalbero

sinistro, poi quello destro e poi il nodo

Visita in ordine simmetrico

Inorder-Tree-Walk(x)

1 if x NIL2 then Inorder-Tree-Walk(left[x])

3 stampa(key[x])

4 Inorder-Tree-Walk(right[x])

Visualizzazione

2

81

4 9

•si parte in 2•viene chiamata la funzione sul figlio sinistro•siamo in 1•viene chiamata la funzione sul figlio sinistro•non esiste figlio sinistro e la ricorsione termina•torniamo in 1•stampiamo 1•viene chiamata la funzione sul figlio destro•non esiste figlio destro e la ricorsione termina•torniamo in 1•la funzione termina•torniamo in 2•stampiamo 2•….

Visualizzazione

2

81

4 9

•viene chiamata la funzione sul figlio destro•siamo in 8•viene chiamata la funzione sul figlio sinistro•siamo in 4•viene chiamata la funzione sul figlio sinistro•non esiste figlio sinistro e la ricorsione termina•torniamo in 4•stampiamo 4•viene chiamata la funzione sul figlio destro•non esiste figlio destro e la ricorsione termina•la funzione termina•torniamo in 8•stampiamo 8•viene chiamata la funzione sul figlio destro•siamo in 9

Visualizzazione

2

81

4 9

•viene chiamata la funzione sul figlio sinistro•non esiste figlio sinistro e la ricorsione termina•torniamo in 9•stampiamo 9•viene chiamata la funzione sul figlio destro•non esiste figlio destro e la ricorsione termina•torniamo in 9•la funzione termina•torniamo in 8•la funzione termina•torniamo in 2•la funzione termina

Visita in ordine anticipato


1 if x NIL2 then stampa(key[x])

3 Inorder-Tree-Walk(left[x])


Visualizzazione

2

81

4 9

•si parte in 2•stampiamo 2•viene chiamata la funzione sul figlio sinistro•siamo in 1•stampiamo 1•viene chiamata la funzione sul figlio sinistro•non esiste figlio sinistro e la ricorsione termina•torniamo in 1•viene chiamata la funzione sul figlio destro•non esiste figlio destro e la ricorsione termina•torniamo in 1•la funzione termina•torniamo in 2

Visualizzazione

2

81

4 9

•viene chiamata la funzione sul figlio destro•siamo in 8•stampiamo 8•viene chiamata la funzione sul figlio sinistro•siamo in 4•stampiamo 4•viene chiamata la funzione sul figlio sinistro•non esiste figlio sinistro e la ricorsione termina•torniamo in 4•viene chiamata la funzione sul figlio destro•non esiste figlio destro e la ricorsione termina•la funzione termina•torniamo in 8•viene chiamata la funzione sul figlio destro•siamo in 9

Visualizzazione

2

81

4 9

•viene chiamata la funzione sul figlio sinistro•non esiste figlio sinistro e la ricorsione termina•torniamo in 9•viene chiamata la funzione sul figlio destro•non esiste figlio destro e la ricorsione termina•torniamo in 9•la funzione termina•torniamo in 8•la funzione termina•torniamo in 2•la funzione termina

Visita in ordine posticipato


1 if x NIL2 then Inorder-Tree-Walk(left[x])


4 stampa(key[x])

Algoritmi ricorsivi su alberi binari

• Capita di dover determinare dei parametri strutturali di un albero avendo in ingresso solo il link alla radice

• Si può sfruttare la struttura ricorsiva degli alberi ed realizzare versioni ricorsive delle funzioni di interesse

• Consideriamo una funzione per determinare il numero di nodi ed una per determinare l’altezza dell’albero

Funzioni ricorsive

int count(link h)

{

if (h == NULL) return 0;

return count(h->l) + count(h->r) + 1;

}

int height(link h)

{ int u, v;

if (h == NULL) return -1;

u = height(h->l); v = height(h->r);

if (u > v) return u+1; else return v+1;

}

Ricerca

• Molte applicazioni richiedono un insieme dinamico che fornisca solo operazioni di inserimento/cancellazione e ricerca o al più la ricerca di elementi particolari della collezione come il massimo/minimo o il predecessore/successore

Alberi Binari di ricerca

• Gli alberi binari di ricerca sono strutture dati dinamiche che forniscono le operazioni richieste (insert, delete, search, maximum, predecessor, etc) in tempo limitato asintoticamente dall’altezza dell’albero, cioè per le varie operazioni si ha T(n)=O(h)

• Quando gli alberi sono bilanciati questo comporta avere tempi di calcolo asintotici O(ln n)

• Tuttavia si possono avere alberi sbilanciati. Un albero può degenerare in un lista lineare. In questo caso si hanno tempi O(n)

Alberi Binari di Ricerca

• Un albero binario di ricerca è un albero binario in cui le chiavi soddisfano la proprietà dell’albero binario di ricerca:– sia x un nodo– key di left[x] key di x– key di right[x] key di x

2

81

4 9

Ordinamento delle chiavi

• In un albero binario di ricerca l’operazione di ordinamento viene eseguita semplicemente attraversando i nodi dell’albero in modo ricorsivo

• la visita deve essere una visita in ordine simmetrico

Visualizzazione

2

81

4 9

Root[t]

2

81

4 9

2

81

4 9

2

81

4 9

2

81

4 9

Sequenza stampata: 1 2 4 8 9

La ricerca

• L’idea è di confrontare la chiave di un nodo x con la chiave cercata

• nel caso che non coincidano si cerca solo nel sottoalbero in cui potrà trovarsi

• è possibile sapere quale sia il sottoalbero perché tutti i nodi del sottoalbero destro contengono chiavi maggiori della chiave di x (e nel sottoalbero sinistro chiavi minori)

PseudoCodice per la Ricerca (versione ricorsiva)

Tree-Search(x,k)

1 if x = NIL o k=key[x]

2 then return x

3 if k < key[x]

4 then return Tree-Search(left[x],key)

5 else return Tree-Search(right[x],key)

Tempo di calcolo

• La procedura discende a partire dalla radice l’albero e restituisce un puntatore al nodo la cui chiave coincide con la chiave cercata

• nel caso in cui essa non esista la procedura discende comunque fino ad una foglia e restituisce un puntatore nullo

• Il tempo impiegato è proporzionale alla lunghezza del cammino percorso, ovvero limitato dalla altezza dell’albero

• pertanto T(n)=O(h)

Nota

• E’ possibile scrivere qualsiasi procedura ricorsiva in forma non ricorsiva (e viceversa)

• La forma ricorsiva è spesso più elegante e compatta ma non la più efficiente

• Di seguito si da una procedura non ricorsiva per la ricerca in un albero binario

PseudoCodice per la Ricerca (versione iterativa)

Iterative-Tree-Search(x,k)

1 while x NIL e k key[x]2 do if k < key[x]

4 then x left[x]5 else x right[x]6 return x

Determinazione della chiave massima e minima

• La chiave massima in un albero binario dovrà trovarsi nel sottoalbero destro della radice

• e nel sottoalbero destro del figlio destro della radice• e così via• Analogamente per la chiave minima che dovrà

essere nel sottoalbero sinistro• Pertanto per determinare l’elemento massimo è

sufficiente discendere tutti i nodi da figlio destro in figlio destro fino ad arrivare alla foglia (e analogamente con i figli sinistri per il minimo)

Minimo e massimo

Tree-Minimum(x)

1 while left[x] NIL2 do x left[x]3 return x

Tree-Maximum(x)

1 while right[x] NIL2 do x right[x]3 return x

Successore e predecessore

• Dato un nodo nell’albero di ricerca talvolta si richiede di determinare il suo successore (o predecessore) secondo l’ordinamento fornito dalle chiavi.

• Se tutte le chiavi sono distinte, il successore di un nodo x è il nodo con la più piccola chiave maggiore della chiave di x

• Con gli alberi binari di ricerca è possibile determinare il successore (predecessore) di un nodo senza dover confrontare le chiavi

Idea intuitiva

• Si considerano due casi:– il nodo x ha un figlio destro– il nodo x non ha un figlio destro

• Nel primo caso si considera il sottoalbero destro che contiene sicuramente nodi con chiavi maggiori della chiave di x

• in questo sottoalbero il nodo con la chiave più piccola è la foglia alla estrema sinistra, cioè il nodo restituito dalla procedura Tree-Minimum

Idea intuitiva

• Nel caso in cui x non ha un figlio destro allora il predecessore deve essere un antenato p di x

• per p, x deve essere un discendente appartenente ad un sottoalbero sinistro (così la chiave di p è maggiore della chiave di x)

• perché la chiave di p sia la più piccola possibile allora p deve essere l’antenato più prossimo – altrimenti se consideriamo il nonno di x, padre di p, è vero

che questo ha chiave > chiave[x] ma non è la minima, perché anche chiave[p]>chiave[x] ma chiave[p]<chiave[nonno]

Idea intuitiva

• Per determinare questo nodo antenato è sufficiente risalire gli antenati di x fino a quando non si trova un nodo che è un figlio sinistro di qualche altro nodo y. Il nodo y sarà il nodo cercato

• si mantengono pertanto i puntatori x e y ai nodi figlio e padre e si risale fino a quando x=left[y]

Visualizzazione

15

186

17 203 7

2 4 13

9

Successore di 13

PseudoCodice Successore

Tree-Successore(x)

1 if right[x] NIL2 then return Tree-Minimum(right[x])

3 y p[x]4 while y NIL e x = right[y]5 do x y6 y p[x]7 return y

Predecessore

• La procedura per la determinazione del predecessore è simmetrica a quella vista per il successore

• il predecessore si troverà nel sottoalbero sinistro (se questo esiste), e sarà l’elemento massimo di questo sottoalbero

• se non esiste sottoalbero sinistro il predecessore sarà l’antenato più prossimo che ha un figlio destro che è antenato del nodo in questione

PseudoCodice Predecessore

Tree-Predecessore(x)

1 if left[x] NIL2 then return Tree-Maximum(left[x])

3 y p[x]4 while y NIL e x = left[y]5 do x y6 y p[x]7 return y

Inserzione

• Per inserire un nuovo valore k in un albero binario di ricerca:– si passa alla procedura un nodo z tale che key[z]=k, e

left[z]=right[z]=p[k]=NIL– si modificano i campi del nuovo nodo per inserirlo

opportunamente all’interno dell’albero binario di ricerca

• l’idea è di muoversi all’interno dell’albero a partire dalla radice spostandosi sul sottoalbero destro o sinistro come appropriato (confrontando le chiavi)

• una volta arrivati ad una foglia si inserisce il nuovo nodo

Visualizzazione

15

186

17 203 7

2 4 13

914

Pseudocodice Inserzione

Tree-Insert(T,z)

1 y NIL2 x root[T]3 while x NIL 4 do y x5 if key[z]<key[x]

6 then x left[x]7 else x right[x]8 p[z] y9 if y=NIL

10 then root[T] z11 else if key[z] < key[y]

12 then left[y] z13 else right[y] z

Cancellazione

• La procedura di cancellazione è più laboriosa in quanto si deve tenere conto di tre casi possibili

• dato un nodo z i casi sono:– z non ha figli– z ha un unico figlio– z ha due figli

• Nel primo caso si elimina direttamente il nodo z

• il secondo caso è identico al caso di eliminazione di un nodo da una lista concatenata

• Nel terzo caso si determina il successore di z e lo si sostituisce a z

Visualizzazione caso 1

15

20

5

18 23

3 12

10 13

16

6

7

15

20

5

18 23

3 12

10

16

6

7


15

20

5

18 23

3 12

10 13

16

6

7

15

20

5

18 23

3 12

10

6

7


15

20

5

18 23

3 12

10 13

6

7

15

20

6

18 23

3 12

10

7

16

PseudoCodice Cancellazione

Tree-Delete(T,z)

1 if left[z]=NIL o right[z]=NIL //identifica il nodo da cancellare o sostituire

2 then y z3 else y Tree-Successor(z)4 if left[y] NIL 5 then x left[y]6 else x right[y]7 if x NIL //ripristina il padre (cancellazione implicita)8 then p[x] p[y]9 if p[y] = NIL //ripristina i figli corretti

10 then root[T] x11 else if y=left[p[y]]

12 then left[p[y]] x13 else right[p[y]] x14 if y z15 then key[z] key[y]17 return y //per eventuale deallocazione

Implementazione C++#include <iostream>

using namespace std;

template<class T, class LessClass >

class TreeClass{

private:

struct Node{Node *left, *right, * parent; T key;};

Node *root;

public:

TreeClass():root(0){}

void insert(T);

void print(){p_print(root); cout<<endl;}

bool search(T user_key){return p_search(root, user_key);}

T minimum();

T maximum();

private:

void p_print(Node *);

bool p_search(Node * x, T user_key);

};

Implementazione C++


void TreeClass<T, LessClass>::p_print(Node *x){

if(x!=0){

p_print(x->left);

cout<<x->key<<" ";

p_print(x->right);

}

}


bool TreeClass<T, LessClass>::p_search(Node * x, T usr_key){

LessClass less;

if(x==0) return false;

if(!less(x->key,usr_key) && !less(usr_key,x->key)) return true; //ugualianza

if(less(usr_key,x->key)) p_search(x->left, usr_key);

else p_search(x->right, usr_key);

}


void TreeClass<T,LessClass>::insert(T usr_key){

LessClass less;

//inizializzazione del nodo da aggingere

Node * z=new Node;

z->key=usr_key; z->left=0; z->right=0; z->parent=0;

//ricerca della giusta posizione di inserzione

Node * y=0;

Node * x=root;

while(x != 0){

y=x;

if(less(z->key, x->key)) x=x->left;

else x=x->right;

}

//settaggio dei puntatori

z->parent=y;

if(y==0) root=z;

else if(less(z->key, y->key)) y->left=z;

else y->right=z;

}


T TreeClass<T, LessClass>::minimum(){

Node * x=root;

while(x->left !=0) x=x->left;

return x->key;

}


T TreeClass<T, LessClass>::maximum(){

Node * x=root;

while(x->right !=0) x=x->right;

return x->key;

}

Implementazione C++

Implementazione C++template<class T> struct LessClass{

bool operator()(const T & a, const T & b)const{return a<b;}

};

int main(){

//integer example

int v[]={2,5,8,1,3,4,7,9,6,0};

TreeClass<int, LessClass<int> > T;

for(int i=0;i<10;i++)

T.insert(v[i]);

T.print();

cout<<"Seraching 5:"<<

(T.search(5)? "Found":"Not found")<<endl;

cout<<"Seraching 11:"<<

(T.search(11)? "Found":"Not found")<<endl;

cout<<"Searching maximum:"<<T.maximum()<<endl;

cout<<"Searching minimum:"<<T.minimum()<<endl;

Implementazione C++ //char example

char c[]="this_is_a.";

TreeClass<char, LessClass<char> > Tc;

for(int i=0;i<10;i++)

Tc.insert(c[i]);

Tc.print();

cout<<"Seraching s:"<<

(Tc.search('s')? "Found":"Not found")<<endl;

cout<<"Seraching v:"<<

(Tc.search('v')? "Found":"Not found")<<endl;

cout<<"Searching maximum:"<<Tc.maximum()<<endl;

cout<<"Searching minimum:"<<Tc.minimum()<<endl;

cout<<endl;

return 0;

}

Lezione 10 Ordinamento ottimo Ricerca. Sommario Ordinamento Ottimo O(n lg n) Ordinamento O(n) Alberi...

Documents

Transcript of Lezione 10 Ordinamento ottimo Ricerca. Sommario Ordinamento Ottimo O(n lg n) Ordinamento O(n) Alberi...