Corsi precedenti

Svolgimento guidato

CodaDoppia

Rappresentiamo la coda doppia tramite un AVL. Siccome la classe CodaDoppia estende la classe AvlTree, ogni coda doppia è anche un AVL; useremo per la rappresentazione della coda proprio tale AVL. Il motivo per cui usiamo l’ereditarietà è la possibilità di accedere anche alle variabili protette della classe AvlTree, in particolare alla variabile root.

Ogni volta che il cliente invoca la insert inseriamo semplicemente un nodo nell’AVL:

public void insert(int key) {
  insert(key, null);
}

(Dal momento che la coda doppia non prevede di associare dati alle chiavi, abbiamo inserito la chiave associandole il dato null.)

Affrontiamo ora il problema di trovare l’elemento di chiave minima (per l’elemento di chiave massima vale un discorso del tutto simmetrico). Trovare il minimo in un AVL è facile, basta partire dalla radice e scendere verso sinistra “il più possibile”:

public int findMin() {
  AvlNode n = root;
  while(n.left != null)
    n=n.left;
  return n.key;
}

Sfortunatamente il metodo findMin() ha costo , per cui non può essere usato direttamente per trovare il minimo quando il cliente invoca la getMin() (che, ricordiamo, deve avere un costo costante). Osserviamo però che le uniche occasioni in cui il minimo della coda cambia sono le seguenti:

• in seguito all’inserimento di una chiave;
• in seguito alla cancellazione della chiave minima.

Poiché il costo dei metodi di inserimento e di cancellazione è già , in tali occasioni possiamo “precalcolare” il nuovo minimo attraverso la findMin() e memorizzarlo, senza variare il costo asintotico dei metodi. Introduciamo dunque una variabile di istanza min (e simmetricamente max)

protected int min;
protected int max;

e modifichiamo il codice dell’insert() così:

public void insert(int key) {
  insert(key, null);
  min = findMin();
  max = findMax();
}

Ora siamo in grado di definire il metodo getMin():

public int getMin() {
  return min;
}

Non resta che implementare la removeMin(), che si avvale del metodo remove degli AVL per rimuovere il minimo corrente, e aggiorna il minimo al nuovo minimo (se la coda non è diventata vuota):

public void removeMin() {
  remove(min);
  if(!isEmpty())
    min = findMin();
}

Dizio2D

Una possibile soluzione fa uso della tecnica del bit interleaving, esposta a lezione. Perché tale tecnica possa essere impiegata, è necessaria l’assunzione che per la rappresentazione binaria delle chiavi del dizionario 2D siano sufficienti la metà dei bit disponibili per rappresentare le chiavi dell’AVL.

Presentiamo ora una soluzione alternativa al problema. Creiamo un “AVL di AVL”: per memorizzare la prima componente delle chiavi (bidimensionali) useremo un AVL ; assoceremo ad ogni prima componente , occorrente in una delle chiavi, un AVL , contenente tutte le seconde componenti tali che è una chiave del dizionario 2D. Un riferimento a sarà contenuto nel dato associato alla chiave .

Dunque la nostra classe Dizio2D disporrà di una variabile d’istanza corrispondente all’AVL :

protected AvlTree t;

inizializzata nel costruttore:

public Dizio2D() {t = new AvlTree(); }

Il metodo insert(x, y, el) lavora in due passi:

1. cerca l’elemento di chiave x in t:
   • se non esiste, vuol dire che non è presente alcuna chiave con prima componente pari ad x. Inserisce tale chiave, associandogli un nuovo AVL
   • altrimenti trova l’AVL , già esistente
2. inserisce la chiave y in , associandogli l’elemento el.

public void insert(int x, int y, Object el) {
  AvlTree tx = (AvlTree) t.find(x);
  if(tx == null) {
    tx = new AvlTree();
    t.insert(x, tx);
  }
  tx.insert(y, el);
}

La ricerca di (x, y) procede in due passi:

1. cerca x in
2. se la trova, cerca y in

public Object find(int x, int y) {
  AvlTree tx = (AvlTree) t.find(x);
  if(tx != null)
    return tx.find(y);
  else
    return null;
}

La cancellazione funziona come la ricerca, ma cancella la chiave y da , e successivamente cancella x da se è diventato vuoto.

public void remove (int x, int y) {
  AvlTree tx = (AvlTree) t.find(x);
  if(tx != null) {
    tx.remove(y);
    if(tx.isEmpty())
      t.remove(x);
  }
}

Ricerca dell’i-esimo elemento

Tutto sta nel capire, quando si visita un nodo, dove è memorizzato l’-esimo elemento: se nel sottoalbero sinistro, nella radice o nel sottoalbero destro.

Osserviamo che la chiave di tutti i nodi del sottoalbero sinistro precedono quella della radice, che a sua volta precede la chiave di tutti i nodi del sottoalbero destro. Dunque si hanno tre casi:

• Se il sottoalbero sinistro ha almeno nodi, l’-esimo elemento è sicuramente memorizzato nel sottoalbero sinistro. In particolare, è l’-esimo elemento del sottoalbero sinistro.
• Se il sottoalbero sinistro ha esattamente nodi, l’-esimo elemento si trova nella radice.
• Se il sottoalbero sinistro ha nodi, l’-esimo elemento si trova nel sottoalbero destro. In particolare è l’-esimo elemento di tale sottoalbero (perché dal conteggio degli elementi dobbiamo escludere quelli contenuti nel sottoalbero sinistro e nella radice, che precedono l’-esimo elemento).

Ci avvaliamo di un metodo ausiliario size(AvlNode n), che restituisce la dimensione di n o 0 se n è vuoto:

protected static int size(AvlNode n) {
  return n==null? 0: n.size;
}
 
public static Object search_i(AvlNode root, int i) {
  if(root == null) return null;  //Solo per robustezza
  int k = size(r.left);
  if(k >= i)
    return search_i(root.left, i);
  else if(k==i-1)
    return root.el;
  else
    return search_i(root.right, i-(k+1));
}

Verifica di un BST

Presentiamo una soluzione alternativa rispetto a quella contenuta nella soluzione del compito d’esame del 14/09/2004 (che suggeriamo comunque di consultare).

Osserviamo che un albero binario è un BST se tutti i nodi verificano la condizione di BST, che afferma che, per ogni nodo n dell’albero:
tutte le chiavi dei nodi del sottoalbero sinistro di n precedono la chiave di n; e la chiave di n precede tutte le chiavi dei nodi del sottoalbero destro di n.

Esprimiamo in modo ricorsivo questa definizione. Un albero binario è un BST se è un albero vuoto, oppure se gode di queste proprietà:

• i sottoalberi destro e sinistro sono BST;
• tutte le chiavi dei nodi del sottoalbero sinistro sono minori della chiave della radice, e la chiave della radice è minore di tutte le chiavi dei nodi del sottoalbero destro.

Ora consideriamo un nodo n. Se la condizione di BST è già stata verificata per i due sottoalberi sinistro e destro di n, per verificare se l’albero di radice n è un BST è sufficiente verificare che il massimo del sottoalbero sinistro di n preceda la chiave di n, e che questa preceda la chiave minima del sottoalbero destro di n. Per non dover pagare un costo aggiuntivo per cercare il massimo e il minimo in un sottoalbero, scriviamo un metodo di servizio isBstMinMax che, preso in input un nodo m, svolge simultaneamente due azioni, con costo proporzionale al numero di elementi dell’albero di radice m:

1. verifica se l’albero di radice m è un BST;
2. in caso affermativo, restituisce chiave massima e minima di tale albero.

Definiamo una classe Coppia che permette al metodo isBstMinMax di restituire minimo e massimo:

private class Coppia {
  int min, max;
}

Assumiamo che il metodo isBstMinMax restituisce null se e solo se l’albero di radice m non è un BST.

protected static Coppia isBstMinMax(BSTNode m) {
  Coppia c = new Coppia();
 
  c.min = c.max = m.key; //Inizializzo minimo e massimo correnti alla chiave del nodo
 
  if(c.left != null) {
    Coppia cl = isBstMinMax(m.left);
    if(cl == null) //Il sottoalbero sinistro non è un BST
      return null;
    if(cl.max > m.key) //La condizione di BST è violata sul nodo m
      return null;
    c.min = cl.min; //Aggiorno il minimo corrente
  }
 
  if(c.right != null) {
    Coppia cr = isBstMinMax(m.right);
    if(cr == null) //Il sottoalbero destro non è un BST
      return null;
    if(cr.min < m.key) //La condizione di BST è violata sul nodo m
      return null;
    c.max = cr.max; //Aggiorno il massimo corrente
  }
 
  return c; //Successo: l'albero di radice m è un BST, restituisco min e max
 
}

A questo punto è immediato scrivere il metodo principale:

public static boolean isBst(BSTNode root) {
  return (isBstMinMax(root) != null);
}