# Albero (informatica)

In informatica, un albero o struttura ad albero (tree in inglese) è la struttura dati che si riconduce al concetto di albero con radice presente nella teoria dei grafi. Un albero si compone di due tipi di sottostrutture fondamentali: il nodo, che in genere contiene informazioni, e l'arco, che stabilisce un collegamento gerarchico fra due nodi: si parla allora di un nodo padre dal quale esce un arco orientato che lo collega a un nodo figlio.
Si chiede inoltre che ogni nodo possa avere al massimo un unico arco entrante, mentre dai diversi nodi possono uscire diversi numeri di archi uscenti. Si chiede infine che l'albero possegga un unico nodo privo di arco entrante: questo nodo viene detto radice (root) dell'albero. Ogni nodo che non presenta archi uscenti è detto foglia (leaf node) e in ogni albero finito, cioè con un numero finito di nodi, si trova almeno un nodo foglia. Ovviamente, un nodo può essere contemporaneamente padre (se ha archi uscenti) e figlio (se ha un arco entrante, ovvero se è diverso dalla radice).
Solitamente ogni nodo porta con sé delle informazioni e molto spesso anche una chiave con cui è possibile identificarlo univocamente all'interno dell'albero. L'altezza o profondità dell'albero è il massimo delle lunghezze dei suoi cammini massimali, cammini che vanno dalla radice alle sue foglie.

## Tipi di albero

Principalmente gli alberi si dividono in alberi non ordinati e alberi ordinati. I primi non seguono alcuna regola per quanto riguarda le relazioni padre-figlio, mentre i secondi impongono che tra il nodo padre e i nodi figli ci sia un ben preciso ordinamento. I più utilizzati in ambito informatico sono sicuramente gli alberi ordinati. Un'altra classificazione può essere fatta in base al numero massimo di figli che un nodo può avere. Si può parlare dunque di Alberi binari in cui ogni nodo può avere al massimo due figli, oppure di Alberi n-ari in cui non vi è un limite al numero massimo di nodi figlio.
Un'ulteriore caratterizzazione è quella che si basa sul cosiddetto bilanciamento: un albero è perfettamente bilanciato se ha tutte le foglie al medesimo livello, ovvero se ogni foglia dell'albero ha la medesima distanza dalla radice. Un albero è $\Delta$-bilanciato se, per ogni nodo $N$, detto $K$ l'insieme dei massimi livelli raggiungibili seguendo tutte le foglie di $N$, la differenza tra il massimo e il minimo di $K$ non è maggiore di $\Delta$.
L'insieme di nodi al di sopra un nodo compone l'insieme dei predecessori, quelli che seguono sono i discendenti.
I tipi di albero più diffusi sono i seguenti:
* Albero binario
* Albero binario di ricerca, chiamato anche BST
* Albero 2-3
* Albero 2-3-4
* Albero AVL
* Heap
* RB-Albero
* B-Albero
* Albero quadramentale
* Albero ottale

## Implementazioni

L'implementazione più diffusa degli alberi si basa su liste concatenate, ovvero da oggetti (i nodi) che referenziano altri oggetti.

### Java

Un'interfaccia tipica di un nodo di un albero binario in Java può essere la seguente:
Notoriamente, gli alberi heap sono implementabili anche tramite array o vettori

### C
#### Elimina elemento
## Visita di alberi in profondità

Molti algoritmi che operano sugli alberi richiedono di visitare tutti i nodi dell'albero, ovvero di definire un (sotto) algoritmo che dato un albero costruisce permutazione dell'insieme dei suoi nodi. I metodi di visita in profondità sono i seguenti.
* Visita in pre-ordine: viene visitata prima la radice, dopo il sottoalbero sinistro e alla fine il sottoalbero destro
Nodepointer è un puntatore al nodo radice da cui parte la ricerca in pre-ordine. son_sx e son_dx sono rispettivamente i figli sinistro e destro del nodo da cui parte la ricerca. L'algoritmo descritto si limita a stampare a video il valore e il markup del nodo considerato.
* Visita in ordine: Prima viene visitato il sottoalbero sinistro, poi la radice e alla fine il sottoalbero destro
Nodepointer è un puntatore al nodo radice da cui parte la ricerca in ordine. son_sx e son_dx sono rispettivamente i figli sinistro e destro del nodo da cui parte la ricerca. L'algoritmo descritto si limita a stampare a video il valore e il markup del nodo considerato.
* Visita in post-ordine: prima viene visitato il sottoalbero sinistro, poi quello destro e alla fine la radice
Nodepointer è un puntatore al nodo radice da cui parte la ricerca in post-ordine. son_sx e son_dx sono rispettivamente i figli sinistro e destro del nodo da cui parte la ricerca. L'algoritmo descritto si limita a stampare a video il valore e il markup del nodo considerato.
Ciascun metodo può essere applicato in modo ricorsivo, ovvero per "visita di un sottoalbero" si intenderà l'applicazione dello stesso algoritmo di visita al nodo radice di tale sottoalbero. In alternativa è possibile implementare la visita in profondità facendo uso di una pila.
Un esempio di metodo esclusivamente non ricorsivo di visita di un albero è invece dato dalla visita in ampiezza.