Fondamenti di informatica per Biomedica - 18 maggio 2015

Esempi di domande aperte

(NOTA: questi esercizi sono complicati e presentati solo per mostrare
come si possono affrontare problemi complessi su alberi).


-------------------------------------------------------------------
1. Si vogliono memorizzare in una struttura ad albero binario SPECIALE
   dei dati della forma
      { Nome: "...", Cognome: " ..." , Anno: XXX, ... } /* DATO */
   I nodi dell'albero hanno la forma
      { d: <dato>, n: <intero>, left, right: <figli successivo> } /* NODO */
   e i dati sono memorizzati in modo da supportare in modo efficiente
   una ricerca per ordine di Cognome
   L'albero e` speciale nel senso che dopo che un elemento viene
   restituito 5 volte in una ricerca, esso viene eliminato.

   NOTA: un albero vuoto viene rappresentato indifferentemente da
   r=null (r e` il riferimento al nodo radice) oppure r.d=null.
   La seconda forma serve quando la funzione cerca() sotto indicata
   genera un albero vuoto.

   Scrivere le seguenti funzioni SPIEGANDO BENE come sono gestiti i
   vari casi.

   function ins(r /* NODO radice */, d /* DATO */)
	inserisce d nell'albero, ritorna il riferimento alla radice

   function print(e /* radice */)
        ritorna un vettore con tutti i DATI dell'albero

   function cerca(e /* radice */, c /* COGNOME */)
        restituisce un vettore con tutti gli elemento per i quali
        d.Cognome == c


-------------------------------------------------------------------
2. Modificare l'albero precedente in modo che tutti i dati con
   lo stesso cognome siano memorizzati nello stesso nodo (sempre col
   vincolo che un dato viene eliminato dopo 5 accessi della cerca()
   Indicare la struttura del nodo e mostrare l'implementazione
   delle tre funzioni ins(), print() e cerca()

		===== ESEMPIO DI SOLUZIONE ====

1' esercizio

Per ricordare quante volte un dato e` stato restituito dalla funzione
cerca() (in chiamate successive), bisogna memorizzare l'informazione
da qualche parte all'interno dell'albero -- nel nodo o nell'elemento
stesso.  In generale e` buona norma non inserire informazioni
aggiuntive nel campo dati, e comunque il testo suggerisce implicitamente
di memorizzare questa informazione nel campo n di ogni nodo
dell'albero.

Di conseguenza, la procedura di inserimento potra` utilizzare come
contatore il campo n del nodo appena creato, per esempio inizializzandolo
al valore 5, e la funzione cerca() dovra` decrementare il valore
per ogni nodo restituito, in modo da poter procedere all'eliminazione
al momento opportuno.

Per ottimizzare le ricerce sul Cognome sceglieremo di inserire i nodi
in modo che e.left.d.Cognome <= e.d.Cognome < e.right.d.Cognome
Altre scelte sono possibili e completamente equivalenti,
tenendo comunque conto che influenzano la procedura di eliminazione.

In particolare, se gli elementi a sinistra sono MINORI O UGUALI
al contenuto del nodo, il nodo eliminato si puo` sostituire
con il figlio piu` a destra del sottoalbero sinistro.
Se invece a sinistra abbiamo solo elementi minori, nella rimozione
un nodo va sostituito con il figlio piu` a sinistra del
sottoalbero destro.

    function ins(r /* radice */, dato /* DATO */) {
	/* variabili di appoggio */
	var n = { d: dato, x: 5, left: null, right: null }; /* nuovo nodo */
	var cur;
	/* se l'albero e` vuoto restituisco n come nuova radice */
	if (r == null)  {
	    r = n;
	} else if (r.d == null) { /* altra forma di albero vuoto */
	    r.d = dato;
	    r.n = 5;
	} else { /* altrimenti inserisco in modo ordinato. */
	    cur = r;
	    /* nel ciclo, se un figlio su cui ci dobbiamo spostare
	     * e` vuoto lo sostituiamo con il nuovo nodo,
	     * cosa che causa anche la terminazione del ciclo
	     */
	    while (cur != n) {
		if (dato.Cognome < cur.d.Cognome) { /* dato va a sinistra */
		    cur.left = cur.left ? cur.left : n;
		    cur = cur.left;
		} else { /* dato va a destra */
		    cur.right = cur.right ? cur.right : n;
		    cur = cur.right;
		}
	    }
	}
	return e;
    }

La funzione print(e) effettua una esplorazione ricorsiva dell'albero.
Non e` richiesto un ordine ma restituire i dati ordinati non richiede
alcuno sforzo aggiuntivo. Useremo una funzione ausiliaria printv()

    function printv(r, v) {
	if (r != null && r.d != null) {
	    printv(r.left, v);
	    v.push(r.d);
	    printv(r.right, v);
	}
    }

    function print(r) {
	return printv(r, []);
    }

La procedura di ricerca e` piu` complicata in quando bisogna non solo
restituire i valori ma anche eliminare gli elementi per i quali il
contatore raggiunge il valore zero.
Siccome vogliamo estrarre potenzialmente piu` elementi, la forma
piu` conveniente da usare e` quella di una funzione ricorsiva,
che riceve in ingresso la radice di un sottoalbero, il vettore
di elementi estratti fino al momento corrente, e la chiave di ricerca.
In uscita la funzione restituisce il vettore aggiornato, eliminando
gli elementi nel sottoalbero (eventualmente marcando con e.d=null
la radice, se l'elemento corrispondente e` stato eliminato).

Detta p1 questa funzione di appoggio, essa si puo` invocare
dalla funzione cerca() come sotto:

    function cerca(e, c) {
	return p1(e, [], c);
    }

    function p1(cur, v, c) {
	/* prima di tutto gestiamo i casi di albero vuoto */
	if (cur == null || cur.d == null) {
	     return v;
	}
	if (c <= cur.d.Cognome) {
	    v = p1(cur.left, v, c); /* cerca a sinistra */
	    /* se p1 restituisce un albero vuoto, lo sganciamo dal nodo */
	    if (cur.left && cur.left.d == null) { /* sotto albero vuoto */
		cur.left = null;
	    }
	    if (c == cur.d.Cognome) {
		v.push(cur.d); /* aggiunge nodo corrente */
		cur.n--; /* decrementa contatore */
		/* se il nodo non contiene dati, compatta l'albero */
		if (cur.n == 0) { 
		    compatta(cur);
		}
	    }
	} else {
	    v = p1(cur.right, v, c); /* cerca a destra */
	    if (cur.right && cur.right.d == null) { /* sotto albero vuoto */
		cur.right = null;
	    }
	}
	return v;
    }

Quando l'informazione in un nodo viene eliminata, la funzione
compatta(e) provvede ad eliminare i nodi non necessari, gestendo i
quattro casi possibili (a seconda dell'esistenza o meno di figli
sinistro e destro).

    function compatta(e) {
	var cur, prev;
	if (e.left == null) { /* nessun figlio sinistro */
	    if (e.right == null) { /* neanche figlio destro */
		e.d = null; /* marca nodo come vuoto */
	    } else { /* migra in alto albero destro */
		cur = e.right;
		e.d = cur.d;
		e.n = cur.n;
		e.left = cur.left;
		e.right = cur.right;
	    }
	} else if (e.right == null) { /* solo figlio sinistro */
            /* migra in alto albero sinistro */
            cur = e.left;
            e.d = cur.d;
            e.n = cur.n;
	    e.left = cur.left;
	    e.right = cur.right;
        } else { /* 2 figli */
	    /* sostituisci 'e' col nodo piu` a destra del figlio sinistro */
            prev = e;
            cur = e.left;
            while (cur.right != null) {
                prev = cur;
                cur = cur.right;
            }
            /* ora cur e` il nodo piu` a destra del sottoalbero sinistro.
             * cur.right = null per definizione.
             */
            /* copia le informazioni */
            e.d = cur.d;
            e.n = cur.n;
            /* se cur e` il figlio sinistro di e,
             * bisogna agganciare il suo sottoalbero sinistro ad e.
             * Altrimenti, cur.left va agganciato a prev.right
             */
            if (cur == e.left) {
                e.left = cur.left;
            } else {
                prev.right = cur.left;
	    }
        }
    }

Esercizio 2:

In questo caso mantenere tutte le informazioni con la stessa chiave
nello stesso nodo semplifica la procedura di ricerca, ma richiede
di aggiungere il contatore n a ciascun elemento di informazione.

Possiamo sostituire il campo d con un vettore che contiene coppie n,d

    function ins(e /* radice */, dato /* DATO */) {
	var n = {d:[], left: null, right: null};
	var cur, c = dato.Cognome;
	if (e == null) {
	    e = {d:null, left:null, right:null};
	}
	if (e.d == null) {
	    e.d = [];
	    e.d.push({n:5, d:dato});
	    return e;
	}
	/* cerca posizione di inserimento */
	cur = e;
	while (true) {
	    if (c < cur.d[0].Cognome) { /* inserire a sinistra */
		cur.left = cur.left || n;
		cur = cur.left;
	    } else if (c > cur.d[0].Cognome) { /* inserire a destra */
		cur.right = cur.right || n;
		cur = cur.right;
	    } else { /* inserire qui */
		cur.d.push({n:5, d:dato});
		break;
	    }
	}
	return e;
    }

Per la stampa la struttura e` simile al caso precedente, tranne che
bisogna estrarre esplicitamente tutti gli elementi dal vettore
            
    function printv(r, v) {
	var i;
	if (r != null && r.d != null) {
	    printv(r.left, v);
	    for (i = 0; i < r.d.length; i++) {
		v.push(r.d[i].d);
	    }
	    printv(r.right, v);
	}
    }

    function print(r) {
	return printv(r, []);
    }

Infine la procedura di ricerca e` leggermente piu` semplice perche'
tutti gli elementi sono nello stesso nodo. Dobbiamo comunque eliminare
gli elementi dal vettore ed eventualmente compattare il nodo.

    function cerca(cur, c) {
	var prev, i, x, ris = [];
	if (cur == null || cur.d == null) { /* albero vuoto */
	    return v;
	}
	/* individuiamo il nodo con i dati, tenendo traccia del padre */
	prev = null;
	while (cur != null) {
	    if (c < cur.d[0].Cognome) { /* cerca a sinistra */
		prev = cur;
		cur = cur.left;
	    } else if (c > cur.d[0].Cognome) { /* cerca a destra */
		prev = cur;
		cur = cur.right;
	    } else { /* trovato */
		break;
	    }
	}
	if (cur == null) {
	    return ris;
	}
	/* estraiamo i risultati e lasciamo in x quelli ancora validi */
	x = []; /* elementi da rimuovere */
	for (i = 0; i < cur.d.length; i++) {
	    ris.push(cur.d[i].d);
	    cur.d[i].n--;
	    if (cur.d[i].n > 0) {
		x.push(d[i]);
	    }
	}
	cur.d = x; /* elementi rimasti */
	if (cur.d.length > 0) { /* niente da eliminare, abbiamo finito */
	    return ris;
	}
	/* cur e` vuoto, compatta albero, come sopra */
	if (cur.left == null) { /* nessun figlio sinistro ... */
	    if (cur.right == null) { /* ne` destro; cur va eliminato */
		/* se e` la radice cur.d=null, altrimenti sgancia dal padre */
		if (prev == null) { /* cur e` la radice */
		    cur.d = null;
		} else if (cur == prev.left) {
		    prev.left = null;
		} else {
		    prev.right = null;
		}
	    } else { /* solo figlio destro, migra in alto */
		x = cur.right;
		cur.d = x.d;
		cur.left = x.left;
		cur.right = x.right;
	    }
	} else if (cur.right == null) { /* solo figlio sx, migra in alto */
	    x = cur.left;
	    cur.d = x.d;
	    cur.left = x.left;
	    cur.right = x.right;
	} else { /* due figli, compatta albero */
	    /* sostituisci cur' col nodo piu` a destra del figlio sinistro */
	    prev = cur;
	    x = cur.left;
	    while (x.right != null) {
		prev = x;
		x = x.right;
	    }
	    /* ora x e` il nodo piu` a destra del sottoalbero sinistro.
	     * x.right = null per definizione.
	     */
	    cur.d = x.d; /* copia le informazioni */
	    /* se x e` il figlio sinistro di cur,
	     * bisogna agganciare il suo sottoalbero sinistro a cur.
	     * Altrimenti, cur.left va agganciato a prev.right
	     */
	    if (x == cur.left) {
		cur.left = x.left;
	    } else {
		prev.right = x.left;
	    }
	}
	return ris;
    }

--------------------------