Corsi precedenti

Sesta Esercitazione in Laboratorio

Nel seguito si propongono alcuni esercizi d’esame sugli alberi AVL. Per implementare quanto richiesto, useremo la classe AVLTree della libreria del corso asd_library: per scaricarla fai clic qui, e copia tutti i file nella cartella di lavoro.

Attenzione! Osserva che

1. l’interfaccia della asd-library differisce leggermente da quella degli esercizi proposti di seguito; in particolare, le chiavi dell’AVL sono di tipo Comparable;
2. il metodo remove attualmente non è implementato nella classe AVLTree della asd-library.

Prova d’esame del 19/09/2005, Problema 4

Considerare la classe AvlTree schematizzata come segue:

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

in cui viene utilizzata la classe AvlNode

public class AvlNode {
  public int key;
  public AvlNode left, right;
  public int height;
}

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

public interface CodaDoppia {
  void insert(int key);
  int getMin();
  int getMax();
  void removeMin();
  void removeMax();
}

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

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

Scrivere una classe Java che implementi l’interfaccia Diz2D mediante la struttura di dati AVL. Supporre di disporre di una classe AVLTree che implementa l’interfaccia AVL. Determinare i costi computazionali dei tre metodi implementati.

public interface AVL { 
  void insert(int k, Object el); // generica info (el) associata a chiave intera (k) 
  void delete(int k); 
  Object find(int k); // restituisce info associata a k o null 
  int getMin(); // restituisce chiave min 
  int getMax(); // restituisce chiave max 
  int height(); // restituisce numero livelli dell'albero 
  int getSize(); // restituisce numero nodi dell'albero 
}

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 
}

Prova d’esame del 09/07/2003, Problema 4

Scrivere un metodo Java, con segnatura public static AVLNode 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. Si utilizzi la seguente definizione:

class AVLNode { 
  int key; 
  AvlNode left; 
  AvlNode right; 
  int height;
  int size; 
}

dove size indica il numero di elementi memorizzati nel sottoalbero avente come radice il nodo.

NBdT: modificare la classe AVLNode dell’esercitazione, aggiungendo il campo size.

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.