Alberi binari

Introduciamo ora gli alberi binari e gli alberi binari di ricerca. Questi ultimi saranno utilizzati nella classe TreeSet per una realizzazione del TDA Insieme (Set).

Gli alberi binari hanno una elegante definizione ricorsiva:

Un albero binario è una struttura definita su un insieme di nodi che:

non contiene nessun nodo (albero vuoto), oppure
contiene un nodo radice, un albero binario detto sottoalbero sinistro ed un albero binario detto sottoalbero destro.

Molti algoritmi su alberi binari possono essere descritti in modo naturale sfruttando questa definizione ricorsiva, comprendendo un caso base (per l'albero vuoto) e una clausola ricorsiva (con due chiamate ricorsive, per i due sottoalberi).

Alberi binari: terminologia

Per chiamare i nodi di un albero binario e le relazioni tra di essi si usano termini botanici e di parentela.
Un nodo senza figli è detto foglia. Se il sottoalbero sinistro (risp. destro) di un albero non è vuoto, la sua radice viene detta figlio sinistro (risp. destro) della radice dell'intero albero (che è il padre). La relazione antenato-discendente generalizza quella di padre-figlio nel modo intuitivo.

Ad esempio, nell'albero seguente [il nodo contenente] 10 è la radice dell'albero, ed ha sia un figlio sinistro (20) che un figlio destro (2). I nodi 1, 29 e 7 sono foglie. Il nodo 20 è il padre di 3 e un antenato di 29, che è un discendente di 10. Il nodo 3 ha soltanto il figlio sinistro, perché il suo sottoalbero destro è vuoto.

$\includegraphics[scale=0.35]{Alberi/FigureAlberi/ff1.eps}$

Realizzazione di alberi binari con BinNode

Per realizzare gli alberi binari in Java utilizziamo la classe BinNode, i cui oggetti rappresentano i nodi di un albero. Ogni nodo contiene:

un riferimento al BinNode del figlio sinistro,
un riferimento al BinNode del figlio destro,
un riferimento al BinNode del padre, e
un riferimento ad un oggetto con l'informazione contenuta nel nodo.

La classe BinNode contiene quindi le seguenti variabili d'istanza:

public Object key;    // campo chiave
public BinNode left;   // riferimento al figlio sinistro
public BinNode right; // riferimento al figlio destro
public BinNode parent; // riferimento al padre

La figura seguente mostra l'albero della figura precedente, in cui nodi sono oggetti di BinNode. Le frecce rappresentano riferimenti, null è rappresentato da un cerchietto, l'oggetto nel campo key è impropriamente riportato direttamente dentro il nodo.

$\includegraphics[scale=0.5]{Alberi/FigureAlberi/ff2.eps}$

BinNode: costruttori

La classe BinNode contiene quattro costruttori che permettono la creazione di un BinNode specificando come inizializzare uno o più campi.

/* Costruttori della classe BinNode */

public BinNode( Object k, BinNode l, BinNode r, BinNode p) {
    if ( k == null )
      throw new IllegalArgumentException( );
    key = k;
    left = l;
    right = r;
    parent = p;
    // aggiorna il padre del figlio sinistro (se esiste)
    if (l != null) l.parent = this;
    // aggiorna il padre del figlio destro (se esiste)
    if (r != null) r.parent = this;
}

public BinNode( Object k ) {
this (k, null, null, null);
}

public BinNode( Object k, BinNode p ) {
this (k, null, null, p);
}

public BinNode( Object k, BinNode l, BinNode r ) {
this (k, l, r, null);
}

Come costruire un albero

I costruttori di BinNode permette di costruire un albero binario "dal basso", a partire dalla foglie. Ad esempio, dopo i comandi

   BinNode A,B,C,D;
   A = new BinNode (new Integer(10));
   B = new BinNode (new Integer(20));
   C = new BinNode (new Integer(30),A,B);
   D = new BinNode (new Integer(40),null,C);

la variabile D contiene il riferimento all'albero:

$\includegraphics[scale=0.35]{Alberi/FigureAlberi/f3.eps}$

Visita di un albero binario

"Visitare" un albero significa esaminare sequenzialmente tutti i suoi nodi. Ci sono tre tipi principali di visite:

Nella visita in ordine simmetrico si visita il sottoalbero sinistro, quindi si esamina la radice e infine si visita il sottoalbero destro.
Nella visita in ordine anticipato si esamina prima la radice e quindi si visitano il sottoalbero sinistro e quello destro.
Nella visita in ordine posticipato si visitano prima i due sottoalberi e dopo si esamina la radice.

Altri tre tipi di visite si ottengono dai precedenti scambiando "sinistro" con "destro".

Il metodo seguente realizza la visita in ordine anticipato, stampando tutti i nodi dell'albero passato per argomento. Si noti che la struttura dell'algoritmo riflette la definizione ricorsiva degli alberi binari.

public static void traverse (BinNode r) {
       // caso base (albero vuoto)
       if (r==null) return;
       // caso ricorsivo (albero non vuoto)
       else {
          // esamina radice
          System.out.println(r.key);
          // visita sottoalbero sinistro
          traverse(r.left);
          // visita sottoalbero destro
          traverse(r.right);
       }
}

Le altre due visite si ottengono modificando l'ordine delle tre istruzioni del ramo else.

Ricerca in un albero binario

Il metodo seguente stabilisce se un certo oggetto appartiene o meno ad un dato albero binario, usando una visita in ordine anticipato. Si noti che:

il caso base è banale (come sempre): se l'albero è vuoto, si restituisce false;
la visita viene interrotta non appena si trova l'oggetto cercato.

public static boolean cerca (Object x, BinNode r) {
       // caso base (albero vuoto)
       if (r==null) return false;
       // caso ricorsivo (albero non vuoto)
       else
         if (x.equals(r.key))
              return true;
         else
             if (cerca(x,r.left))
                 return true;
             else
                 return (cerca(x,r.right));
   }

Calcolo del numero di foglie

Come ultimo esempio di algoritmo su alberi binari, vediamo un metodo che conta le foglie dell'albero passato per parametro. Lo schema è il solito:

il caso base è banale: se l'albero è vuoto, allora non contiene alcuna foglia;
nel caso ricorsivo distinguiamo due sottocasi:

se la radice è una foglia, allora questa è l'unica dell'albero;
altrimenti il numero di foglie è la somma di quelle contenute nei due sottoalberi.

Si noti che le due chiamate ricorsive compaiono all'interno della stessa espressione.

public static int contaFoglie (BinNode r) {
      // caso base (albero vuoto)
      if (r == null) return 0;
      // caso ricorsivo (albero non vuoto)
      else{
         if ((r.left == null) && (r.right == null))
              return 1;
         else
              return (contaFoglie(r.left) +
                       contaFoglie(r.right));
       }
}

Alberi binari di ricerca

Un albero binario di ricerca è un albero binario tale che:

sui valori delle chiavi dei suoi nodi è definito un ordinamento totale;
soddisfa la seguente proprietà:

(ABR) Per ogni nodo n dell'albero:

tutte le chiavi dei nodi contenuti nel sottoalbero sinistro di n hanno valore minore della chiave contenuta in n,

tutte le chiavi dei nodi contenuti nel sottoalbero destro di n hanno valore maggiore della chiave contenuta in n.

Un esempio...

$\includegraphics[scale=0.5]{Alberi/FigureAlberi/ff4.eps}$

Una importante conseguenza della proprietà (ABR) è la seguente:

La visita in ordine simmetrico di un albero binario di ricerca A genera una sequenza crescente di tutte le chiavi di A.

Operazioni su alberi binari di ricerca

Sugli alberi binari di ricerca sono definite diverse operazioni (si veda [Cormen-Leiserston-Rivest]). Oltre a quelle dell'interfaccia Set (che vedremo in seguito), sono importanti:

min e max: restituiscono il nodo dell'albero contenente la chiave più piccola e più grande, rispettivamente;

successor e predecessor: applicati ad un nodo dell'albero contenente la chiave x, restituiscono il nodo contenente la chiave immediatamente successiva o precedente a x nell'ordinamento, rispettivamente.

Queste operazioni sono ben definite grazie all'esistenza dell'ordinamento totale tra i valori delle chiavi.