albero

albero

albero particolare → grafo a struttura ramificata. Viene definito a partire dalla più generale nozione di → albero libero, fissando un suo nodo come radice. Essendo nota la radice, risulta stabilita la suddivisione dei nodi in livelli. Il livello della radice è 0, mentre il livello di ogni altro nodo N è pari al numero di nodi contenuti nel percorso semplice tra la radice e N, esclusa la radice stessa. Il numero dei livelli è detto profondità dell’albero. La struttura si sviluppa da una radice per ramificazioni successive: si chiama foglia un qualsiasi nodo che non compare in alcun percorso semplice tra la radice e un altro nodo. Le foglie sono anche dette nodi terminali, mentre gli altri nodi sono detti nodi non terminali. Per un albero valgono le proprietà dell’albero libero; di esso, tuttavia, si può dare una definizione più compatta, di tipo ricorsivo, senza fare riferimento esplicito agli archi, che risultano essere un semplice mezzo di ordinamento dei nodi. Un albero è un insieme A di uno o più nodi, tale che:

• un particolare nodo è designato come radice;

• i rimanenti nodi, se esistono, possono essere ripartiti in insiemi disgiunti A1, A2, …, A_m (con m ≥ 0) ciascuno dei quali è a sua volta un albero.

Un albero è, quindi, un particolare grafo privo di ciclicità e rappresenta un ordinamento non lineare di dati. È detto, a sua volta, albero ordinato quando è significativo l’ordine in cui si considerano i nodi di ciascun livello.

☐ Nell’organizzazione dei dati, l’albero è una particolare struttura che consente di rappresentare elementi disposti in modo gerarchico e di identificare i rapporti di dipendenza di alcuni elementi da altri. Come struttura di dati, l’albero è rappresentabile graficamente con un diagramma, detto appunto diagramma ad albero, che evidenzia la radice, le diramazioni e i vari livelli. I nodi contengono le informazioni concernenti i dati, messi in relazione tra loro attraverso il cammino determinato dai rami: questi ultimi esprimono una relazione di subordine del nodo in cui entrano rispetto al nodo da cui escono. La radice non possiede alcun ramo entrante, mentre una foglia non possiede alcun ramo uscente. Nel linguaggio comune, per illustrare la struttura di dati ad albero si fa spesso riferimento all’albero genealogico: esso rappresenta la successione dei discendenti di una o più famiglie in cui il capostipite è alla radice dell’albero e i rami corrispondono alla relazione tra genitore e figlio. Da questa analogia antenato-discendente segue che il predecessore di un nodo è il nodo-padre, mentre il successore è il nodo-figlio. La struttura ad albero consente di determinare anche i livelli di profondità, ossia la collezione dei nodi che presentano lo stesso numero di rami predecessori: prendendo come esempio l’albero genealogico, è possibile affermare che due cugini sono parenti dello stesso grado rispetto all’antenato che è il nonno comune. Gli alberi si prestano molto bene alla rappresentazione di informazioni disposte gerarchicamente, quale per esempio il file di un supporto di memoria di un computer.

Molti algoritmi sono costruiti a partire da strutture di dati ad albero, avendo come obiettivo primario la ricerca del dato corrispondente a un particolare nodo. Per questo assume importanza la nozione di visita di un albero, che corrisponde a un percorso semplice che attraversa tutti i suoi nodi.