Un albero binario è un tipo di struttura dati utilizzata nella programmazione del computer per archiviare, ordinare e accedere alle informazioni. Gli alberi binari sono la varietà più semplice di alberi, ma sono molto utili e facili da implementare. Una tipica implementazione di un albero binario si basa su un nodo radice collegato ad una serie di nodi che compongono l’albero stesso tramite variabili puntatore. Questo tipo di albero deriva il suo nome dal fatto che nessun nodo all’interno dell’albero può avere più di due figli.
Le strutture dati ad albero sono disponibili in molte varietà. Sono costituiti da diversi nodi, che sono organizzati in uno schema gerarchico. Un singolo nodo, la radice, è il punto di accesso attraverso il quale l’intero albero dei dati può essere ricercato o altrimenti manipolato. Questo nodo radice punta al nodo superiore all’interno dell’albero stesso.
Qualsiasi nodo all’interno di un albero, ad eccezione del nodo più in alto, avrà un nodo padre che si trova sopra di esso nella gerarchia dell’albero. Può anche avere nodi figlio, che si trovano al di sotto di esso. Si accede a un dato nodo tramite quelli sopra di esso nell’albero e fornisce l’accesso a quelli sotto di esso.
Le strutture dati ad albero binario consentono a ciascun nodo di non avere più di due figli. Un dato nodo può quindi avere zero, uno o due nodi figli ad esso collegati. Gli alberi binari ordinari consentono nodi con qualsiasi numero di figli in qualsiasi punto dell’albero. Inoltre, non pongono restrizioni sulla disposizione dei valori archiviati nei nodi che compongono un albero.
Le strutture di dati sono più utili quando migliorano la velocità con cui è possibile accedere ai dati da un computer e le versioni modificate degli alberi binari vengono utilizzate per migliorarne l’efficienza. Un albero di ricerca binario è uno in cui tutti i valori dei dati situati sul ramo discendente sinistro di un dato nodo hanno valori uguali o inferiori al valore memorizzato in quel nodo. I valori sul lato destro di un nodo in un albero binario ordinato devono, a loro volta, essere maggiori del valore nel nodo base. Questo ordinamento dei dati consente di scrivere un algoritmo di ricerca molto più efficiente.
Anche la forma di un albero binario è importante per determinare l’efficienza di un algoritmo di ricerca. La varietà meno efficiente di un albero binario è quella in cui ogni nodo ha un solo figlio. Un computer potrebbe dover esaminare ogni elemento di dati nell’intero albero per individuare una singola informazione in questa configurazione. L’albero binario più efficiente, al contrario, è quello in cui ogni nodo, tranne quelli nella parte inferiore dell’albero, ha due figli e in cui tutti i nodi foglia, i nodi inferiori dell’albero, sono alla stessa distanza dalla radice.