|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.AlSp-AlberiBinari History
Show minor edits - Show changes to output
Changed lines 175-177 from:
!!!Visite
Ci sono tre tipi di visita, che corrispondono alle 3 corrispondenti visite degli alberi. Il codice è ''lo stesso'', cambia solo il punto in cui si esegui l'esame del nodo. La loro complessità è O(n). Questo sotto è rigorosamente pseudocodice. Si tratta di una funzione ricorsiva. to:
!!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.
Changed lines 300-301 from:
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, quindo to:
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:) Changed lines 304-306 from:
to:
Ad occhio e croce, l'algoritmo é ottimo perchè visita tutti i nodi una e una sola volta: O(n).
Added lines 175-306:
!!!Visite
Ci sono tre tipi di visita, che corrispondono alle 3 corrispondenti visite degli alberi. Il codice è ''lo stesso'', cambia solo il punto in cui si esegui 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, quindo
Quando arriverò ad avere '''u''' = '''null''' e la pila vuota, uscirò dal ciclo.
Deleted lines 4-7:
(:include Servizi.DaModificare:)
->[[!'''DaModificare''']]: ''Da aggiungere le realizzazioni''
Changed lines 80-178 from:
to:
!!!Implementazione in C++
[@
typedef struct _bincella {
tipoelem valore;
struct _bincella *sx, *dx, *padre;
} bincella;
typedef *bincella binalbero;
typedef *bincella nodo;
binalbero T;@]
* %color=#4169E1%'''creabinalbero''': \\
[@
void creabinalbero (binalbero T) {
T = NULL;
}
@]
* %color=#4169E1%'''binalberovuoto''': \\
[@
void binalberovuoto (binalbero T) {
return (T == NULL);
}
@]
* %color=#4169E1%'''binradice''': \\
[@
void binradice (binalbero T) {
if (!binalberovuoto(T))
return (T);
}
@]
* %color=#4169E1%'''binpadre''': \\
[@
void binpadre (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->padre);
}
@]
* %color=#4169E1%'''figliosinistro''': \\
[@
void figliosinistro (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->sx);
}
@]
* %color=#4169E1%'''figliodestro''': \\
[@
void figliodestro (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->dx);
}
@]
* %color=#4169E1%'''sinistrovuoto''': \\
[@
void sinistrovuoto (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->sx == NULL);
}
@]
* %color=#4169E1%'''destrovuoto''': \\
[@
void destrovuoto (nodo u, binalbero T) {
if (!binalberovuoto(T))
return (u->dx == NULL);
}
@]
* %color=#4169E1%'''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);
}
@]
Changed lines 7-8 from:
->[[!'''DaModificare''']]: ''Da completare sintassi, semantica e aggiungere le realizzazioni'' to:
->[[!'''DaModificare''']]: ''Da aggiungere le realizzazioni'' Changed lines 36-37 from:
''Restituisce vero o falso a seconda che l'albero binario sia vuoto o no.'' to:
''Restituisce vero o falso a seconda che il nodo a sinistra sia vuoto o no.''
* '''destrovuoto: %color=#4169E1%(nodo, binalbero) -> booleano'''\\
''Restituisce vero o falso a seconda che il nodo a destra sia vuoto o no.''
* '''costrbinalbero: %color=#4169E1%(binalbero, binalbero) -> binalbero'''\\
''Crea un albero binario.'' Changed lines 63-65 from:
to:
* %color=#4169E1%'''figliosinistro(''u'', ''T'') = ''v'' '''%%\\
'''Pre:''' ''T'' ≠ Λ, ''u'' nodo in ''T'', ''u'' ha un figlio sinistro\\
'''Post:''' ''v'' è il figlio sinistro di ''u'' in ''T''
* %color=#4169E1%'''figliodestro(''u'', ''T'') = ''v'' '''%%\\
'''Pre:''' ''T'' ≠ Λ, ''u'' nodo in ''T'', ''u'' ha un figlio destro\\
'''Post:''' ''v'' è il figlio destro di ''u'' in ''T''
* %color=#4169E1%'''sinistrovuoto(''u'', ''T'') = b '''%%\\
'''Pre:''' ''T'' ≠ Λ, ''u'' nodo in ''T''\\
'''Post:''' b = vero, se ''u'' non ha figlio sinistro; b = falso, altrimenti
* %color=#4169E1%'''destrovuoto(''u'', ''T'') = b '''%%\\
'''Pre:''' ''T'' ≠ Λ, ''u'' nodo in ''T''\\
'''Post:''' b = vero, se ''u'' non ha figlio destro; b = falso, altrimenti
* %color=#4169E1%'''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
Added lines 1-63:
(:title Algoritmi e strutture dati - Specifiche: Alberi binari:)
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
----
(:include Servizi.DaModificare:)
->[[!'''DaModificare''']]: ''Da completare sintassi, semantica e aggiungere le realizzazioni''
%titolo%''':: Algoritmi e strutture dati - Specifiche ::'''
%center%%bgcolor=#d9e4f2 font-size=11pt padding=4px padding-left=50px padding-right=50px%Alberi
----
!!!Sintassi
* '''creabinalbero: %color=#4169E1%() -> binalbero'''\\
''Crea ed inizializza un albero binario vuoto.''
* '''binalberovuoto: %color=#4169E1%(binalbero) -> booleano'''\\
''Restituisce vero o falso a seconda che l'albero binario sia vuoto o no.''
* '''binradice: %color=#4169E1%(binalbero) -> nodo'''\\
''Accede direttamente alla radice.''
* '''binpadre: %color=#4169E1%(nodo, binalbero) -> nodo'''\\
''Accede al padre di un nodo.''
* '''cancsottobinalbero: %color=#4169E1%(nodo, binalbero) -> binalbero'''\\
''Cancella un sottoalbero binario.''
* '''legginodo: %color=#4169E1%(nodo, binalbero) -> tipoelem'''\\
''Legge il valore contenuto in un nodo.''
* '''scrivinodo: %color=#4169E1%(tipoelem, nodo, binalbero) -> binalbero'''\\
''Cambia il valore memorizzato in un nodo.''
* '''figliosinistro: %color=#4169E1%(nodo, binalbero) -> nodo'''\\
''Accede al figlio sinistro di un nodo.''
* '''figliodestro: %color=#4169E1%(nodo, binalbero) -> nodo'''\\
''Accede al figlio destro di un nodo.''
* '''sinistrovuoto: %color=#4169E1%(nodo, binalbero) -> booleano'''\\
''Restituisce vero o falso a seconda che l'albero binario sia vuoto o no.''
!!!Semantica
* %color=#4169E1%'''creabinalbero() = ''T' '' '''%%\\
'''Post:''' T' = Λ
* %color=#4169E1%'''binalberovuoto(''T'') = b'''%%\\
'''Post:''' b = vero, se T = Λ; b = falso altrimenti
* %color=#4169E1%'''binradice(''T'') = ''u'' '''%%\\
'''Pre:''' T ≠ Λ\\
'''Post:''' ''u'' = ''r''
* %color=#4169E1%'''binpadre(''u'',''T'') = ''v'' '''%%\\
'''Pre:''' T ≠ Λ, ''u'' nodo in ''T'', ''u'' ≠ ''r''\\
'''Post:''' ''u'' = ''r''
* %color=#4169E1%'''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''
* %color=#4169E1%'''legginodo(''u'', ''T'') = ''a'' '''%%\\
'''Pre:''' ''T'' ≠ Λ, ''u'' nodo in ''T''\\
'''Post:''' ''a'' è valore memorizzato in ''u''
* %color=#4169E1%'''scrivinodo(''a'', ''u'', ''T'') = ''T' '' '''%%\\
'''Pre:''' ''T'' ≠ Λ, ''u'' nodo in ''T''\\
'''Post:''' ''T' '' è ottenuto da ''T'' scrivendo il valore ''a'' nel nodo ''u''
----
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
|
|
