Quarta Esercitazione in Laboratorio


Lo scopo della esercitazione e' quello di studiare la struttura dati BST (Albero di ricerca binario), definirne i principali metodi di gestione (inserimenti, ricerche) e di valutarne le prestazioni comparandole con strutture dati basate su array.
Nella seconda parte invece verranno proposti semplici problemi sugli alberi, da risolvere mediante la scrittura di metodi adhoc.

Classi BST e BSTNode

La classe BSTNode rappresenta i nodi di alberi binari di ricerca a chiavi intere.

La classe BST rappresenta invece alberi binari di ricerca e contiene i seguenti metodi:

Il codice sorgente delle classi e' disponibile ai link seguenti: BSTNode , BST

Parte 1

Implementare i seguenti metodi della classe BST:

Scrivere poi (e testare) un metodo main che costruisca, attraverso un’opportuna sequenza di inserimenti, il BST seguente:

Stampare poi l'albero in notazione a trattini per controllarne la correttezza.

L'esercizio deve essere svolto entro un tempo massimo di 30 minuti, oltre il quale utilizzare la soluzione per poter accedere alla parte successiva



Parte 2

Effettuare dei test comparativo per la valutazione delle performance su alberi BST.
Si vogliono analizzare i tempi di inserimento (e di ricerca) di valori in un BST, comparandoli con quelli di un array.
I passi da seguire sono i seguenti
  1. Allocare un vettore di n interi inizializzandolo con valori random: questo vettore conterra' i valori di input del test.
  2. Creare un BST e con i valori generati e misurarne i tempi.
  3. Creare un array (di dimensione n) e con i valori generati e misurarne i tempi.
  4. (Facoltativo) Conteggiare il tempo necessario a ricercare tutti i valori random generati sia per il BST che per l'array
  5. Ripetere il test con valori di n pari a 1.000, 50.000, 100.000 e 200.000, con distribuzione sia random che sequenziale crescente
Per ottenere i tempi di risposta utilizzare la funzione System.currentMillis().

Parte 3

Minimo Antenato Comune

Definire un metodo public BSTNode antenatoComune(int k1,int 2) che, forniti due valori di chiave (presenti nell'albero) ritorni il minimo antenato comune ai due valori La soluzione e' disponibile qui

Test BST

Dato un albero binario, stabilire se questo e' un albero binario di ricerca (BST).
Soluzione: Condizione necessaria e sufficiente perche' un albero binario sia di ricerca e' che la sua visita in inordine generi numeri non decrescenti (per definizione).

Parte 4 (esercizi per casa)

Unione di BST

scrivere un metodo Java che, dati un nodo v e due BST T1 e T2, verifichi se l’albero ottenibile rendendo T1 sottoalbero sinistro di v e T2 sottoalbero destro di v è un BST. Valutare la complessita' computazionale dell’algoritmo.

Range Query

Diversi problemi d’esame, sono varianti dell’esercizio seguente.

Dato un BST perfettamente bilanciato di nodi, scrivere un metodo Java che, dato un intervallo , con , determini le chiavi dell’albero interne all’intervallo con complessita' computazionale pari a , ove e' il numero di chiavi riportate.

Spezza-albero

Scrivere un algoritmo (Java) che, dato un albero di ricerca T e una chiave k, spezzi T in due alberi di ricerca, il primo con tutte le chiavi di T minori o eguali a k, il secondo con tutte le chiavi di T maggiori di k (assumere che in T non vi siano chiavi duplicate).
Valutare il costo computazionale dell’algoritmo (si noti che non e' necessaria la visita dell’intero albero).

Parte 4 - Suggerimenti

Unione di BST

Osserviamo che, poiche' gia' sappiamo che T1 e T2 sono BST, tutti i nodi interni a tali alberi verificano la condizione di BST. Dunque occorre verificare la condizione di BST soltanto per il nodo v.

La condizione di BST afferma che tutti i nodi di T1 devono avere chiave minore della chiave di v; e la chiave di v deve essere minore di tutte le chiavi dei nodi di T2. La prima condizione puo' essere verificata semplicemente cercando la massima chiave di T1, con complessita' computazionale , dove e' l’altezza di T1, e verificando che tale massimo sia minore della chiave di v. Per T2 si puo' procedere analogamente.

Range Query

E’ sufficiente una visita dell’albero: ogni volta che visitiamo un nodo decidiamo se e' possibile evitare di scendere in uno dei due sottoalberi, perche' tutti i suoi nodi cadono fuori dall’intervallo considerato.

Spezza-albero

Si suggerisce di usare la ricorsione: a seconda del valore della radice, decidere quale dei due sottoalberi occorre spezzare (ricorsivamente), e poi collegare opportunamente la radice a uno dei due sottoalberi restituiti.


SoluzioneParte4.java