Albero binario

Da Wikipedia, l'enciclopedia libera.

In programmazione un albero binario è una struttura dati formata da nodi collegati tra loro da archi.

Ogni nodo è strutturato in modo particolarmente semplice: ha come componenti una chiave, il suo contenuto, e due puntatori con ruoli distinti, un puntatore al cosiddetto figlio destro e uno al figlio sinistro; ciascuno dei due figli può mancare. Si tratta quindi di un caso particolare di struttura ad albero, struttura relazionale per la quale non si pongono limiti al numero dei figli.

I vantaggi di questa struttura dati stanno principalmente nel fatto che consentono di implementare liste che possono essere visitate da procedure molto efficienti.

[modifica] Implementare gli alberi binari

In questa sezione trattiamo l'implementazione degli alberi binari dal punto di vista teorico, facendo ricorso 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 flag 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. È 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.

Profondità di un albero: La radice r ha profondità 0, i suoi figli sinistro e destro, hanno profondità 1, i nipoti profondità 2 e cosi via. Quindi se la profondità di un nodo è p i suoi figli non vuoti hanno profondità p+1

Per quanto riguarda l'altezza h di un albero binario è data dalla massima profondità raggiunta dalle sue foglie. Quindi, l'altezza misura la massima distanza di una foglia dalla radice dell'albero, in termini di numero di archi attraversati. Poiché la definizione di alberi si applica anche ai sotto alberi, è più efficiente e semplice trovare l'altezza di un albero binario osservando che l'albero composto da un solo nodo ha altezza pari a 0, mentre un albero con almeno due nodi ha altezza pari all'altezza del suo sottoalbero più alto, incrementata di uno in quanto la radice introduce un ulteriore livello(da cui deriviamo che l'albero vuoto ha altezza pari a -1)

Nel caso dell'albero nella figura qui sopra, l'altezza h è 0(foglie)+1(figli radice)+1(radice)=2.

Esistono alcune formule per calcolare le caratteristiche degli alberi:

[modifica] Implementare gli alberi di ricerca binari su array

Se non è necessario effettuare frequentemente operazioni di inserimento e cancellazioni o non è affatto necessario effettuarle e non si vuole usare troppa memoria è possibile implementare un albero di ricerca binario su un array ordinato, con la restrizione che il numero degli elementi sia 2ⁿ − 1 con .

L'immagine sopra mostra un albero di ricerca binario implementato su un array ordinato di 15 elementi, si comincia ponendo il centro dell'array come radice dell'albero e come sue foglie rispettivamente il centro della parte destra dell'array e il centro della parte sinistra dell'array, si continua applicando ricorsivamente il procedimento fino a che non sono stati coperti tutti gli elementi. Si ottiene quindi l'equivalente dell'albero

la pseudo-algoritmo per la ricerca di una chiave è

Ricerca di una chiave

   N := numero di elementi dell'albero (2^k-1)
   A := array delle N chiavi ordinate in ordine crescente, A[0], A[1] .. A[N - 1]
   key := chiave da cercare
   jump := (N + 1)/4
   i: = (N - 1)/2
   while p > 0 do
       if key == A[i] then
           ricerca finita
       else if key < A[i] then
           i = i - jump
       else if key > A[i] then
           i = i + jump
       endif
       jump = jump / 2
   done
   nessun risultato

.

[modifica] Esempi di alberi binari

Albero del torneo