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



Scaricare 445 b.
17.11.2017
Dimensione del file445 b.


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)


Alberi binari: rappr. sequenziale

  • Utilizza array di lunghezza predefinita

  • Alberi completi

  • Per gli alberi non completi serve un tag booleano che indica se il nodo esiste



Alberi binari: rappr. sequenziale



Svantaggi:

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

  • Serve una variabile inizio per definire l'indice della radice all'interno dell'array



Alberi binari: rappr. collegata mediante array



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



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 6 5 7 2



Visita in ampiezza di un grafo

  • 7 5 6 4 2 3 1



Rappresentazione dei grafi



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


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



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



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:



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



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:



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






©astratto.info 2017
invia messaggio

    Pagina principale