Albero (informatica)

Da Wikipedia, l'enciclopedia libera.

In informatica, un albero (tree in inglese) è quella struttura dati che modella un albero radicato. Come nella teoria dei grafi, anche in informatica un albero si compone di due strutture fondamentali: il nodo, che in genere contiene informazioni, e l'arco che collega gerarchicamente due nodi tra loro. Viene definito quindi il concetto di nodo padre che tramite un arco orientato si collega ad un nodo figlio. In questo modo, ogni nodo può avere al massimo un unico arco entrante, ed un numero variabile di archi uscenti. Un nodo che non ha archi entranti, è detto radice (root) dell'albero, ed è unico per l'albero; se un nodo non ha archi uscenti, è detto foglia (leaf node), e in ogni albero ve n'è almeno uno. Ovviamente, un nodo può essere contemporaneamente padre (se ha archi uscenti) e figlio (se ha un arco entrante). Solitamente ogni nodo porta con se delle informazioni e molto spesso anche una chiave con cui è possibile identificarlo univocamente all'interno dell'albero. L'altezza dell'albero è il massimo delle distanze tra la radice e le sue foglie.

[modifica] Tipi di albero

Un albero binario non ordinato

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. Una 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 è $Δ$ -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 ed il minimo di K non è maggiore di $Δ$ . 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
Albero Heap
B-Albero
Albero Red Black
Quadtree

[modifica] Implementazione

L'implementazione più diffusa degli alberi si basa su strutture collegate, ovvero da oggetti (i nodi) che referenziano altri oggetti. Una implementazione tipica di un nodo di un albero binario in Java può essere la seguente

public class Nodo {
    public Nodo figlioSinistro;
    public Nodo figlioDestro;

    //le informazioni contenute dal nodo, ad esempio una stringa
    public String informazioni;
    //una chiave univoca per identificare il nodo, ad esempio un intero
    public int chiaveUnivoca; 
}

Notoriamente, gli alberi heap sono implementabili anche tramite array o vettori

[modifica] Metodi di visita

Visita in pre-ordine: viene visitata prima la radice, dopo il sottoalbero sinistro e alla fine il sottoalbero destro
Visita in ordine: Prima viene visitato il sottoalbero sinistro, poi la radice e alla fine il sottoalbero destro
Visita in post-ordine: prima viene visitato il sottoalbero sinistro, poi quello destro e alla fine la radice