HomeWork4 < Architetture2/MZ/AA15

---+++ Homework 4 - Manipolazione di un albero binario 

__DEFINITIVO__

Per rappresentare un albero binario con *M* nodi si può usare un vettore di *N&gt;M* elementi in cui:
   * *nodi pieni:* ciascun elemento positivo del vettore è uno dei nodi dell'albero (se raggiungibile dalla radice)
   * *nodi vuoti:* tutti gli elementi negativi o nulli indicano spazio libero per l'inserimento di nuovi valori
   * la radice dell'albero si trova nella posizione *1* (per rendere più semplice il calcolo della posizione dei figli)
   * il numero *M* di elementi inseribili nel del vettore (pieni o vuoti che siano, compresa la pos 0) è memorizzato nell'elemento di indice *0*
   * dati un qualsiasi nodo in posizione *1 &le; X &lt; N* i due figli, se esistono, si trovano nelle posizioni:
      * figlio sinistro: *2X*
      * figlio destro:   *2X+1*
   * *foglie*:
      * tutti gli elementi con indice *X>N/2*  sono foglie perchè i due figli si trovano oltre la posizione N-1
      * inoltre un elemento è foglia se *entrambi* i due figli sono vuoti

Esempio: se il vettore contiene gli *M=15* valori (di cui il primo è M=15):
   * 15 1 2 3 4 5 -6 7 8 9 10 -1 -2 -3 14
corrisponderà all'albero (in cui ho evidenziato i nodi vuoti con valori negativi)
<verbatim>
          1
        /   \
      /       \
    2           3
   / \        /   \
 4    5      -6    7
/ \  / \    / \   / 
8 9 10 -1 -2  -3 14
</verbatim>

I nodi di questo albero possono essere univocamente individuati indicando il *percorso* (sinistra destra stop) che porta dalla radice al nodo desiderato.
   * il *percorso* è codificato in un intero che va interpretato come numero binario
   * iniziando _dal bit meno significativo_ del *percorso* ogni *0* indica svolta a *destra* ed ogni *1* svolta a *sinistra*
   * non appena si arriva al bit 1 più significativo ci si ferma e si torna il valore del nodo individuato
   * tranne nel caso in cui se uno dei nodi esplorati era vuoto e allora si torna *0*
   * quindi per estrarre la radice si usa il valore 1 (nessuna svolta visto che siamo già al bit più significativo)

*Esempio:* (rispetto all'albero precedente) 
| *Percorso* | *in binario* | *mosse* | *nodo* | *note* |
|   1 |     1 | stop  |                             1 | radice |
|   2 |    10 | destra   stop  |                    3 | |
|   3 |    11 | sinistra stop  |                    2 | |
|   4 |   100 | destra   destra   stop  |           7 | |
|   5 |   101 | sinistra destra   stop  |           5 | |
|   6 |   110 | destra   sinistra stop  |           0 | -6 è vuoto |
|   7 |   111 | sinistra sinistra stop  |           4 | |
|   8 |  1000 | destra   destra   destra   stop  |  0 | il figlio destro di 7 ha indice &gt; 14 |
|   9 |  1001 | sinistra destra   destra   stop  |  0 | -1 è vuoto |
|  10 |  1010 | destra   sinistra destra   stop  |  0 | si passa per -6 che è vuoto |
|  11 |  1011 | sinistra sinistra destra   stop  |  9 | |
|  12 |  1100 | destra   destra   sinistra stop  |  14 | |
|  13 |  1101 | sinistra destra   sinistra stop  |  10 | |
|  14 |  1110 | destra   sinistra sinistra stop  |  0 | si passa per -6 che è vuoto |
|  15 |  1111 | sinistra sinistra sinistra stop  |  8 | |


Per gestire l'albero si devono realizzare le funzioni:
   * *NUOVOALBERO(N)* che riceve come argomento il numero *N &le; 1000* di elementi che è possibile al massimo inserire nell'albero e prepara il vattore
      * inserisce *N* nella posizione *0*
      * riempie tutti gli elementi dell'albero con valori _vuoti_
   * *STAMPA()* che stampa l'albero *inordine*, un elemento per riga, ovvero
      * prima stampa inordine il sottoalbero sinistro
      * poi stampa il valore del nodo radice (se esiste, altrimenti visto i figli non sono raggiungibili, non si stampa nulla) 
      * poi stampa inordine il sottoalbero destro
   * *CANCELLA(P)* che azzera il nodo individuato dal percorso *P* (vedi sopra)
      * torna *0* se tutto è andato bene
      * torna *-1* se il percorso è passato o è arrivato su un nodo vuoto o se è uscito dal vettore 
   * *INSERISCI(P,X)* che inserisce il valore *X* nella posizione individuata dal percorso *P* e
      * torna *-1* se il percorso passa su un nodo vuoto o esce dal vettore (se il nodo vuoto è l'arrivo invece va bene, vedi sotto)
      * torna *0* se si è potuto raggiungere un nodo in cui inserire il valore *X* (nota, il nodo individuato può essere vuoto)

__NOTA Le funzioni che percorrono l'albero devono essere ricorsive__

Scrivete il programma *main* ASM MIPS che legge una sequenza di comandi e li esegue sull'albero (allocato staticamente in memoria):

I comandi sono formati da una sola lettera seguita sulle linee successive dagli eventuali _argomenti_ (per compattezza qui li scrivo sulla stessa riga):
   * *Q*     (quit)      esce dal programma
   * *N <i>X</i>*   (nuovo)     chiama la funzione *NUOVOALBERO(X)*
   * *P*     (print)     chiama la funzione *STAMPA()*
   * *C <i>P</i>*   (cancella)  chiama la funzione *CANCELLA(P)*    e ne stampa il risultato
   * *I <i>P X</i>* (inserisci) chiama la funzione *INSERISCI(P,X)* e ne stampa il risultato
Gli argomenti possono essere:
   * *<i>X</i>* un valore numerico positivo
   * *<i>P</i>* un numero positivo da interpretare come percorso sull'albero

---+++ Esempio
---++++ Input
<verbatim>
N
10
I
1
10
I
2
20
I
3
30
I
4
40
I
5
60
I
6
50
I
7
70
P
Q
</verbatim>

Ovvero costruisce l'albero
<verbatim>
        10
      /    \
    30      20
   / \     /   \
 70   60 50    40
</verbatim>

---++++ Output
<verbatim>
0
0
0
0
0
0
0
70
30
60
10
50
20
40
</verbatim>

*Nota:* i primi 7 zeri sono i codici tornati dai sette comandi INSERT, segue la stampa in preordine dell'albero

*NOTA:* può essere comodo stampare prima di ciascun nodo un numero di TAB pari alla profondità raggiunta, così da controllare se l'albero è giusto
<verbatim>
      70
   30
      60
10
      50
   20
      40
</verbatim>



---+++ Consegna entro domenica 22 maggio

%RED%
   * per una mia svista ho pubblicato i programmi consegnati nello HomeWork4 e dai log vedo che almeno 4 persone se li sono scaricati
   * sono costretto a chiudere la consegna oggi in anticipo (scusate)
   * chi non ha consegnato entro stamattina si dedichi a svolgere lo HomeWork5 
%FINE%

Altri esempi di input/output li trovate sulla [[%ATTACHURL%][pagina dei test]], per usarli usate la linea di comando
   * __java -jar Mars_4.5.jar me nc sm ic file.asm &lt; es1.in &gt; es1.out__
   * per controllare che l'output sia uguale potete usare il comando *diff* 


-- Users.AndreaSterbini - 03 May 2016

<!--
   * Set ALLOWTOPICCHANGE = Users.AndreaSterbini
-->
This topic: Architetture2/MZ/AA15_16 > HomeWork4
Topic revision: r10 - 2016-05-21 - AndreaSterbini