Torna alla pagina di Algoritmi e strutture dati
:: Algoritmi e strutture dati - Specifiche ::
Alberi
Sintassi
- creabinalbero: () -> binalbero
Crea ed inizializza un albero binario vuoto.
- binalberovuoto: (binalbero) -> booleano
Restituisce vero o falso a seconda che l'albero binario sia vuoto o no.
- binradice: (binalbero) -> nodo
Accede direttamente alla radice.
- binpadre: (nodo, binalbero) -> nodo
Accede al padre di un nodo.
- cancsottobinalbero: (nodo, binalbero) -> binalbero
Cancella un sottoalbero binario.
- legginodo: (nodo, binalbero) -> tipoelem
Legge il valore contenuto in un nodo.
- scrivinodo: (tipoelem, nodo, binalbero) -> binalbero
Cambia il valore memorizzato in un nodo.
- figliosinistro: (nodo, binalbero) -> nodo
Accede al figlio sinistro di un nodo.
- figliodestro: (nodo, binalbero) -> nodo
Accede al figlio destro di un nodo.
- sinistrovuoto: (nodo, binalbero) -> booleano
Restituisce vero o falso a seconda che il nodo a sinistra sia vuoto o no.
- destrovuoto: (nodo, binalbero) -> booleano
Restituisce vero o falso a seconda che il nodo a destra sia vuoto o no.
- costrbinalbero: (binalbero, binalbero) -> binalbero
Crea un albero binario.
Semantica
- creabinalbero() = T'
Post: T' = Λ
- binalberovuoto(T) = b
Post: b = vero, se T = Λ; b = falso altrimenti
- binradice(T) = u
Pre: T ≠ Λ
Post: u = r
- binpadre(u,T) = v
Pre: T ≠ Λ, u nodo in T, u ≠ r
Post: u = r
- cancsottobinalbero(u, T) = T'
Pre: T ≠ Λ, U ≠ Λ, u nodo in T
Post: T' ottenuto da T eliminando sottoalbero binario di radice u; T = Λ se u = r
- legginodo(u, T) = a
Pre: T ≠ Λ, u nodo in T
Post: a è valore memorizzato in u
- scrivinodo(a, u, T) = T'
Pre: T ≠ Λ, u nodo in T
Post: T' è ottenuto da T scrivendo il valore a nel nodo u
- figliosinistro(u, T) = v
Pre: T ≠ Λ, u nodo in T, u ha un figlio sinistro
Post: v è il figlio sinistro di u in T
- figliodestro(u, T) = v
Pre: T ≠ Λ, u nodo in T, u ha un figlio destro
Post: v è il figlio destro di u in T
- sinistrovuoto(u, T) = b
Pre: T ≠ Λ, u nodo in T
Post: b = vero, se u non ha figlio sinistro; b = falso, altrimenti
- destrovuoto(u, T) = b
Pre: T ≠ Λ, u nodo in T
Post: b = vero, se u non ha figlio destro; b = falso, altrimenti
- costrbinalbero(T, U) = T'
Post: T' è ottenuto introducendo un nuovo nodo u, che diventa la radice di T' , che ha come sottoalbero sinistro T e come sottoalbero destro U:
- se T = Λ, u non fa figlio sx
- se U = Λ, u non fa figlio dx
Implementazione in C++
typedef struct _bincella {
tipoelem valore;
struct _bincella *sx, *dx, *padre;
} bincella;
typedef *bincella binalbero;
typedef *bincella nodo;
binalbero T;
- creabinalbero:
void creabinalbero (binalbero T) {
T = NULL;
}
- binalberovuoto:
void binalberovuoto (binalbero T) {
return (T == NULL);
}
- binradice:
void binradice (binalbero T) {
if (!binalberovuoto(T))
return (T);
}
- binpadre:
void binpadre (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->padre);
}
- figliosinistro:
void figliosinistro (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->sx);
}
- figliodestro:
void figliodestro (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->dx);
}
- sinistrovuoto:
void sinistrovuoto (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->sx == NULL);
}
- destrovuoto:
void destrovuoto (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->dx == NULL);
}
- costrbinalbero:
void costrbinalbero (binalbero T, binalbero U) {
nodo u;
u = malloc (sizeof(bincella));
u->padre = NULL;
u->sx = T;
u->dx = U;
if (!binalberovuoto(T))
T->padre = u;
if (!binalberovuoto(U))
U->padre = u;
return (u);
}
Binvisite
Ci sono tre tipi di visita, che corrispondono alle 3 corrispondenti visite degli alberi. Il codice delle 3 binvisite è lo stesso, cambia solo il punto in cui si esegue l'esame del nodo. La loro complessità è O(n). Questo sotto è rigorosamente pseudocodice. Si tratta di una funzione ricorsiva.
void binvisita (nodo u, binalbero T) {
// Qui ci va l'esame anticipato del nodo u per la previsita
if (!sinistrovuoto(u, T))
binvisita (figliosinistro(u, T), T);
// Qui ci va l'esame simmetrico del nodo per l'invisita
if (!destrovuoto(u, T))
binvisita(figliodestro(u, T), T);
// Qui ci va l'esame differito del nodo per la postvisita
}
Binvisite non ricorsive
È possibile anche visitare un albero binario tramite visite non ricorsive, cioè iterative, utilizzando la struttura dati pila che già dovremmo conoscere. In generale, è sempre possibile passare da una ricorsione ad un'iterazione con una pila, ed in effetti nei calcolatori le ricorsioni sono implementate tramite lo stack, che è una pila.
La differenza con la binvisita ricorsiva, oltre che nel sistema di visita, sta anche nel fatto che per le tre diverse visite ci sono tre diverse implementazioni.
Visita anticipata
Il sistema che si utilizza qui è quello di mettere il primo nodo nella pila, e finché la pila non è vuota, estrarne il primo elemento e, nell'ordine, infilare nella pila i suoi figli prima destro e poi sinistro. Perché prima il destro e poi il sinistro? Perché la pila è una struttura LIFO: l'ultimo che ho inserito sarà il primo ad uscire. Quindi, se voglio analizzare prima il figlio sinistro, deve essere l'ultimo a venir impilato.
void binvisitaIterativa (nodo u, binalbero T) {
nodo v;
creapila (P);
inpila (u, P);
while (!pilavuota(P)) {
//Le due righe seguenti estraggono il primo elemento della pila
v = leggipila (P);
fuoripila(P);
//Esame del nodo v testé estratto
if (!destrovuoto(v,T))
inpila (figliodestro(v,T), P);
if (!sinistrovuoto(v,T))
inpila (figliosinistro(v,T), P);
}
L'algoritmo è di complessità ottima O(n) perché esamina tutti i nodi una e una sola volta.
Visita differita
Il problema della visita differita è che devo analizzare i nodi a partire dall'ultimo. Come faccio con una pila? Come faccio a sapere quando ho finito i nodi? Il sistema adottato è quello di utilizzare 2 pile: una che si comporta come la pila dell'esercizio precedente: quando è vuota, vuol dire che ho terminato l'albero. L'altra pila invece viene riempita esattamente come la pila dell'esercizio precedente, ma a differenza di quella, non viene mai svuotata all'inizio del while. In sostanza, in questa seconda pila infiliamo tutti i valori dal primo all'ultimo, e in un secondo momento li estrarremo, trattandosi di una pila, dall'ultimo al primo.
void binvisitaIterativa (nodo u, binalbero T) {
nodo v;
creapila (P); //La pila per sapere quando ho finito i nodi
creapila (Q); //La pila per l'effettivo esame del nodo
inpila (u, P);
inpila (u, Q);
while (!pilavuota(P)) {
//Le due righe seguenti estraggono il primo elemento dalla
//pila P, ma NON dalla pila Q
v = leggipila (P);
fuoripila(P);
//Esame del nodo v testé estratto
if (!destrovuoto(v,T))
inpila (figliodestro(v,T), P);
inpila (figliodestro(v,T), Q); //Metto il nodo anche nell'altra pila
if (!sinistrovuoto(v,T))
inpila (figliosinistro(v,T), P);
inpila (figliosinistro(v,T), Q);
}
//OK: ora ho tutti i nodi belli e impilati in Q. Non ci resta che
//estrarli da Q uno alla volta ed esaminarli
while (!pilavuota(Q)) {
v = leggipila(Q);
fuoripila(Q);
//esame del nodo v;
}
}
La complessità di questo algoritmo è, parimenti, ottima, cioè O(n). Questo perché entrambi i while compiono l'operazione n volte. Quindi n + n = 2n, e l'asintoto è n => O(n).
Visita simmetrica
Ahi ahi, qui sono dolori. Innanzitutto definiamo che cos'è una visita simmetrica: supponendo un padre e due figli, la visita simmetrica esamina prima il figlio sinistro, poi il padre, infine il figlio destro. Se uno qualsiasi dei figli di questo padre è padre a sua volta, allora si esegue una visita simmetrica anche su di esso, il che vuol dire che esaminerò il suo figlio sx, poi lui, poi quello dx etc. etc. ricorsivamente.
Come uscire dalla ricorsione con la pila? Ebbene, qui sotto c'è la soluzione. Il ciclo termina quando una flag booleana viene impostata a vera, perché la pila può svuotarsi da un momento all'altro senza implicare che siano finiti i nodi da esaminare. Inoltre, assumiamo la realizzazione con puntatori padre e figlio. Quando un puntatore non punta a niente, il suo valore è NULL. Equivale a dire che non ha un figlio in quella posizione.
void binvisitaIterativa (nodo u, binalbero T) {
creapila(P);
boolean finito = false;
while (!false) {
if (u != null) {
inpila (u, P);
u = figliosinistro(u, T);
}
else
{
if (!pilavuota(P)) {
u = leggipila(P);
fuoripila(P);
//Esame del nodo
u = figliodx(u, T);
}
else fatto = true;
}
Ecco come funziona. u è il mio nodo, che viene passato come parametro alla funzione. Il primo controllo che si fa all'interno del while è che u esista: certo non è il caso iniziale, ma nel codice sottostante può accadere (ci arriviamo subito).
Se u esiste, lo inpilo, e vado al suo figlio sinistro (u ora punta al suo sinistro figlio). Vado avanti così finché trovo figli sinistri da impalare inpilare.
Nel caso che u non abbia un figlio sinistro, il suo puntatore sarebbe null, e quindi u stesso sarebbe null. Ecco quindi che la prima condizione (if (u != null) ...) si è verificata. In questo caso, finché la pila non è vuota, estraggo l'ultimo elemento, lo esamino, e vado al suo figlio destro, e ritorno da capo. Qui sta il nocciolo: ho messo in pila u. Non ha figli sinistri, quindi l'ultimo nodo nella pila è lui. Lo esamino, lo tolgo dalla pila e vado al figlio destro. Se il figlio destro esiste, sarà inpilato ed esaminato, altrimenti sarà estratto dalla pila, esaminato, e si ritornerà al nodo di lui padre. Fate uno schemino a mano e vedrete che sarà più chiaro:)
Quando arriverò ad avere u = null e la pila vuota, uscirò dal ciclo.
Ad occhio e croce, l'algoritmo é ottimo perchè visita tutti i nodi una e una sola volta: O(n).
Torna alla pagina di Algoritmi e strutture dati
