Gli alberi strutture Dati Astratte alberi Generali



Scaricare 166.93 Kb.
Pagina2/3
17.11.2017
Dimensione del file166.93 Kb.
1   2   3

AritmNode = record


Nlabel: char;

Nvalue: integer;

LeftD, RightD: AritmPointer

end;


Ora, scrivere la procedura per la valutazione dell’espressione è proprio facile: per ogni nodo (partendo dalla radice), si verifica il ‘tipo’; se si tratta di un’operazione, la si esegue; se si tratta di un valore (una foglia) si prende il valore. Ovviamente, per eseguire un’operazione sarà necessario conoscere il valore dei suoi operandi; ma questi si ottengono valutando l’espressione associata al sottoalbero, e cioè con due chiamate ricorsive (una per il primo operando, sottoalbero sinistro, una per il secondo operando, sottoalbero destro) alla stessa funzione (che chiamerò aritmEval:
function aritmEval (root: AritmPointer): integer;

begin


case root^.Nlabel of

‘+’: aritmEval := aritmEval (root^.LeftD) + aritmEval (root^.Rightd)

‘-’: aritmEval := aritmEval (root^.LeftD) - aritmEval (root^.Rightd)

‘*’: aritmEval := aritmEval (root^.LeftD) * aritmEval (root^.Rightd)

‘/’: aritmEval := aritmEval (root^.LeftD) / aritmEval (root^.Rightd)

‘v’: aritmEval := root^.Nvalue

end;
Proc.3 – Valutazione di un’espressione aritmetica rappresentata come albero binario

Si osservi solo che, per i nodi intermedi, il campo Nvalue non è utilizzato. Volendo, è possibile (con semplici modifiche alla procedura) memorizzare in esso i risultati (parziali) del calcolo delle sottoespressioni.



3.5 Un esempio: altezza di un nodo
Un utile esercizio, che ci permette di confrontare le operazioni sugli alberi binari con quelle sugli alberi generali, è quello del calcolo dell’altezza di un nodo. Definiamo per altezza del nodo n, la massima distanza di n da una foglia. Più precisamente:

  • Se n è una foglia, allora altezza(n)=0

  • Se n non è una foglia, allora altezza(n)=Max(altezza dei suoi figli)+1

Cominciamo a vedere come questa definizione può essere realizzata su alberi binari. La cosa più interessante della procedura che segue, è che essa ricalca esattamente la definizione data!
function height (node: BinaryNodePointer): integer;

begin


if (node^.LeftD = NIL) and (node^.RightD = NIL)

then height := 0

else if node^.LeftD = NIL

then height := height (node^.RightD) + 1

else if node^.RightD = NIL

then height := height (node^.RightD) + 1

else height := max (height (node^.LeftD),

height (node^.RightD)) + 1

end;
Proc.4 – Altezza di un nodo in un albero binario (versione 1)

L’unica differenza, rispetto alla definizione, è che, per trovare il massimo dell’altezza dei figli, si devono trattare separatamente i casi in cui uno dei due figli è NIL (cioè, manca). Un’alternativa, un pò più elegante, è la seguente:

function height2 (node: BinaryNodePointer): integer;

begin


if node = NIL

then height2 := -1

else height2 := max (height2 (node^.LeftD), height (node^.RightD)) + 1

end;
Proc.5 – Altezza di un nodo in un albero binario (versione 2)


La differenza, rispetto alla versione precedente, e che qui non si termina la ricorsione sulle foglie, ma si scende di un livello in più, andando a considerare i figli NIL (cioè assenti). La cosa interessante è che questo si applica sia alle foglie (in cui ambedue i figli sono NIL) sia ai nodi con un solo figlio (destro o sinistro). Nel caso di una foglia, noi vogliamo che la sua altezza sia 0, per cui, visto che la definizione richiede che l’altezza di un nodo sia pari all’altezza massima dei suoi figli incrementata di 1, sarà necessario che l’altezza che si ottiene da un puntatore NIL sia –1. In questo modo, per le foglie, si ha che l’altezza di ambedue i figli (NIL) è –1, il massimo è quindi –1, e il massimo incrementato di 1 è 0 (come desiderato). Nel caso in cui uno solo dei due figli sia NIL, il valore dell’altezza è determinato dall’altro figlio, per cui il valore –1 non ha alcun effetto (l’altezza di un qualunque nodo è maggiore di –1).


Per calcolare l’altezza di un nodo in un albero generale, il procedimento è sempre lo stesso, ma con una piccola estensione per tener conto che un nodo può avere da 0 a un certo massimo3 (io userò 10) di figli. Poiché in un albero generale non si sa quanti sono i figli, è necessario un ciclo che operi sui figli (che ripeterà il body tante volte quanti sono i figli. Quindi, per spostarsi sulla successione dei figli di un nodo, si userà un procedimento iterativo (ciclo while, appunto). Per quanto riguarda la discesa sull’albero, al contrario, valgono le considerazioni che avevamo fatto per la procedura preorder e cioè che è necessario mantenere sullo stack le informazioni locali relative alle diverse chiamate. Ma c’è qualcuno che già fa questo per noi, e cioè il meccanismo di gestione delle chiamate di procedura, che inserisce un blocco sullo stack per ogni chiamata (e cioè, per ogni livello dell’albero, come desiderato). La struttura complessiva della procedura è quindi molto simile a quella che avevamo già visto per preorder.
function height3 (node: TreePointer): integer;

var tempheight: integer;

begin

if node = NIL



then height3 := -1

else


begin

tempheight := -1;

i := 1;

while (i<= MaxDaughters) and (node^.Daughters[i] <> NIL) do



begin

tempheight := max (tempheight, height3 (node^.Daughters[i]);

i := i+1

end


height3 := tempheight + 1

end


end;
Proc.6 – Altezza di un nodo in un albero rappresentato tramite array di puntatori

Penso sia utile confrontare questa versione con l’ultima versione vista per gli alberi binari. La differenza principale qui, come è ovvio, è che al posto della semplice operazione


height2 := max (height2 (node^.LeftD), height (node^.RightD)) + 1
è necessaria l’introduzione del ciclo while. Per rendersi conto meglio dell’analogia, osservate che l’operazione riportata qui sopra è equivalente a:
tempheight := -1;

tempheight := max (tempheight, height2 (node^.LeftD));

tempheight := max (tempheight, height2 (node^.RightD));

height2 := tempheight + 1


Il che è praticamente identico allo sviluppo della while del programma per alberi generali, nel caso in cui si eseguano solo due cicli. Si noti, comunque, che la seconda condizione della while (e cioè node^.Daughters[i] <> NIL) potrebbe anche essere omessa; l’unica differenza sarebbe che viene effettuata la chiamata ricorsiva su tutti i 10 puntatori, anche quelli a NIL che non corrispondono a nessun figlio. Ma visto che per essi il valore ottenuto è –1, questo non provoca problemi. Naturalmente, questo è molto inefficiente, perché bisogna effettuare una chiamata ricorsiva in più, anche per tutti i figli inesistenti (con relativa allocazione-deallocazione di un blocco sullo stack).

3.6 Alberi generali rappresentati mediante alberi binari
Dobbiamo ora ritornare al paragrafo 3.3, in cui abbiamo scelto di rappresentare gli alberi generali come array di puntatori. Allora, si era sottolineato come questa soluzione soffrisse di tutti i problemi legati alla rappresentazione di sequenze tramite vettori: limite sul numero massimo di elementi e spreco di spazio. Ora, è il caso di chiedersi se, anziché un vettore di puntatori, non sia possibile usare una lista di puntatori (esattamente come avevamo fatto nel caso delle sequenze di interi, mentre si trattava il problema dell’ordinamento).
Naturalmente, questa soluzione è possibile (i vettori possono essere sempre sostituiti da liste). Il nostro albero di esempio (vedi le figure 1 e 2) risulta, con le liste di puntatori, rappresentato come si vede nella figura che segue.

Figura 3 – Sequenza dei puntatori ai figli realizzata come lista di puntatori

Come si vede dalla figura, ci sono due tipi di puntatori: quelli che puntano a dei nodi (con l’etichetta) e quelli che puntano a ‘coppie di puntatori’. Questo è naturale: i primi sono i nostri vecchi puntatori dell’albero, i secondi sono dei puntatori che ci servono a rappresentare la sequenza di (puntatori ai) figli come lista. Questo metodo di rappresentazione può essere ‘dichiarato’ in Pascal nel modo seguente:


Type ToNodePointer = ^TreeNode;

PointerListPointer = ^PointerNode;

TreeNode = record

NodeData: TipoDato;

FirstDaughter: PointerListPointer

end;


PointerNode = record

Daughter: ToNodePointer;

NextDaughter: PointerListPointer

end;
Si può osservare che il tipo PointerNode prevede una coppia di puntatori (anche se di tipo diverso). Il primo di essi (di tipo ToNodePointer) è in realtà un ‘dato’ (come gli interi del nostro esempio di sort), mentre il secondo è il vero ‘puntatore al prossimo elemento’. Notate infine che il ‘puntatore all’inizio della lista (dei figli)’ non è memorizzato in una variabile del main o della procedura, ma dentro i record stessi (e cioè nello Heap); in particolare, nei record di tipo TreeNode.


Sebbene questa rappresentazione risolva i problemi visti per i vettori (ci sono solo tanti puntatori quanti servono e non ce n’è un numero massimo), forse si può fare meglio! Se guardate bene la figura, vedete che, per ogni nodo di tipo ToNodePointer c’è un corrispondente nodo di tipo TreeNode, e viceversa. In altre parole, c’è un accoppiamento rigido (una relazione 1 a 1) tra nodi ToNodePointer e nodi TreePointer. E inoltre, per arrivare al primo figlio di un nodo, bisogna fare un doppio passaggio: prima si deve passare per il nodo ‘coppia di puntatori’ e poi, da esso, si può arrivare al vero ‘nodo che contiene i dati’.
Perché, allora, non fondere in un unico nodo ogni ToNodePointer con il TreeNode ad esso associato? Se facciamo questa operazione, otteniamo la seguente rappresentazione:



Figura 4 – Un albero generale rappresentato come albero binario (a parte la radice)

Beh, questa realizzazione sembra molto più semplice della precedente. Qui abbiamo che ogni nodo ha due puntatori; il primo di essi punta al primo figlio (se c’è), mentre il secondo punta al fratello successivo (se c’è). L’unico problema è quello della radice, che ha un solo puntatore; questo dipende dal fatto che la radice non può avere un ‘fratello successivo’. Ma noi possiamo lo stesso mettere nel record questo puntatore (per avere un nodo fatto come tutti gli altri), anche se esso sarà sempre NIL.
A questo punto, il tipo Pascal per questa rappresentazione può essere come segue:
Type NodePointer = ^TreeNode;

TreeNode = record

NodeData: TipoDato;

FirstDaughter: NodePointer;

NextSister: NodePointer

end;
Ma questi tipi assomigliano (anzi sono esattamente uguali) a quelli che avevamo visto per gli alberi binari! Quindi, quello che abbiamo ottenuto è un albero binario! Ma a questo siamo arrivati per rappresentare un albero generale. Di conseguenza, quella che abbiamo trovato è una rappresentazione di alberi generali fatta mediante alberi binari. Ripeto, perché è importante: la struttura dati astratta è l’albero generale, mentre l’implementazione (struttura dati concreta) è quella di un albero binario.


Per comprendere meglio questa differenza, riprendiamo il problema di determinare l’altezza di un nodo. Ridisegniamo però, prima, l’albero binario di Fig.4 nel nostro solito formato ‘leggibile’.

Ora, qual è l’altezza della radice di quest’albero? Facile! Guardando la figura, si vede subito che l’altezza è 5! Facile, ma sbagliato. Se questo albero è solo un’implementazione diversa del nostro vecchio albero delle figure precedenti, allora l’altezza che vogliamo è quella della radice di quell’albero, e cioè 2. Il motivo dell’errore è semplice: muoversi verso il sottoalbero destro non deve far aumentare l’altezza! Infatti, ci stiamo solo spostando tra ‘fratelli’, che hanno tutti la stessa altezza. Proviamo allora a scrivere una procedura che ci permetta di calcolare l’altezza ‘giusta’ (ovviamente, possiamo far ‘girare’ il programma che calcola l’altezza di un nodo negli alberi binari sull’albero dell’esempio, ma in questo caso otterremo, appunto, il risultato ‘sbagliato’, cioè 5).


Per ottenere l’altezza di un albero generale rappresentato come albero binario, scriviamo, come al solito, una procedura iterativa in ampiezza e ricorsiva in profondità. Naturalmente, in questo caso, l’iterazione in ampiezza comporta non un ciclo su un vettore, ma un ciclo su una lista. E quindi il ciclo terminerà quando si sarà raggiunta la fine della lista (NextDaughter=NIL).

function height4 (node: TreePointer): integer;

var tempheight: integer;

begin


if node = NIL

then height4 := -1

else

begin


tempheight := -1;

nextDaughter := node^.FirstDaughter;

while nextDaughter <> NIL do

begin


tempheight := max (tempheight, height4 (nextDaughter));

nextDaughter := nextDaughter^.NextSister

end;

height4 := tempheight + 1



end

end;
Proc.7 – Altezza di un nodo di un albero generale rappresentato come albero binario


Come si può vedere, questa procedura corrisponde esattamente alla Proc.6 (Altezza di un albero rappresentato come array di puntatori). La differenza che può essere difficile da comprendere è quella relativa all’inizializzazione del ciclo while. Nel caso di Proc.6, era sufficiente porre i:=1 (che vuol dire posizionarsi sul primo figlio); qui, per posizionarsi sul primo figlio, è necessario scendere sul sottoalbero sinistro; infatti nextDaughter, che ha la funzione di variabile di ciclo, viene inizializzata a node^.FirstDaughter.

3.7 Lettura di un albero da file
In quest’ultimo paragrafo riporto un programma completo per leggere un albero da un file e stamparlo in preordine. Ricordo che sto parlando di un file solo perché i dati, se memorizzati in un file, saranno disponibili per diverse prove (i programmi raramente funzionano al primo colpo). Lo stesso input può essere anche dato, volendo, da tastiera; si riveda la discussione sui files nel primo capitolo di queste dispense.
Il primo problema da affrontare è relativo al modo in cui dare l’albero in input. Ovviamente, non possiamo usare puntatori: i puntatori non si possono leggere né stampare, visto che sono oggetti interni (indirizzi sullo heap). Ma tutte le rappresentazioni che abbiamo usato coinvolgono dei puntatori! L’unica alternativa è quella di ritornare alle nostre definizioni della struttura dati astratta ‘albero’. Possiamo liberamente scegliere una qualunque delle due; io sceglierò la seconda (con alcune modifiche).
Ricordo (si veda il §3.2) che un albero può essere definito come una coppia il cui primo elemento è un insieme di nodi e il secondo è un insieme di archi. Per prima cosa, io non userò il primo elemento: in input verranno dati solo gli archi, assumendo che in questo modo i nodi siano (implicitamente) definiti. Ciascun arco verrà descritto come una coppia .
Per una questione di semplicità, assumerò inoltre che l’albero venga costruito, un arco alla volta, partendo dalla radice. Questo vuol dire che, ogni volta che viene letto un arco, verrà aggiunto un nuovo nodo, figlio di un nodo già presente. In altre parole, non deve essere possibile introdurre un nodo intermedio nell’albero che si sta costruendo, ma vengono aggiunte solo foglie (che magari non saranno foglie alla fine, poiché ad esse potranno essere aggiunti, in seguito, dei figli). Questo perché l’aggiunta di una foglia è un’operazione molto semplice, mentre l’aggiunta di un nodo intermedio è un po’ più complicata.
Questa strategia è abbastanza naturale, ma ha due conseguenze:

  1. Non possiamo applicare la definizione di radice. Tale definizione, infatti, richiede di avere a disposizione tutti gli archi, per verificare quale nodo non compare mai come secondo elemento (cioè non è figlio di nessun altro nodo). Quando si legge un arco, invece, non si sa ancora come saranno gli altri archi che seguono.

  2. Ogni volta che si introduce un arco, il genitore (primo elemento della coppia) deve già essere presente nell’albero.

Poiché l’albero deve crescere dall’alto verso il basso, il primo nodo da introdurre deve essere la radice. Ma noi non possiamo introdurre nodi, ma soltanto archi. Per risolvere il problema, inventiamoci un arco fittizio; diciamo che c’è un nodo (fasullo) che sta sopra la radice e identifichiamolo con un simbolo speciale (ad esempio *).


A questo punto, l’algoritmo di lettura è abbastanza semplice:

 Per ogni arco:



  • se il primo elemento è *, allora si tratta della radice

  • altrimenti, cerca nell’albero costruito finora il primo elemento (il genitore) e inserisci il secondo elemento come suo figlio

Si possono però verificare alcuni errori (se i dati nel file non sono stati messi come previsto):



  1. Può esserci più di una coppia il cui primo elemento è * (più di una radice)

  2. Il primo elemento della coppia (diverso da *) non c’è nell’albero (si sta cercando di introdurre un figlio senza aver ancora introdotto il genitore)

  3. Si cerca di introdurre un figlio per un genitore che ha già raggiunto il numero massimo di figli (questo è un problema della rappresentazione con array di puntatori)

Per questo motivo, sembra ragionevole introdurre un meccanismo di segnalazione degli errori: se si verifica uno di questi errori, dovrà comparire a video una scritta che descriva il tipo di errore.
Possiamo ora vedere il programma; dobbiamo però ancora decidere come sono fatti i ‘dati’, e cioè le etichette dell’albero. Questa volta, userò come dato un carattere (tipo char). C’è però ancora un problema: cosa succede se introduciamo due volte lo stesso carattere? Questo è un problema interessante che richiede due parole di spiegazione (il problema non dipende dal fatto che io abbia scelto un carattere, con gli interi sarebbe stato lo stesso)4. Spesso si tende a confondere un nodo con la sua etichetta (il dato che esso contiene). Ma le due cose sono completamente diverse! Nella definizione di albero si dice che un albero è un insieme di ‘nodi’, non di ‘etichette di nodi’ (o ‘nomi di nodi’). Poiché si parla di un insieme, i nodi devono essere diversi: in un insieme non ci sono elementi uguali. Ma nulla esclude che due elementi distinti abbiano etichette (o in generale, dati) uguali. E’ chiaro che un insieme di persone può anche includere due persone (diverse) con lo stesso nome. A questo punto, ci si può chiedere: ma allora come facciamo a distinguere due elementi che hanno gli stessi dati? Da un punto di vista applicativo, questo è un problema serio (non per niente sono stati inventati i codici fiscali), che non è il caso di approfondire qui. Ma nel nostro piccolo (la lettura dell’albero) si possono fare due osservazioni interessanti. Due ‘nodi’ con la stessa etichetta sono diversi perché sono memorizzati in due record diversi! E cioè ci saranno celle diverse nello heap che contengono lo stesso dato. Ma il fatto che i record siano diversi non vuol dire che noi siamo in grado di trovare quello giusto! Supponiamo infatti di aver introdotto due coppie e . Fin qui, nulla di male. Ma se ora introduciamo la coppia , sotto quale dei due ‘z’ dovrà essere introdotto ‘c’? Non c’è nulla da fare: non abbiamo modo per distinguerli! Ci manca un identificatore univoco (appunto, un ‘codice fiscale’ dei nostri nodi)! Io non mi preoccuperò di questo problema nel programma che segue. Un modo possibile per risolverlo è quello di imporre che non possano esserci due nodi con la stessa etichetta (cosicchè l’etichetta è l’identificatore univoco): questo controllo non è fatto nel programma, ma non è difficile aggiungerlo. Di conseguenza, quello che succederà nel programma nella situazione descritta sopra (inserimento di , e ) è che ‘c’ verrà inserito come figlio sotto il primo ‘z’ che si trova. Poiché la procedura di ricerca del genitore è sempre la stessa, ogni figlio di ‘z’ andrà sempre sotto lo stesso ‘z’. L’altro, poverino, rimarrà per sempre senza figli!
Possiamo ora vedere il programma.
Ho assunto che ogni nodo possa avere al massimo 10 figli (maxDaughters). Per quanto riguarda gli errori, ho introdotto un tipo ‘nuovo’, il cosiddetto tipo enumerato.

I tipi enumerati
Come sappiamo, in Pascal ci sono tre classi di tipi: quelli semplici (es. Integer) e quelli strutturati (es. array) e i puntatori. I tipi semplici, a loro volta, si suddividono in Ordinali e Reali. Gli ordinali, infine, possono essere predefiniti (e questi sono 3: Integer, Boolean e Char), enumerati e subrange. Dirò qui due parole sui tipi enumerati.
Un tipo enumerato specifica un elenco ordinato di valori, a scelta di chi definisce il tipo. Questo viene fatto semplicemente indicando i valori voluti tra parentesi tonde:
type giorno = (lun, mar, mer, gio, ven, sab, dom);

type sesso = (mas, fem);
E’ importante osservare che i valori che vengono specificati per il tipo non sono stringhe (cioè array di Char), né nomi di variabili, ma sono delle costanti come ad esempio 127 (un intero) o false (un booleano). In particolare, Pascal prevede di essere in grado di stabilire sempre il tipo, quando trova una costante in un programma, per cui se aggiungiamo alle dichiarazioni sopra:
type vacanza = (mon, mar, cam, via);
che starebbero per ‘montagna’, ‘mare’, ‘campagna’, ‘viaggio’, si verifica un errore, perché mar è una costante ambigua (è sia un giorno che una vacanza). Inoltre, il tipo è definito tramite un elenco ordinato (infatti numerali fanno parte dei tipi ordinali). In altre parole, l’ordine con cui vengono specificati i valori è rilevante. Ad esempio,

lun < mer vale true (è vero)

mentre


fem < mas vale false (è falso)
Ovviamente, come per tutti i tipi, si possono definire variabili di un tipo enumerato:

var oggi, domani: giorno;

sessoDelProprietario: sesso;

e operare su di esse in modo standard:



oggi := dom;

sessoDelProprietario := fem;

Non solo, ma grazie alla presenza di un ordinamento si possono fare cose un po’ più ‘singolari’ (a prima vista):



for oggi := lun to ven

stampaOreLezione (oggi);

Oppure


if oggi > ven then writeln (‘Finalmente!!!’);

Infine, è possibile usare un tipo enumerato come indice di array:


type CoppiaOre = record

ore, minuti: integer

end;

type orario = array [lun..ven] of CoppiaOre;
Per cui sarà poi possibile riferirsi all’orario del giovedì con:

orario[gio]

Ma c’è anche qualcosa di utile che NON si può fare; in particolare, non è possibile leggere o stampare un valore di un tipo enumerato:



readln (domani); è sbagliato!

Per concludere, menzionerò l’esistenza di procedure predefinite che operano su tipi enumerati; in particolare:



succ(x), prec(x) e ord(x) (successore, predecessore e numero d’ordine)

ad esempio, se oggivale mer:



1   2   3


©astratto.info 2017
invia messaggio

    Pagina principale