Quinta Esercitazione in Laboratorio


Lo scopo della esercitazione e' quello di utilizzare la struttura dati BST (Albero di ricerca binario) mediante il supporto di animazioni che mostrano gli effetti degli algoritmi.
In particolare la classe Java che gestisce il BST e' la classe BST_g che utilizza BSTNode per la gestione del singolo nodo.
Rispetto ad una normale struttura dati BST, la classe offre dei metodi per la visualizzazione grafica dell'albero e l'evidenziazione dei nodi.
In particolare sono disponibili i metodi classici per la manipolazione dei dati: e metodi per la gestionde delle animazioni:
Queste classi disponibili sono: e devono essere copiate TUTTE nella propria cartella di lavoro;
inoltre, in caso si usi JCreator per la compilazione, occorre compilare in maniera esplicita tutte le classi, iniziando con Gui.java e poi il resto.

Parte 1

Questa parte e' utile a prendere familiarita' con le funzioni grafiche per la manipolazione dei nodi.

Operazioni elementari

  1. Realizzare un metodo che permette l'inserimento dell'albero BST
    albero esempio
  2. Realizzare il metodo void postOrdine(BST_g tree)che visita l'albero seguendo lo schema post ordine.
    Ogni volta che si accede ad un nuovo nodo, questo va colorato di grigio e solo quando viene effettivamente visitato va impostato a rosso.
  3. Realizzare il metodo int max(BST_g tree)che cerca il massimo dell'albero; in particolare ad ogni iterazione deve evidenziare di verde il nodo in qui si trova.
    Il nodo di valore massimo deve infine essere evidenziato con il rosso.

Soluzione

La soluzione e' disponibile qui.

Parte 2

Esercizi sui BST

Questa sezione raccoglie semplici esercizi che sfruttano l'ordinamento del BST per essere svolti in maniera efficiente.
  1. Inserimento bilanciato: Realizzare un metodo Java void insertBalanced(int[] input, BST_g tree) che dato un array di interi qualsiasi e un albero, inserisca secondo una opportuno ordine, i valori del vettore nell'albero BST in modo che questo sia bilanciato, cioe' in cui la differenza tra i livelli di due foglie non puo' essere superiore ad uno.

    Suggerimenti:
  2. Implementare il metodo boolean equalsTopologia(BST_g tree1,BST_g tree2); che controlla che i due alberi siano uguali sia nei valori che nella topologia.
  3. Implementare il metodo boolean equalsValori(BST_g tree1,BST_g tree2); che controlla che i due alberi contengano gli stessi valori.Assumere che non ci sono valori duplicati.

Soluzione

La soluzione e' disponibile qui.

Esercizi su alberi binari

In questa sezione vengono presentati esercizi generici sugli alberi binari che per essere svolti non richiedono necessariamente l'utilizzo dei BST, ma che possono comunque essere applicate a queste strutture dati.
  1. Vistita in ampiezza
    Scrivere un metodo void visitaInAmpiezza(BST_g tree) che effettui la visita in ampiezza dell'albero, cioe' visitando tutti i nodi di ogni livello (da sinistra a destra) prima di passare ai nodi del livello successivo.
    In particolare il metodo deve efidenziare nell'albero con il colore rosso i nodi visitati e con il verde quelli incontrati, ma non ancora visitati, e messi in coda.

    Suggerimento Per effettuare la visita in ampiezza (in versione iterativa) si puo' utilizzare una coda che contiene il nodo da visitare (inizialmente la radice) e ad ogni passo si estrae dalla testa un nodo (oggetto di visita) e si aggiungono in coda i nodi figli.
  2. Prova d’esame del 01/07/2004, Problema 2 Dato un albero t, definiamo <code>int gap(t)</code> la differenza fra la lunghezza del suo ramo più lungo e quella del suo ramo più corto. Il gap di un albero vuoto è per definizione pari a 0.<br> Definire un metodo Java che calcola il gap cioe' che, dato un albero t, restituisca il valore di gap(t).
    Determinare il costo computazionale di tale metodo.

Soluzione

La soluzione e' disponibile qui.

Parte 3

BST multidimensionale

Definire una struttura dati basata sui BST in grado di memorizzare le coordinate intere bidimensionali di un piano.
Le operazioni che devono essere implementate in modo efficiente sono:
Suggerimento: La struttura dati puo' essere costituita da un BST che per ogni nodo memorizza sia l'ascissa x che un riferimento ad un secondo BST contenente tutte le ordinate y dei punti con la stessa ascissa (x).

Soluzione

La soluzione e' fornita nelle seguenti classi.