Albero binario: differenze tra le versioni

Versione delle 17:40, 31 mag 2006

Versione delle 00:55, 24 giu 2006

Riga 1:

Un albero binario è una [[struttura dati]] formata da nodi collegati tra loro da archi.

{{stub informatica}}

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.

Un '''albero binario''' è un [[albero_(informatica)|albero]] nel quale ogni nodo può avere al massimo due figli.

In questa [[Struttura dati|struttura di dati]] i figli di un nodo vengono chiamati ''figlio destro'' e ''figlio sinistro''. Esempi di alberi binari sono gli [[heap]] oppure gli [[Albero binario di ricerca|alberi binari di ricerca]].

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<br/>

2. I figli sono ordinati tra loro<br/>

3. Ogni figlio può essere radice di un nuovo albero<br/>

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.

[[Immagine:Mg744Albero1.PNG|center|200px]]

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]].

[[Immagine:Mg744Albero2.PNG|center|200px|]]

<div style="text-align:center;">'''Inizio = 1'''</div>

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à:

<div style="text-align:center;">'''''N=lunghezza del più lungo cammino + 1'''''</div>

Dove come cammino si intende il percorso misurato in nodi attraversati per raggiungere una posizione a partire dalla radice. <br/>Nel caso dell’albero nella figura qui sopra, l’altezza è 1+2 cioè 3.

Esistono alcune formule per calcolare le caratteristiche degli alberi:

<table><tr><td>

'''Log2(n+1)</'''td><td> Altezza di un albero pieno di n nodi<br/></td></tr>

<tr><td>'''2h-1'''</td><td> Numero massimo di nodi in un albero binario di altezza h<br/></td></tr>

<tr><td>'''h'''</td><td>Altezza o numero minimo di nodi di un albero con altezza h<br/></td></tr>

<tr><td>'''2*l'''</td><td>Numero massimo di nodi ad un livello l (elle)<br/></td></tr></table>

Ogni albero può essere trasformato in un albero binario applicando le seguenti regole:

1. La radice dell'albero rimane immutata;

2. Si eliminano i legami tra radici e nodi, figli diversi dal primogenito vengono posizionati sul lato destro mentre i primogeniti vengono posizionati sempre e soltanto sul lato sinistro;

3. Si collegano tra loro i nodi fratelli ognuno sottoalbero del fratello immediatamente maggiore.

[[Categoria:Strutture dati]]