Gli alberi

Fondamenti di Informatica 1

Gli alberi

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

• Le relazioni esplicate sono tra:– genitori– figli– fratelli

• Radice, foglie• Alberi binari, N-ari


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 trueB trueC true0 false0 falseD true

123456

E true7



• Svantaggi:– utilizzo elevato memoria– operazioni in inserimento complesse

(richiedono spostamenti nell'array)

• Vantaggi:– accesso semplice (anche per elementi

ad una specifica profondità)



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 05 A 31 C 60 0 00 B 00 E 0

123456

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 00 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

56

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

56

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 ei,j è definito:

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

• false, altrimenti



1 2 3 4 5 6 7

1 0 0 1 0 0 0 02 1 0 1 0 0 0 03 0 1 0 1 0 0 0 4 0 0 0 0 0 1 15 0 0 0 0 0 0 0 6 0 0 1 1 1 0 07 1 0 0 0 0 0 0

1 3 4 7

56

2



• 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

PR

S



• Se anche gli archi sono etichettati, gli elementi della matrice non saranno booleani, ma del tipo usato per le etichette



• 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 N2

– 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 7nodo 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

56

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

Gli alberi

Documents

Transcript of Gli alberi