Tags:
create new tag
view all tags

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
corrisponderà all'albero (in cui ho evidenziato i nodi vuoti con valori negativi)
          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
Gli argomenti possono essere:
  • 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

Edit | Attach | Watch | Print version | History: r10 < r9 < r8 < r7 < r6 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r10 - 2016-05-21 - AndreaSterbini






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback