Alberi binari di ricerca

Questa lezione ha come obiettivo l'implementazione della struttura di dati albero binario di ricerca.

Seguire i seguenti passi implementativi:

1. Leggere, se necessario, lo pseudocodice spiegato nel corso di teoria.
2. Creare una classe ABRNode che rappresenta un nodo di un ABR. La classe deve contenere i seguenti campi:
   • public int key: una chiave intera;
   • public ABRNode p: un riferimento al nodo padre;
   • public ABRNode left: un riferimento al figlio sinistro;
   • public ABRNode right: un riferimento al figlio destro;
   e i seguenti metodi:
   • public ABRNone(int k). Costruttore: assegna la chiave al valore passato e mette a null tutti i riferimenti.
3. Creare una classe ABR che rappresenta un ABR. La classe deve contenere i seguenti campi:
   • public ABRNode root: la radice dell'albero;
   • public int size: la dimensione (numero di nodi) dell'albero;
   e i seguenti metodi:
   • public ABR(). Costruttore: assegna la radice a null e la dimensione a 0;
   • public ABRNode search(int k). Cerca la chiave k nell'albero. Restituisce un nodo con tale chiave oppure null se la chiave non esiste;
   • public void insert(int k). Inserisce un nodo con chiave k;
   • public ABRNode min(ABRNode x). Restituisce il nodo con chiave minima nell'albero radicato in x;
   • public ABRNode max(ABRNode x). Restituisce il nodo con chiave massima nell'albero radicato in x;
   • public ABRNode successor(ABRNode x). Restituisce il nodo successore del nodo x oppure null se il successore non esiste;
   • public ABRNode predecessor(ABRNode x). Restituisce il nodo predecessore del nodo x oppure null se il predecessore non esiste;
   • public void delete(ABRNode x). Cancella il nodo x dell'albero;
   • public void delete(int k). Cancella il nodo con chiave k, se esiste;
   • public void printKeys(). Stampa in ordine intermedio (sinistra-radice-destra) tutte le chiavi.
4. creare un metodo main che accetta i seguenti comandi da console (si veda la classe Console ottenibile con il metodo System.console()):

   new

   crea un nuovo albero vuoto;

   insert k

   inserisce un nodo con chiave k;

   delete k

   cancella il nodo con chiave k, se esiste;

   search k

   cerca un nodo con chiave k e mi informa se esiste;

   min

   restituisce la chiave massima;

   max

   restituisce la chiave minima;

   successor k

   restituisce la chiave che segue k, se esiste;

   prececessor k

   restituisce la chiave che precede k, se esiste;

   print

   stampa le chiavi in ordine intermedio (visualizzazione uni-dimensionale);

   viz

   stampa e salva in un documento di testo l'albero in formato GraphViz (visualizzazione bi-dimensionale; si veda la classe PrintWriter);

   help

   stampa l'elenco dei possibili comandi;

   quit

   esce dal programma;

   
   
   GraphViz è un programma che che visualizza grafi a partire da una descrizione in formato testo. Un esempio di ABR in formato GraphViz è il seguente:

   graph abr {
    5 -- 3;
    3 -- 1;
    3 -- 4;
    5 -- 7;
    7 -- 6;
    7 -- 9;
   }
   

   Per visualizzare un grafico, occorre trasformare la rappresentazione testuale in una qualche rappresentazione grafica. Ad esempio, per ottenere una immagine PNG (abr.png) del grafo contenuto nel documento di testo abr.dot usare il comando:

   dot -Tpng -oabr.png abr.dot

   Il risultato è il seguente:
   
5. Approfondimento: aggiungere alla classe ABR i seguenti metodi:
   • public Boolean insertIfNotFound(int k). Inserisce un nodo con chiave k solo se la chiave non esiste. Restituisce true se la chiave esiste e false altrimenti;
   • public int[] getKeys(). Restituisce un vettore con le chiavi dell'albero in ordine intermedio.
   • una versione iterativa di printKeys e getKeys. [Suggerimento: si definisca e si usi una struttura di dati Pila]