Indietro

ⓘ Albero binario




Albero binario
                                     

ⓘ Albero binario

In informatica un albero binario è un albero i cui nodi hanno grado compreso tra 0 e 2. Per albero si intende un grafo non diretto, connesso e aciclico mentre per grado di un nodo si intende il numero di sotto alberi del nodo, che è uguale al numero di figli del nodo.

Anche lalbero costituito da un solo nodo e nessun arco si considera un albero binario valido, sebbene il grado del nodo in questo caso sia nullo.

Come nel caso generale degli alberi è possibile individuare in maniera non unica un nodo radice: qualunque nodo di grado minore di 3 può essere scelto come radice dellalbero binario. Stabilito un nodo radice è possibile costruire delle relazioni di parentela tra nodi: il nodo radice non ha padre e può avere 0, 1 o 2 figli, ed ogni nodo è ovviamente padre dei suoi figli. Poiché tutti i nodi tranne la radice hanno un padre, per via della limitazione sul grado dei nodi ogni nodo può avere al massimo 2 figli da qui il nome "albero binario".

I nodi senza figli vengono detti foglie o nodi terminali; un nodo non foglia è un nodo interno.

                                     

1. Implementare gli alberi binari

In questa sezione trattiamo limplementazione 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 dellalbero secondo questa logica: la radice occupa la prima posizione dellarray e i figli di questa radice sono a loro volta nellarray 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 lalbero è completo cioè se tutti gli elementi che costituiscono lalbero 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 dellutilizzo 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.

Unaltra implementazione che prevede luso di array è quello della rappresentazione collegata con array, in cui, in una tabella a tre colonne abbiamo, rispettivamente per riga, in quella centrale il valore, in quella sinistra lindirizzo del figlio sinistro e in quella destra lindirizzo di quello destro. È necessario aggiungere una variabile inizio per indicare il punto in cui dobbiamo iniziare lanalisi, al contrario, se un indirizzo è a zero è da considerarsi NULL.

Iniziando da 1, ha figli che sono in 2 e 3, il figlio B non ha discendenti, quello C invece ha come discendenti 4 a sinistra e 5 a destra, cioè ed E.

Lo stesso risultato si può ottenere 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 allimmagine 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 così 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, laltezza misura la massima distanza di una foglia dalla radice dellalbero, in termini di numero di archi attraversati. Poiché la definizione di alberi si applica anche ai sotto alberi, è più efficiente e semplice trovare laltezza di un albero binario osservando che lalbero composto da un solo nodo ha altezza pari a 0, mentre un albero con almeno due nodi ha altezza pari allaltezza del suo sottoalbero più alto, incrementata di uno in quanto la radice introduce un ulteriore livello

Nel caso dellalbero nella figura qui sopra, laltezza h è 0foglie+1figli radice+1radice=2.

Esistono alcune formule per calcolare le caratteristiche degli alberi:

                                     

2. 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 n − 1 {\displaystyle 2^{n}-1} con n ∈ N {\displaystyle n\in \mathbb {N} }.

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

lo pseudo-algoritmo per la ricerca di una chiave è

Ricerca di una chiave N:= numero di elementi dellalbero 2^k-1 A:= array delle N chiavi ordinate in ordine crescente, A then i = i + jump endif jump = jump / 2 done nessun risultato

Suddetta modalità di visualizzazione di un albero binario sfrutta la definizione di skip-list, ossia di albero binario i cui elementi sono ordinati e si sfrutta una algoritmo randomizzato. In una skip list per cercare un elemento non facciamo altro che creare nuove liste a partire da quella di partenza L0, dimezzando ogni volta gli elementi seguendo la regola n/2^i=2, cioè sappiamo che possiamo creare Li liste fino a che non arriviamo alla lista con il minor numero di elementi, ossia 2. La skip list è molto utile se vogliamo trovare un elemento in quanto nella ricerca dobbiamo partire dalla lista Llgn e scendere cercando sempre il primo elemento più grande del valore cercato x; è un buon algoritmo anche se è costoso in termini di spazio, ma è più difficile aggiungere o cancellare un elemento.

                                     

3. Implementare gli alberi binari tramite puntatori

Un modo semplice per implementare gli alberi binari di ricerca è quello di usare i puntatori. Nellimplementazione classica ogni nodo dellalbero oltre al suo valore ha un puntatore al figlio destro ed uno al figlio sinistro, in questo modo è possibile, partendo dalla radice, discendere nellalbero fino ad arrivare alle foglie. Tutti i nodi sono uguali, lunica differenza è che nessun nodo punterà alla radice infatti la radice non è né un figlio destro, né un figlio sinistro, le foglie non avendo figli non punteranno a nulla nil, NULL value.

                                     

4. Algoritmi elementari su alberi binari

Determinazione della larghezza

La larghezza di un albero binario corrisponde al numero massimo di nodi giacenti al medesimo livello.

La determinazione di suddetta grandezza può essere ottenuta attraverso unopportuna modifica della Visita in-order: si fa uso di un vettore, dimensionato al pari del numero di nodi, inizialmente con valori tutti uguali a zero; la funzione WrapperLarghezza è deputata al passaggio corretto dei parametri alla funzione ricorsiva Larghezza, che ritorna il valore massimo contenuto nel vettore, cioè la larghezza dellalbero.