Alberi

Indice

๐Ÿ“ Definizione 1

Un albero consiste di un insieme di nodi e un insieme di archi orientati che connettono coppie di nodi, con le seguenti proprietร :

  • Un nodo dellโ€™albero รจ designato come nodo radice
  • Ogni nodo n, a parte la radice, ha esattamente un arco entrante
  • Esiste un cammino unico dalla radice ad ogni nodo
  • Lโ€™albero รจ connesso

๐Ÿ“ Definizione 2

Un albero รจ dato da:

  • Un insieme vuoto, oppure
  • Un nodo radice e zero o piรน sottoalberi, ognuno dei quali รจ un albero; la radice รจ connessa alla radice di ogni sottoalbero con un arco orientato

๐Ÿ“š Terminologia

Profonditร  di un nodo (depth)

La lunghezza del percorso dalla radice al nodoย (cioรจ il numero di archi tra la radice e il nodo).

Livello (level)

Lโ€™insieme di nodi alla stessa profonditร .

Altezza albero (height)

La profonditร  massima della sue foglie.

โŒจ๏ธ Implementazione

Esistono diversi modi per memorizzare un albero, piรน o meno indicati a seconda del numero massimo e medio di figli presenti.

Realizzazione con vettore dei figli

ImplVettoreFigli.png500

Campi memorizzati nei nodi:

  • parent: reference al nodo padre
  • vettore dei figli: a seconda del numero di figli, puรฒ comportare una discreta quantitร  di spazio sprecato

Realizzazione primo figlio, prossimo fratello

Implementato come una lista di fratelli

ImplListaFigli.png500

Realizzazione con vettore dei padri

Lโ€™albero รจ rappresentato da un vettore i cui elementi contengono il valore associato al nodo e lโ€™indice della posizione del padre nel vettore.

ImplVettorePadri.png500

Per ogni nodo in posizione i nel vettore:

  • Il figlio sinistro si trova nella posizione 2โ‹…i+1
  • Il figlio destro si trova nella posizione 2โ‹…i+2