Albero binario: differenze tra le versioni

Versione delle 00:55, 24 giu 2006

Versione delle 00:58, 24 giu 2006

Riga 11:

==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’arraynell’[[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 tagflag [[booleano]], in realtà un array di accompagnamento, che ci indica se la posizione è valida o meno.

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

Riga 21:

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.