Homework 4 - Manipolazione di un albero binario

DEFINITIVO

Per rappresentare un albero binario con M nodi si può usare un vettore di N>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 ≤ X < 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

          1
        /   \
      /       \
    2           3
   / \        /   \
 4    5      -6    7
/ \  / \    / \   / 
8 9 10 -1 -2  -3 14

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 > 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 ≤ 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 X (nuovo) chiama la funzione NUOVOALBERO(X)
• P (print) chiama la funzione STAMPA()
• C P (cancella) chiama la funzione CANCELLA(P) e ne stampa il risultato
• I P X (inserisci) chiama la funzione INSERISCI(P,X) e ne stampa il risultato

• X un valore numerico positivo
• P un numero positivo da interpretare come percorso sull'albero

Esempio

Input

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

Ovvero costruisce l'albero

        10
      /    \
    30      20
   / \     /   \
 70   60 50    40

Output

0
0
0
0
0
0
0
70
30
60
10
50
20
40

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

      70
   30
      60
10
      50
   20
      40

Consegna entro domenica 22 maggio

• 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

Altri esempi di input/output li trovate sulla pagina dei test, per usarli usate la linea di comando

• java -jar Mars_4.5.jar me nc sm ic file.asm < es1.in > es1.out
• per controllare che l'output sia uguale potete usare il comando diff

-- AndreaSterbini - 03 May 2016