Gli alberi

Gli alberi

• E' un tipo di dato astratto che rappresenta relazioni gerarchiche tra oggetti

• Le relazioni esplicate sono tra:

– genitori – figli

– fratelli

• Radice, foglie

Gli alberi binari

• Ogni nodo ha al massimo 2 figli

• Sui figli è definito un ordinamento

• Ogni figlio può essere la radice di un nuovo albero binario

• Vantaggio: migliorare l'efficenza della

visita di una lista

Gli alberi binari

• Metodi:

– test_albero_vuoto: alb_bin  boolean

– costruisci: alb_bin x nodo x alb_bin alb_bin – radice: alb_bin  nodo

– sinistro: alb_bin  alb_bin

– destro: alb_bin  alb_bin

Gli alberi binari

• Algoritmi di visita:

– visita in preordine (ABCD)

– visita in postordine (BDECA)

– visita simmetrica (BADCE)

A

B C

D E

Alberi binari: rappr. sequenziale

• Utilizza array di lunghezza predefinita

– radice in prima posizione

– figli in posizione (2i) e (2i+1)

• Alberi completi

• Per gli alberi non completi serve un tag

booleano che indica se il nodo esiste

A

B C

D E

A true B true C true 0 false 0 false D true 1

2 3 4 5 6

E true 7

Alberi binari: rappr. sequenziale

• Svantaggi:

– utilizzo elevato memoria

– operazioni in inserimento complesse (richiedono spostamenti nell'array)

• Vantaggi:

– accesso semplice (anche per elementi ad una specifica profondità)

Alberi binari: rappr. sequenziale

Alberi binari:

rappresentazione collegata

• Ogni elemento della lista contiene:

– un atomo (la radice dell'albero) – una lista (sottoalbero sinistro) – una lista (sottoalbero destro)

( A (B () () ) ( C (D () () ) (E () () ) ) )

Alberi binari:

rappr. collegata mediante array

• Array a tre valori:

– indice sottoalbero sinistro – valore del nodo

– indice sottoalbero destro

• Serve una variabile inizio per definire

l'indice della radice all'interno dell'array

0 D 0

5 A 3

1 C 6

0 0 0

0 B 0

0 E 0

1 2 3 4 5 6

Inizio = 2

Alberi binari:

rappr. collegata mediante array

A

B C

D E

Alberi binari: rappr.

collegata mediante puntatori

• Ogni nodo viene rappresentato con tre campi:

– l'informazione associata al nodo

– un puntatore al sottoalbero di sinistra

– un puntatore al sottoalbero di destra

Alberi binari: rappr.

collegata mediante puntatori

A

B C

D E

A

0 B 0

C

0 E 0

0 D 0

Esercizio

• Data in ingresso una rappresentazione parentetica di un albero, generare

l'albero corrispondente utilizzando la

rappresentazione collegata sia mediante

array che mediante puntatori

Alberi binari di ricerca

• Problema:

– memorizzare grosse quantità di dati

soggetti a frequenti operazioni di ricerca

• Soluzione:

– utilizzo di alberi di ricerca in cui il valore di un nodo è per definizione maggiore o

uguale di quello dei nodi del sottoalbero sx,

e minore del sottoalbero dx

Alberi binari di ricerca

• Vantaggi:

– minor complessità

• Requisiti:

– profondità ridotta dell'albero – alberi bilanciati

– bilanciamento dell'albero

Alberi n-ari

• Non hanno limiti sul numero di figli

• Generalmente:

– visita solo preordine e postordine – rappresentazione mediante lista

– rappresentazione mediante albero binario (miglior sfruttamento della memoria)

– rappresentazioni tramate

(per ottimizzare certe operazioni)

I grafi

• Strutture che rappresentano relazioni binarie su un insieme di elementi (grafi orientati)

• E' necessario definire politiche di visita

(in presenza di cicli è possibile raggiungere

nodi già visitati; serve un tag di visita)

Visita in profondità di un grafo

1 3 4 7

5 6

2

1 3 4 6 5 7 2

Depth first serach : analoga alla visita in preordine

Visita in ampiezza di un grafo

1 3 4 7

5 6

2

7 5 6 4 2 3 1

Breadth first serach : analoga alla visita in postordine

Rappresentazione dei grafi

• Per rappresentare un grafo esistono diverse possibilità:

– matrice delle adiacenze – liste dei successori

– lista doppia

Matrice delle adiacenze

• La matrice è così definita:

– tante righe e colonne quanti sono i nodi del grafo

– gli elementi della matrice sono di tipo booleano

– il generico elemento e

è definito:

• true, se esiste un arco tra il nodo i e il nodo j

• false, altrimenti

Matrice delle adiacenze

1 2 3 4 5 6 7 1 0 0 1 0 0 0 0 2 1 0 1 0 0 0 0 3 0 1 0 1 0 0 0 4 0 0 0 0 0 1 1 5 0 0 0 0 0 0 0 6 0 0 1 1 1 0 0 7 1 0 0 0 0 0 0

1 3 4 7

5 6

2

Matrice delle adiacenze

• Se i valori dei nodi non sono numerici, serve una corrispondenza tra nodi (ad es. stringhe) con gli indici

• "Vettore dei nodi"

A S R V K P E 1 2 3 4 5 6 7

A E V K

R P

S

Matrice delle adiacenze

• Se anche gli archi sono etichettati, gli

elementi della matrice non saranno

booleani, ma del tipo usato per le

etichette

Matrice delle adiacenze

• Vantaggi:

– semplice

– accesso diretto alle informazioni sugli archi (meccanismi di accesso ad una matrice)

• Svantaggi:

– numero massimo di nodi del grafo – occupazione in memoria pari a N

– l'analisi di un nodo richiede una scansione

Matrice delle adiacenze:

rappresentazione compatta

• Generalmente la matrice delle adiacenze è sparsa, quindi si può usare:

– la rappresentazione compatta usata per le matrici sparse

– una nuova rappresentazione che evidenzia solo gli archi

nodo di part: 1 2 2 3 3 4 4 6 6 6 7

nodo di arr: 3 1 3 2 4 6 7 3 4 5 1

Liste di successori

• Si associa ad ogni nodo una lista semplice, realizzata mediante rappresentazione

collegata

• In ogni lista si memorizza l'insieme dei

successori del nodo senza un ordinamento particolare

• I nodi sono in corrispondenza con gli archi per cui si possono memorizzare anche

evenuali etichette

Liste di successori

1 3 4 7

5 6

2 3 0

1 2 6 0

3

1 0

3 0 4 0 7 0

4 5 0

1

2

3

4

5

6

7

Liste di successori

• Vantaggi:

– migliore occupazione della memoria:

proporzionale a N+M

– più efficiente determinare la lista dei successori

• Svantaggi:

– verifica di un arco tra i e j è poco agevole

– l'utilizzo di un vettore per le info sui nodi

Liste doppie

• Si utilizza una lista per memorizzare le informazioni dei nodi

• Vantaggi:

– il numero di nodi non ha un limite massimo

• Svantaggi:

– l'accesso ai nodi è più complesso

Percorso minimo in un grafo

• Problema:

– dato un grafo con archi etichettati con

valore interi positivi, si trovi il percorso più breve tra due nodi

• Soluzione:

– proposta da Dijkstra