Corsi precedenti

Quarta Esercitazione in Laboratorio

Nel seguito si propongono alcuni esercizi d’esame sugli alberi AVL. Per implementare quanto richiesto, useremo le classi AvlNode e AvlTree: per scaricarle fai clic qui, e copia tutti i file nella cartella di lavoro.

La classe AvlTree è schematizzata come segue:

public class AvlTree {
  protected AvlNode root;
  public AvlTree() {...}
  public void insert(int key, Object el) {...}
  public void remove(int key) {...} 
  public Object find(int key) {...}
  public boolean isEmpty() {...}
}

in cui viene utilizzata la classe AvlNode

public class AvlNode {
  public int key;
  public Object el;            //info associata alla chiave
  public AvlNode left, right;
  public int height;
  public int size;             //numero di nodi del sottoalbero che ha per radice questo nodo
 
}

Dalla prova d’esame del 19/09/2005, Problema 4

Estendere AvlTree per progettare una classe che implementi la seguente interfaccia:

public interface CodaDoppia {
  void insert(int key);
  int getMin();     //Restituisce l'elemento con chiave piu' piccola, NdT
  int getMax();     //Restituisce l'elemento con chiave piu' grande,  NdT
  void removeMin(); //Elimina l'elemento con chiave piu' piccola, NdT
  void removeMax(); //Elimina l'elemento con chiave piu' grande,  NdT
}

Realizzare i metodi getMin() e getMax() in modo che abbiano costo .

Dalla prova d’esame del 14/09/2004, Problema 5

Scrivere una classe Java che implementi l’interfaccia Diz2D mediante la classe AvlTree. Determinare i costi computazionali dei tre metodi implementati.

public interface Diz2D  { 
  void insert(int x, int y, Object el); // generica info (el) associata a (x, y) 
  void delete(int x, int y); 
  Object find(int x, int y); // restituisce info associata a (x, y) o null 
}

Dalla prova d’esame del 09/07/2003, Problema 4

Scrivere un metodo Java, con segnatura public static Object search_i(AvlNode root, int i), che restituisce lâ??i-esimo elemento memorizzato in un albero AVL con costo computazionale proporzionale allâ??altezza dellâ??albero.

Prova d’esame del 14/09/2004, Problema 4

Dato un albero binario (chiavi int), scrivere un metodo Java che determini se l’albero è un BST. Definire la rappresentazione Java dell’albero e calcolare il costo computazionale del metodo.

Commenti dei visitatori

Accedi per lasciare commenti.