iconNotes in Public

Alberi (Struttura Dati)

2 min read

Index

  1. Introduzione
  2. Nodi (definizioni)
  3. Esempio
  4. Alberi Ordinati

Related

Introduzione

L’albero è una struttura dati estremamente versatile, utile per modellare una grande quantità di situazioni reali e progettare le relative soluzioni algoritmiche.

Nodi e Archi

L’albero in informatica è una struttura dati che rappresenta un insieme di nodi interconnessi da archi. È formato da due

  • Nodo contiene informazioni
  • Arco stabilisce un collegamento gerarchico fra due nodi.

Livelli

I nodi sono organizzati in livelli, numerati in ordine crescente allontanandosi dalla radice.

Altezza

L’Altezza di un albero è la lunghezza del più lungo cammino dalla radice ad una foglia.

  • Una albero di altezza contiene livelli, numerati da a .

Nodi (definizioni)

Radice

La radice di un albero in informatica è il nodo più alto dell’albero (livello 0), rappresentante l’origine del tutto.

  • Non ha un padre o fratelli
  • È l’unico antenato comune ti tutti i nodi

Padre

Dato un qualunque nodo v che non sia la radice, il primo nodo che si incontra sul cammino da v alla radice viene detto padre di v.

Fratelli

Nodi che hanno lo stesso padre sono detti fratelli.

  • La radice è l’unico nodo che non ha padre.

Antenato

Ogni nodo sul cammino da v alla radice viene detto antenato di v.

Figli

Tutti i nodi che hanno v come padre sono detti figli di v.

Foglie

I nodi che non hanno figli sono dette foglie.

Discendenti

Tutti i nodi che ammettono v come antenato vengono detti discendenti di v.

Esempio

Alberi Ordinati

Un albero si dice ordinato se attribuiamo un qualche ordine ai figli di ciascun nodo.

Se un nodo ha figli, allora vi è un figlio che viene considerato primo, uno che viene considerato secondo, …, uno che viene considerato k-esimo.

Una particolare sottoclasse di alberi radicati e ordinati è quella degli Alberi Binari, che hanno la particolarità che ogni nodo ha al più due figli.

Graph View

Backlinks