Albero binario
Un albero binario è una struttura dati formata da nodi collegati tra loro da archi. Ogni nodo è strutturato in modo particolarmente semplice, ovvero una chiave, il “contenuto” del nodo, e poi due puntatori, ovvero un puntatore al figlio desto e uno al figlio sinistro. Questa è una limitazione rispetto agli alberi tradizionali per i quali non si era mai messo un limite alla ramificazione, invece in questo caso, ogni nodo può avere al massimo due figli.
Ecco quali sono le caratteristiche che denotano un albero binario, premettendo che se anche uno solo di questi parametri è trascurato allora l’albero non è più binario.
1. Ogni nodo ha al più due figli
2. I figli sono ordinati tra loro
3. Ogni figlio può essere radice di un nuovo albero
I vantaggi di questa implementazione non sono subito evidenti, si accetti come postulato che la visita di una lista implementata con un albero binario è molto efficiente.
Implementare gli alberi binari
In questa sezione trattiamo l'implementazione degli alberi binari dal punto di vista teorico, facendo ricordo a strutture di programmazione generiche, sarà poi compito del programmatore decidere come implementare queste strutture sulla base del linguaggio di programmazione che si troverà ad usare.
Esistono vari sistemi, ma il più semplice risulta essere quello che utilizza un array che contiene i nodi dell’albero secondo questa logica: La radice occupa la prima posizione dell’array e i figli di questa radice sono a loro volta nell’array e occupano come posizione (2i) e (2i+1) dove i è la posizione della radice, del padre, dei due figli.
Si fa notare che questa implementazione è ottimale se l’albero è completo cioè se tutti gli elementi che costituiscono l’albero hanno esattamente due figli, tranne ovviamente le foglie, altrimenti è necessario un tag booleano, in realtà un array di accompagnamento, che ci indica se la posizione è valida o meno.
Interpretiamola: in A, posizione 1, c’è sempre la radice, in posizione 2 e 3 troviamo i figli B e C. Prendiamo il figlio B, posizione 2, i suoi figli sono in 4 e 5, ma, la colonna dei flag ci dice che le posizioni 4 e 5 sono disattivate, infatti B non ha figli, al contrario, C posizione 3, in 6 e 7 ha proprio i valori cercati e cioè i suoi due figli D, E.
I vantaggi dell’utilizzo di questa implementazione sono la semplicità di accesso e la semplicità di gestione degli elementi della lista, al contrario, le operazioni di inserimento e in generale la dimensione considerevole di un array di un grande albero giocano a sfavore di questa implementazione che risulta essere di conseguenza sconveniente da usare.
Un'altra implementazione che prevede l’uso di array è quello della “rappresentazione collegata con array"", in cui, in una tabella a tre colonne abbiamo in una colonna il valore, in quella sinistra l’indirizzo, nella stessa tabella, del figlio sinistro e in quella destra l’indirizzo di quella destra. E’ necessario aggiungere una variabile inizio per indicare il punto in cui dobbiamo iniziare l’analisi, al contrario, se un indirizzo è a zero è da considerarsi NULL.
Iniziando da 1 , A ha figli che sono in 2 e 3 , il figlio B non ha discendenti, quello C invece ha come discendenti 6 a sinistra e 7 a destra, cioè D ed E.
Lo stesso di può ottener prendendo in considerazione anziché un array, un semplice nodo strutturato a tre campi, etichetta, figlio sinistro, figlio destro e con un puntatore al primo nodo, e di fatto ci ricolleghiamo all’immagine di accompagnamento alle due tabelle precedenti.
Per quanto riguarda l’altezza di un albero binario, questa è 1, se l’albero ha un solo nodo, è zero se l’albero è vuoto e, se invece sono presenti più nodi, l’altezza sarà:
Dove come cammino si intende il percorso misurato in nodi attraversati per raggiungere una posizione a partire dalla radice.
Nel caso dell’albero nella figura qui sopra, l’altezza è 1+2 cioè 3.
Esistono alcune formule per calcolare le caratteristiche degli alberi:
| Log2(n+1)</td> | Altezza di un albero pieno di n nodi |
| 2h-1 | Numero massimo di nodi in un albero binario di altezza h |
| h | Altezza o numero minimo di nodi di un albero con altezza h |
| 2*l | Numero massimo di nodi ad un livello l (elle) |