Terza parte degli appunti delle lezioni del corso di Programmazione I con laboratorio (A.A. 2011/12)

Parte 3

Problema della ricerca

● Input: una sequenza A (con n elementi) e un

valore x

● Output: True se x compare in A, False altrimenti ● oppure

● Output: la posizione (o una posizione) di x in A,

Ricerca lineare

● Se non si hanno informazioni sulla disposizione

degli elementi di A, l'unico modo di risolvere il problema è quello di scandire tutti gli elementi di A

● Ci si ferma

● quando si trova un elemento uguale a x (successo),

oppure

Ricerca lineare

def ricerca_lineare(A,x): n=len(A)

trovato=False i=0

while i<n and not trovato: if A[i]==x:

trovato=True else:

i=i+1

Analisi

● Terminazione e correttezza sono ovvie

● Il costo nel caso peggiore è di n confronti, che

si verifica quando

● x è all'ultimo posto di A ● x non è presente in A

● Possiamo quindi dire che il costo complessivo è

Ricerca binaria

● Se A è ordinata (ad esempio in senso crescente)

si può usare un metodo più veloce

● L'idea è di confrontare l'elemento centrale di A

con x

parte sinistra parte destra

● se è uguale a x, l'algoritmo termina con successo ● se è maggiore di x, la ricerca continua sulla parte

sinistra di A (gli elementi della parte destra sono sicuramente maggiori di x)

Ricerca binaria

def ricerca_binaria(A,x): n=len(A) s=0 d=n-1 trovato=False

while s<=d and not trovato: m=(s+d)/2

if A[m]==x:

trovato=True elif A[m]>x:

Esempio di esecuzione

● Partendo dall'input A=[1,3,4,5,8,11,15,20,37] e

x=4

● All'inizio s=0 e d=n-1=9

● Alla prima iterazione m=4 e A[m]=8, quindi

d=m-1=3

● Alla seconda iterazione m=1 e A[m]=3, quindi

s=m+1=2

● Alla terza iterazione m=2 e A[m]=2, quindi

Analisi

● Terminazione e correttezza dipendono dal fatto

che ad ogni passo il numero di elementi in

considerazione (pari d-s+1) dimezza: prima o poi ne rimarranno uno o due e poi all'iterazione nessuno

● Il costo dipende dal numero di passaggi con cui

dimezzando n si arriva a 1

● Questo è pari a log

Ordinamento

● Problema molto importante: data una sequenza

A di numeri (o dati ordinabili), disporre gli

elementi in senso crescente (o decrescente)

● Si dice ordinamento “sul posto” perché si

modifica l'ordine della sequenza di partenza, senza crearne una nuova

● E' utile in tante situazioni avere dati ordinati

secondo qualche criterio

Scambio

● Definiamo una funzione che data una sequenza

A e due indici i e j, scambia tra di loro gli elementi di posto i e di posto j

● def scambia(A,i,j):

temp=A[i] A[i]=A[j] A[j]=temp

Bubble-sort

● L'idea del Bubble-sort è quella di controllare le

coppie di elementi consecutivi A[i] e A[i+1]

● se A[i]>A[i+1], sono fuori posto e allora si

scambiano tra di loro

● L'intera scansione di A non è sufficiente ad

ordinare A

● Ma è in grado di portare l'elemento maggiore di

Esempio di passaggio

● Partendo da A=[4,5,2,1,8,11,7,9], i passaggi

successivi sono ● [4,5,2,1,8,11,7,9] ● [4,5,2,1,8,11,7,9] scambia 5 e 2 ● [4,2,5,1,8,11,7,9] scambia 5 e 1 ● [4,2,1,5,8,11,7,9] ● [4,2,1,5,8,11,7,9] ● [4,2,1,5,8,11,7,9] scambia 11 e 7

Bubble-sort

● Eseguendo una seconda scansione si hanno i

seguenti passaggi ● [4,2,1,5,8,7,9,11] scambia 4 e 2 ● [2,4,1,5,8,7,9,11] scambia 4 e 1 ● [2,1,4,5,8,7,9,11] ● [2,1,4,5,8,7,9,11] ● [2,1,4,5,8,7,9,11] scambia 8 e 7 ● [2,1,4,5,7,8,9,11] ● [2,1,4,5,7,8,9,11]

Bubble-sort

● Infine con una terza scansione la sequenza viene

ordinata

● Infatti al primo passaggio si scambia 2 e 1, e ogni altro

controllo non cambierà più l'ordine

● Ad ogni scansione un elemento va al posto giusto:

● La prima scansione mette l'elemento più grande

all'ultimo posto

● La seconda scansione mette il secondo elemento più

grande al penultimo posto

Bubble-sort

def bubble_sort(A): n=len(A) for r in range(1,n): for i in range(0,n-r): if A[i]>A[i+1]: scambia(A,i,i+1)

● Il ciclo interno su i può essere ad ogni

passaggio sempre più corto: i controlli saltati sarebbero inutili

Miglioramento

● In molte situazioni sono sufficienti un numero

minori di scansioni

● Quando in una scansione non è svolto alcuno

scambio, ogni altra scansione sarà inutile e il ciclo può terminare

● A tal scopo si può cambiare il ciclo for su r con

Versione migliorata

def bubble_sort(A): n=len(A)

r=0

scambiato=True

while r<n-1 and scambiato: scambiato=False for i in range(0,n-r-1): if A[i]>A[i+1]: scambia(A,i,i+1) scambiato=True r=r+1

Calcolo del costo

● numero di confronti

(n-1)+(n-2)+(n-3)+...+1=O(n2₎

● numero di scambi nel caso peggiore

Perché O(n

2

)

● Una dimostrazione informale del perché

1+2+3+...+n fa è la seguente

● Sia n=12, scriviamo i numeri da 1 a 12 così

1 2 3 4 5 6 12 11 10 9 8 7

● La somma di ogni colonna è 13, le colonne

sono 6, quindi la somma totale è 6x13=78

● In generale, per n pari, le colonne sono n/2 e

ognuno ha somma n+1

● Anche per n dispari la formula vale

n n1

Selection-sort

● Idea

● il più piccolo elemento di A deve stare al primo

posto

● il secondo elemento più piccolo deve stare al

secondo posto

● …

● l'elemento più grande deve stare all'ultimo posto

Selection-sort

def selection_sort(A): n=len(A) for i in range(0,n-1): imin=i for j in range(i+1,n): if A[j]<A[imin]: imin=j if i!=imin: scambia(A,i,imin)

Esempio di esecuzione

● Partendo da A=[6,5,8,11,2,4,9]

● Al primo passaggio scambia 6 con 2 ottenendo

[2,5,8,11,6,4,9]

● Al secondo passaggio scambia 5 con 4

ottenendo [2,4,8,11,5,4,9]

● Al terzo passaggio scambia 8 con 5 ottenendo

[2,4,5,11,6,8,9]

Costo

● numero di confronti

(n-1)+(n-2)+(n-3)+...+1=O(n2₎

● numero di scambi nel caso peggiore

n-1

Insertion-sort

● L'idea è di ordinare una sequenza usando la

stessa tecnica di un giocatore di carte (ad esempio di Ramino o Scala 40)

● Avendo già in mano

A♠ 3♣ 4♠ 7♥ 9♦

● se gli arriva un 5♦ lo inserisce tra il 4 e il 7

ottenendo

Insertion-sort

● Le carte scorrono facilmente ed è semplice

creare posto ad una nuova carta

● Per compiere l'operazione analoga su una

sequenza è necessario spostare ogni

elemento, a partire dalla posizione in cui si deve inserire l'elemento, di un posto verso destra

1 3 4 7 9

Insertion-sort

● Il modo con cui si può ordinare una sequenza è

il seguente:

● Si divide la sequenza in due parti:

● una parte a sinistra già ordinata (all'inizio solo il

primo elemento)

● una parte a destra non ordinata (all'inizio tutti gli

altri)

Insertion-sort

● L'inserimento avviene partendo dall'ultimo

elemento della parte già ordinata e copiando man mano tutti gli elementi sulla cella

successiva

● Quando si trova un elemento più piccolo

dell'elemento x da inserire il ciclo si ferma

● A questo punto x è memorizzato al posto

Inserimento

● Ad esempio per inserire x=8 nella parte già

ordinata [2,4,10,11,14,15] si parte da [2,4,10,11,14,15,8]

[2,4,10,11,14,15,15] [2,4,10,11,14,14,15] [2,4,10,11,11,14,15]

[2,4,10,10,11,14,15] il ciclo termina dato che 4<8, quindi scrive 8 al posto del primo 10

Insertion-sort

def insertion_sort(A): n=len(A) for j in range(1,n): temp=a[j] i=j-1

while i>=0 and a[i]>temp: a[i+1]=a[i]

i=i-1

a[i+1]=temp

sistemare a[j] nella parte a[0..j-1] già ordinata

Esempio di esecuzione

● Ad esempio partendo con A=[7,9,5,2,10,3,4] i

passaggi sono [7,9,5,2,10,3,4] [7,9,5,2,10,3,4] [5,7,9,2,10,3,4] [2,5,7,9,10,3,4] [2,5,7,9,10,3,4] [2,3,5,7,9,10,4] [2,3,4,5,7,9,10]

la parte già ordinata è sottolineata

Costo

● numero di confronti nel caso peggiore

(n-1)+(n-2)+(n-3)+...+1=O(n2₎

● numero di assegnamenti nel caso peggiore

(n-1)+(n-2)+(n-3)+...+1=O(n2₎

Quick-sort

● Uno degli algoritmi per l'ordinamento più

efficienti ed utilizzati è il Quick-Sort

● Si tratta di un algoritmo ricorsivo basato sulla

tecnica del “divide et impera”

● Ci sono due fasi

● divide il problema in due o più sottoproblemi dello

stesso tipo e risolvili ricorsivamente

Divide et impera

Si divide la sequenza da

ordinare in due parti

Si ordinano (ricorsivamente) le due parti

Si ricombinano insieme le parti ordinate in modo da

ottenere l'ordinamento di tutta la sequenza

Quick-Sort

● La divisione della sequenza si potrebbe fare in

tanti modi

● Nel Quick-Sort si divide in un modo che non c'è

bisogno di fare niente quando si ricombinano le due parti già ordinate

● E' sufficiente che ogni elemento della prima

parte sia ≤ di ogni elemento della seconda parte

Partition

● Un modo per ottenere ciò è dato dalla

procedura Partition

● Scelto un elemento x detto “pivot”

● si mettono nella prima parte tutti gli elementi di A ≤x ● si mettono nella seconda parte tutti gli elementi di A

Partition

def partition(A,s,d): x=A[s] j=s for i in range(s+1,d+1): if A[i]<x: j=j+1 scambia(A,i,j) scambia(A,s,j) return j

Commenti

● All'inizio del ciclo for:

● il pivot si trova nella posizione s

● j=s

● Ad ogni iterazione

● gli elementi da s+1 a j sono < del pivot ● gli elementi da j+1 a i-1 sono >= del pivot

● Se A[i]<pivot, A[i] è spostato nella prima parte

incrementando j

● Alla fine del ciclo

Esempio

[9 || 10, 7, 4, 3, 2, 11, 8, 15] [9 || 10, 7, 4, 3, 2, 11, 8, 15] [9 | 7 | 10, 4, 3, 2, 11, 8, 15] [9 | 7, 4 | 10, 3, 2, 11, 8, 15] [9 | 7, 4, 3 | 10, 2, 11, 8, 15] [9 | 7, 4, 3, 2 | 10, 11, 8, 15] [9 | 7, 4, 3, 2 | 10, 11, 8, 15]

Commenti

● Dopo lo scambio finale

● gli elementi da s a j-1 sono < del pivot ● il pivot si trova in posizione j

● gli elementi da j+1 a d sono >= del pivot

● Le due parti da ordinare con il divide et impera

sono perciò

● da s a j-1, e ● da j+1 a d

Quicksort

def quicksort(A,s,d): if s<d: j=partition(A,s,d) quicksort(A,s,j-1) quicksort(A,j+1,d)

Costo

● L'analisi del costo dell'algoritmo Quick-sort è

molto complicata

● Il numero di operazioni dipende dalla scelta del

pivot

● Una scelta buona è quella di creare con la

partition due parti con più o meno la stessa grandezza

● La scelta ottimale per il pivot sarebbe la

Costo

● Il numero di livelli di ricorsione è logaritmico, in

ogni livello il numero di operazioni è O(n), quindi il numero di operazioni totali è O(n log₂n)

● 16

8 8

4 4 4 4

2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Costo

● Se la scelta del pivot è casuale, in media

l'andamento asintotico è sempre O(n log₂n)

● Nel caso peggiore, partition crea sempre una

partizione sbilanciata (1 da una parte e tutti gli altri dall'altra)

● In tale situazione il numero di livelli di ricorsione

è O(n) e quindi il numero totale di operazioni è O(n2₎

Operazioni insiemistiche

● Le operazioni insiemistiche (unione,

intersezione, differenza, ecc.) possono essere facilmente implementate su insiemi

rappresentati come sequenze

● Si ha un vantaggio considerevole se le

Intersezione

● Siano dati due insiemi A e B

● Si usano due indici, i su A e j su B

● Ad ogni passo si confronta A[i] con B[j] ● Se sono uguali, tale elemento è inserito

nell'intersezione C ed i e j sono incrementati

● Altrimenti l'indice relativo all'elemento minore

Intersezione

def intersezione_ordinate(a,b): n=len(a) m=len(b) c=[ ] i=0 j=0

while i<n and j<m: if a[i]==b[j]: c.append(a[i]) i=i+1 j=j+1 elif a[i]<b[j]: i=i+1

Unione

● Per calcolare l'unione tra A e B si usa un

procedimento analogo

● Se A[i] è diverso da B[j] si inserisce nell'unione

C il minore tra i due e l'indice corrispondente è incrementato

● Se sono uguali, tale valore è inserito in C e

entrambi gli indici sono incrementati

● A fine ciclo, tutti i restanti elementi di A (o di B)

Costo

● Sia per il calcolo dell'unione che per

l'intersezione di insiemi rappresentati come sequenze ordinate il costo complessivo è

O(m+n), ove m è il numero di elementi di A e n quello di B

● Se le sequenze non fossero ordinate, il costo

Strutture dati dinamiche elementari: liste concatenate

Strutture dati dinamiche

● Le strutture dati dinamiche nascono

dall'esigenza di memorizzare una collezione di elementi con un numero variabile di elementi e di poter inserire, cancellare e cercare elementi in modo efficiente

● Le sequenze (dette impropriamente liste in

Python) non soddisfano appieno questi

requisiti: inserimenti e cancellazioni non sono così efficienti

Strutture dati dinamiche

● In particolare l'inserimento e la cancellazione

richiedono un'eventuale ridimensionamento della sequenza

● Inoltre se l'inserimento o la cancellazione non

avvengono in fondo alla sequenza, è

necessario spostare gli elementi per far posto al nuovo elemento (nell'inserimento) o eliminare lo spazio occupato dall'elemento (nella

Strutture dati dinamiche

● Infine, in molti linguaggi di programmazione, ad

esempio in C (ma non in Python) gli array

hanno una lunghezza fissa che non può essere in alcun modo alterata

● Diventa quindi indispensabile avere un metodo

di memorizzazione di collezioni di dati che sia più flessibile rispetto alle sequenze e agli array

Liste

● Le liste sono le strutture dati più semplici ● L'organizzazione è di tipo “lineare”: ogni

elemento ha un immediato successore (tranne l'ultimo) ed un immediato predecessore (tranne il primo)

● Si possono creare liste unidirezionali e liste

bidirezionali

● In questo corso vedremo solo le liste

Liste bidirezionali

● Ogni elemento ha una chiave ed è collegato

all'elemento precedente e all'elemento

successivo, tramite dei riferimenti prev e next

● Nei due casi estremi (primo ed ultimo

elemento) i riferimenti valgono None

● La lista è gestita memorizzando solo il

riferimento al primo (first) e all'ultimo elemento (last)

Definizione delle strutture dati

class nodo_lista: def __init__(self): self.key=None self.prev=None self.next=None class lista: def __init__(self): self.first=None self.last=None

Esempio di lista

● Come esempio creiamo la lista

● Come primo passo creiamo tre variabili

nodo_lista

p1=nodo_lista( ) p2=nodo_lista( ) p3=nodo_lista( )

Esempio di lista

● Inseriamo le chiavi

p1.key=1 p2.key=2 p3.key=3

● Infine creiamo i collegamenti

p1.next=p2 p2.next=p3 p3.prev=p2 p2.prev=p1

Esempio di lista

● Creiamo ora una variabile lista

L=lista( ) L.first=p1 L.last=p2

● Chiaramente serve un meccanismo più

semplice di creazione di una lista tramite inserimento

Inserimento all'inizio

● Per inserire un nodo di chiave x all'inizio di una

lista L def ins_inizio(L,x): n=nodo_lista() n.key=x n.next=L.first if L.first != None: L.first.prev=n else: L.last=n

Inserimento alla fine

● Per inserire un nodo di chiave x alla fine di una

lista L def ins_fine(L,x): n=nodo_lista() n.key=x n.prev=L.last if L.last != None: L.last.next=n

Esempi

● Inserimento all'inizio di 5

Inserimento

● L'inserimento sia all'inizio che a fine lista

avviene in un numero fisso di operazioni (costo O(1))

● In maniera analoga può essere svolto

l'inserimento in un punto arbitrario della lista (ad esempio prima o dopo un dato nodo)

Cancellazione

● Per cancellare un nodo p in una lista L occorre

“scavalcare” p def cancella(L,p): if p.next!=None: p.next.prev=p.prev else: L.last=p.prev if p.prev!=None: p.prev.next=p.next else:

Cancellazione

● Ad esempio per cancellare il 4

Scrivere una lista sullo schermo

● Per scrivere il contenuto di una lista sullo

schermo def scrivi_lista(L): p=L.first while p!=None: print p.key, p=p.next print

Scansione

● In generale il frammento di codice

p=L.first

while p!=None:

fai qualcosa con p.key p=p.next

Scansione

● Infatti p inizialmente si riferisce al primo

elemento di L

● Ad ogni passo p è aggiornato con p.next

● se p si riferisce al primo elemento, p.next si riferisce

al secondo

● se p si riferisce al secondo elemento, p.next si

riferisce al terzo

● …

● se p si riferisce all'ultimo elemento, p.next è None

Scansione all'indietro

● Una lista bidirezionale, in virtù della presenza di

prev, può anche essere scorsa all'indietro p=L.last

while p!=None:

fai qualcosa con p.key p=p.prev

Lunghezza

● Per calcolare la lunghezza di una lista è

sufficiente contare i nodi def lunghezza(L): p=L.first conta=0 while p!=None: conta=conta+1 p=p.next return conta

Ricerca

● Anche se gli elementi di una lista sono ordinati,

non si può usare la ricerca binaria (manca l'equivalente di A[m])

● Si può invece usare la ricerca lineare

def ricerca_lineare(L,x): p=L.first

trovato=False

while p!=None and trovato==False: if p.key==x:

trovato=True else:

N-esimo elemento

● Per trovare l'n-esimo elemento di una lista

(equivalente di A[n] per una sequenza A) def ennesimo(L,n):

p=L.first i=0

while i<n and p!=None: p=p.next

i=i+1 return p

Copia

● Per creare una copia fisica di una lista occorre

definire una funzione apposita che usa ins_fine def copia_lista(L): L1=lista() p=L.first while p!=None: ins_fine(L1,p.key) p=p.next

Conversione da sequenza a lista

● E' possibile creare una lista a partire da una

sequenza def seq_lista(a): n=len(a) L=lista() for i in range(0,n): ins_fine(L,a[i]) return L

Ricorsione e liste

● Una definizione ricorsiva di lista è la seguente ● Una lista è vuota oppure è composta da un

nodo n collegato ad una lista (quella che inizia con n.next)

● Un nodo n si può sempre pensare come primo

elemento della lista formata da n, dal suo successore, dal successore del successore ecc.

Ricorsione e liste

● Per ottenere una definizione ricorsiva di una

funzione f che opera con le liste

● Il caso base è quando la lista è vuota o ha un

solo elemento

● La regola ricorsiva mette in relazione il valore di

f sull'intera lista con il valore di f sulla sottolista che inizia con il secondo elemento

● Avremo bisogno sempre di una funzione

supplementare che “inizia” la ricorsione con la sottolista che parte da L.first

Esempio di ricorsione con le liste

● Come primo esempio calcoliamo

ricorsivamente la lunghezza di una lista

● Il caso base è ovvio: la lista vuota ha lunghezza

0

● La regola ricorsiva è: se la sottolista che inizia

con il secondo elemento ha lunghezza L, allora la lista ha lunghezza L+1

Esempio di ricorsione con le liste

def lunghezza(L): return lungh_ric(L.first) def lungh_ric(n): if n==None: ris=0 else: ric=lung_ric(n.next) ris=ric+1 return ris

Esempio di ricorsione con le liste

● Come secondo esempio vediamo come si

scrivono le chiavi di una lista sullo schermo

● Nel caso base non occorre fare niente: la

Esempio di ricorsione con le liste

def scrivi_lista(L): scrivi_ric(L.first) def scrivi_ric(n): if n!=None: print n.key, scrivi_ric(n.next)

Confronto liste e sequenze

sequenze liste

concatenate inserimento O(n) O(1)

cancellazione O(n) O(1)

Code

● Una coda è una struttura dati che consente due

operazioni

● inserire un nuovo elemento

● restituire l'elemento inserito meno recentemente

eliminandolo dalla coda

● La politica di gestione di una coda si chiama

FIFO (First In First Out), ovvero

Code

● Ad esempio inserendo in una coda gli elementi

A, B e C (in questo ordine), il primo ad essere eliminato A, poi B

● Se a questo si inserisce D, il prossimo ad

essere eliminato è C, poi D. Infine la coda è vuota

● Una coda può essere facilmente implementata

Implementazione di una coda

tramite lista concatenata

def entra_coda(coda,x): ins_inizio(coda,x) def esci_coda(coda): x=coda.last.key cancella(coda,coda.last) return x

Implementazione di una coda

mediante una sequenza

● In maniera alternativa una coda limitata (cioè

con un numero massimo di elementi) può

essere implementata mediante una sequenza

● Occorrono poi due indici (p e u) che indicano,

rispettivamente il primo e l'ultimo elemento della coda

● Tali indici sono gestiti in modo circolare

(quando arrivano in fondo alla sequenza sono riportati all'inizio) in modo da sfruttare al

Implementazione

Supponiamo di voler gestire al massimo 10 elementi class coda_sequenza: def __init__(self): self.dati=[None]*10 self.p=-1 self.u=-1

Implementazione

def entra_coda( coda,x): coda.u=coda.u+1 if coda.u==10: coda.u=0 coda.dati[coda.u]=x def esci_coda(coda): x=coda.dati[coda.p] coda.p=coda.p+1 if coda.p==10: coda.p=0

Pile

● Una pila è una struttura dati che consente due

operazioni

● inserire un nuovo elemento

● restituire l'elemento inserito più recentemente

eliminandolo dalla pila

● La politica di gestione di una pila si chiama

LIFO (Last In First Out), ovvero

Pile

● Ad esempio inserendo in una pilaa gli elementi

A, B e C (in questo ordine), il primo ad essere eliminato C, poi B

● Se a questo si inserisce D, il prossimo ad

essere eliminato è D, poi A. Infine la pila è vuota

● Anche una pila può essere facilmente

Implementazione di una pila

mediante una lista concatenata

def entra_pila(pila,x): ins_fine(pila,x) def esci_pila(pila): x=pila.last.key cancella(pila,pila.last) return x

Implementazione di una pila con

una sequenza

● L'implementazione di una pila limitata tramite

una sequenza è simile a quella di una coda limitata, serve solo l'indice u e non serve la gestione circolare

class pila_sequenza: def __init__(self):

self.dati=[None]*10 self.u=-1

Implementazione

def entra_pila(pila,x): pila.u=pila.u+1 pila.dati[pila.u]=x def esci_pila(pila): x=pila.dati[pila.u] pila.u=pila.u-1 return x

Alberi

● Gli alberi sono una generalizzazione della lista

concatenata

● Ogni elemento di un albero è collegato con

alcuni altri elementi

● Le due proprietà che devono essere rispettate

sono dai collegamenti (non tenendo conto del verso delle frecce)

● Ogni elemento deve essere collegato ad almeno a

Terminologia

● Gli elementi si chiamano nodi e ognuno di essi

ha una chiave

● C'è un solo elemento a cui non arrivano frecce:

si chiama radice

● Ogni altro nodo N ha un'unica freccia entrante:

il nodo M a cui è collegato si chiama padre (o

genitore) di N, mentre N è detto figlio di M

Terminologia

● Dato un nodo N, si chiamano discendenti di N

i figli di N, i figli dei figli e così via

● Il numero di frecce che bisogna percorrere per

arrivare dalla radice ad un nodo si chiama

livello (o profondità) del nodo

● L'altezza di un albero è il massimo livello delle

foglie

● Il massimo numero di figli è chiamato grado

Alberi

● Gli alberi sono molto utilizzati nell'informatica ● Ad esempio l'organizzazione dei file e delle

directory (file system) dei moderni sistemi operativi forma un albero per ogni disco (o dispositivo di memorizzazione) in cui

● i nodi sono file e directory

● un nodo è un figlio di una directory se il nodo è

Alberi binari

● Gli alberi con grado 2 sono chiamati alberi binari

● I figli di un nodo sono chiamati figlio di sinistra

e figlio di destra

● Un nodo può avere sia entrambi i figli, sia un

solo figlio (a sinistra o a destra), sia nessun figlio

● Sono una struttura dati molto utilizzata in molti

Esempio

● Negli esempi useremo il seguente albero

Alberi e sottoalberi

● Dato un nodo N si chiama sottoalbero di sinistra la

parte di albero che ha come radice il figlio sinistro di N

● Analogamente è definito il sottoalbero di destra ● Ad esempio per il nodo 0

Sottoalbero

di sinistra Sottoalbero

Definizione ricorsiva

● Una definizione ricorsiva di albero binario è la

seguente

● Un albero binario è vuoto oppure è formato da

un nodo (radice) a cui sono collegati due alberi binari, uno a sinistra e l'altro a destra

Alberi binari

● Ogni nodo è collegato, mediante dei riferimenti,

ai suoi due figli di sinistra (left) e di destra (right)

● Se un figlio non c'è si usa il valore None

● Inoltre è collegato all'eventuale nodo genitore

(par)

Alberi binari

class nodo_albero: def __init__(self): self.key=None self.par=None self.left=None self.right=None

Esempio

n1=nodo_albero() n2=nodo_albero() n3=nodo_albero() n1.key=1 n2.key=2 n3.key=3 n1.left=n2 n1.right=n3 n2.par=n1 n3.par=n3

Visite

● Lo svolgimento di un'operazione su tutti i nodi

di un albero (binario) si chiama visita

● Un albero binario si può visitare in tre modi

principali

● pre order o visita anticipata ● in order

● post order o visita posticipata

Pre-order

Il nodo è visitato prima di tutti i suoi discendenti

• def pre_order(T):

if T != None:

print T.key,” “,

pre_order(T.left) pre_order(T.right)

• I nodi visitati nell'esempio sono nell'ordine

In-order

Il nodo è visitato dopo i suoi discendenti di sinistra, ma prima di quelli di destra

● def in_order(T):

if T != None:

in_order(T.left) print T.key,” “,

in_order(T.right)

Post-order

Il nodo è visitato dopo tutti i suoi discendenti

● def post_order(T):

if T != None:

post_order(T.left) post_order(T.right) print T.key,” “,

● I nodi visitati sono nell'ordine

Espressione come

albero binario

● Un'espressione del tipo 7*3+(5-8/2) può essere

Espressioni e alberi binari

● Un'espressione rappresentata mediante un

albero binario ha come foglie numeri e variabili, mentre ogni nodo è un'operazione

● Può essere visualizzata sullo schermo

mediante una visita in-order

● Può essere inoltre valutata (ovvero calcolata)

Gestione di un albero

● L'inserimento di un nuovo nodo “in fondo

all'albero”, cioè come “figlio mancante” di un nodo già esistente è facile: basta effettuare i collegamenti

● E' un po' più complicato inserire un nuovo nodo

n1 “in mezzo all'albero”, cioè come nuovo figlio di un nodo n2 che ha già il figlio in questione

Gestione di un albero

● La cancellazione di un nodo foglia n è facile,

basta eliminare i collegamenti

● Se il nodo n ha un solo figlio f, è sufficiente

collegare il genitore di n al nodo f

● Se invece n ha due nodi, il modo più semplice

per ovviare al problema, è quello di trovare un nodo c che abbia 0 o 1 figlio, di mettere la

chiave di c al posto di quella di n e infine di cancellare c

Alberi binari di ricerca

● Un albero binario di ricerca consente di cercare

"velocemente" un elemento all'interno di un

albero, in modo da raggiungere, se possibile, la ricerca binaria su una sequenza

● Per facilitare la ricerca gli elementi devono

Alberi binari di ricerca

● In un albero binario di ricerca (ABR) ogni

elemento deve essere

● Minore o uguale di tutti gli elementi che si trovano

nel sottoalbero di sinistra

● Maggiore o uguale di tutti gli elementi che si

trovano nel sottoalbero di destra

● Si noti che sia il sottoalbero di sinistra che

Ricerca

● E' l'equivalente della ricerca binaria sulle

sequenze

● Partendo dalla radice, confronta la chiave del

nodo corrente n con la chiave da cercare x

● Se è uguale a x, la ricerca termina con

successo

● Se è minore di x, si passa al nodo di destra

(quelli di sinistra sarebbe ancora più piccoli)

● Se è maggiore di x, si passa al nodo di sinistra ● Termina con insuccesso quando si arriva ad un

Ricerca

def cerca_abr(r,x): trovato=False

while r!=None and not trovato: if r.key==x: trovato=True elif r.key>x: r=r.left else: r=r.right

Ricerca (versione ricorsiva)

def cerca_abr_ric(r,x): if r==None: ris=None elifr.key==x: ris=r elifr.key>x: ris=cerca_abr_ric(r.left,x) else: ris=cerca_abr_ric(r.right,x) return ris

Costo

● Il numero di confronti, nel caso peggiore, è pari

all'altezza dell'albero

● Infatti il numero più alti di passaggi si ha

quando si cerca un elemento che sta nella foglia più profonda (o dovrebbe stare lì...)

● Un albero con N nodi ha altezza pari almeno a

log₂N

Inserimento

● Per inserire un nodo di chiave x in un ABR

occorre innanzitutto cercare il punto in cui mettere il nuovo nodo

● Ciò corrisponde a cercare x, ricordandosi

dell'ultimo nodo p su cui la ricerca è passata

Inserimento

def ins_abr(r,x): radice=r p=r while r!=None: p=r if r.key>x: r=r.left else: r=r.right n=nodo_albero() n.key=x n.parent=p if p!=None: if p.key>x: p.left=n else: p.right=n else: radice=n return radice

Inserimento (versione ricorsiva)

def ins_abr_ric(r,x): if r==None: ris=nodo_albero() ris.key=x elif r.key>x: ric=ins_abr_ric(r.left,x) ric.parent=r r.left=ric ris=r else: ric=ins_abr_ric(r.right,x) ric.parent=r r.right=ric ris=r

Costo

● Anche in questo caso il costo dipende

dall'altezza dell'albero

● Infatti nel caso peggiore il nuovo nodo sarà

inserito come nuovo figlio della foglia più profonda

Minimo e massimo

● Il minimo di un ABR è la foglia più a sinistra,

mentre il massimo è la foglia più a destra def minimo(r):

while r.left != None: r=r.left

return r

def massimo(r):

while r.right != None: r=r.right

Successore

● Il successore di un nodo con chiave x è tra tutti

i nodi con chiave >x quello che la chiave minore

● Nell'albero di esempio il successore di 7 è 10,

mentre quello di 12 è 13

● Il successore di un nodo che ha il figlio destro si

trova prendendo il minimo del sottoalbero destro

Cancellazione

● Per cancellare un nodo n da un ABR i casi

semplici sono quando n è una foglia o n ha un solo figlio

● In tali situazioni si opera come negli alberi

binari

● Nel caso in cui n abbia 2 figli, il nodo che

prenderà il posto di n è il suo successore

● Nella funzione

● c è il nodo che sarà realmente cancellato (n o il suo

successore)

Cancellazione

def cancella(r,n): if n.left==None or n.right==None: c=n else: c=successore(n) n.key=c.key if c.left!=None: f=c.left else: f=c.right g=c.parent if f!=None: f.parent=g if g==None: r=f elif g.left==c: g.left=f else: g.right=f return r

Costo

● Anche in questa operazione il numero di

passaggi dipende dall'altezza dell'albero

● Infatti potrebbe essere necessario trovare il

successore di un nodo e questo potrebbe essere la foglia più profonda

Considerazioni finali

● I tempi di esecuzione delle operazioni sugli

ABR dipendono dall'altezza

● Nel caso peggiore l'altezza è N, pari al numero

di nodi

● Ma con una gestione oculata si può tenere

l'altezza più bassa possibile, cioè log₂N

● In questo modo gli ABR hanno, nella ricerca, le