La classe TreeSet

La classe TreeSet fornisce una realizzazione dell'interfaccia Set utilizzando gli alberi binari di ricerca. Gli elementi di un insieme vengono memorizzati come valori delle chiavi dei nodi dell'albero. Poiché su questi elementi deve essere definito un ordinamento totale, richiederemo che siano di tipo Comparable, e useremo il metodo compareTo per confrontare gli elementi.

La classe TreeSet ha due variabili d'istanza:

root, che contiene il riferimento al nodo radice dell'albero, e vale null solo se l'albero è vuoto;
modCount, che conta il numero di modifiche effettuate sull'albero.

Il costruttore ed i metodi isEmpty e clear sono ovvi.

public class TreeSet implements Set {
    // riferimento al nodo radice
    protected BinNode root;
    // numero di modifiche effettuate
    protected int modCount;

    // inizializza a null il riferimento al nodo radice
    public TreeSet ( ) {
        root = null;
        modCount = 0;
    }

    // determina se l'albero e' vuoto
    public boolean isEmpty ( ) {
        return (root == null);
    }

    // svuota l'albero
    public void clear ( ) {
        root = null ;
        modCount++;
    }

Ricerca in un ABR

Per la ricerca di un elemento in un albero binario di ricerca vediamo il primo esempio di algoritmo che sfrutta la proprietà (ABR). Questa proprietà permette di ridurre la ricorsione doppia, tipica degli algoritmi su alberi binari, ad una ricorsione singola.

L'algoritmo è il seguente:

Se l'albero è vuoto la ricerca termina subito con fallimento.
Se l'albero non è vuoto, si confronta il valore cercato con quello contenuto nella radice dell'albero:

Se i due valori coincidono la ricerca termina con successo.

Se il valore cercato è minore di quello contenuto nella radice la ricerca prosegue ricorsivamente nel sottoalbero sinistro.
Se è invece maggiore la ricerca prosegue nel sottoalbero destro.

Quindi in ogni caso si visita un solo sottoalbero, a differenza della ricerca in un albero binario: si confrontino i due metodi.

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

TreeSet: metodo contains

Questo permette anche di sostituire la ricorsione con una semplice iterazione (while).

Il metodo ausiliario containsHelper usa in realtà un ciclo while (invece della ricorsione) per cercare un nodo contenente l'oggetto x passato per parametro. Restituisce questo nodo se esiste, null altrimenti.
Il metodo contains (che realizza il corrispondente metodo di Set) si limita a trasformare il risultato ricevuto da containsHelper in un boolean. Si noti che contains controlla che il parametro x non sia null e sia di tipo Comparable.

    /*
      restituisce true se l'oggetto x appartiene all'albero,
      restituisce false altrimenti
    */
    public boolean contains ( Object x ) {
        if ( (x == null) || !(x instanceof Comparable) )
            throw new IllegalArgumentException( );
        return ( containsHelper( (Comparable) x ) != null );
    }

    /*
      restituisce il nodo contenente l'oggetto x se questo
      appartiene all'albero, restituisce null altrimenti
    */
    protected BinNode containsHelper ( Comparable x ) {
        BinNode t = root;
        while ( t != null ) {
            if ( x.compareTo( t.key ) < 0 )
                t = t.left;
            else
               if ( x.compareTo( t.key ) > 0 )
                    t = t.right;
               else
                   return t;
        }
        return null;
    }

Inserimento in un ABR

Per inserire un elemento in un albero binario di ricerca si sfrutta ancora la proprietà (ABR). Confrontiamo il valore dell'elemento x da inserire con quello contenuto nella radice dell'albero:

se i due valori coincidono restituiamo false: l'elemento non va inserito perché già presente;
se il valore di x è minore di quello della radice controlliamo se la radice ha il figlio sinistro:

se la radice non ha figlio sinistro lo creiamo ed inseriamo x in questo nuovo nodo;
se la radice ha il figlio sinistro, ricorsivamente inseriamo x nel sottoalbero sinistro.

Se il valore di x è maggiore di quello della radice si opera in modo simmetrico.

TreeSet: metodo add

Il metodo ausiliario addHelper inserisce un oggetto x in un albero non vuoto t, restituendo true se x non appartiene già all'albero e false altrimenti.
Il metodo add (che realizza il corrispondente metodo di Set) inserisce direttamente l'elemento se l'albero è vuoto ed invoca addHelper se l'albero non è vuoto.

   /*
      se l'oggetto x non appartiene all'albero lo inserisce
      nell'albero e restituisce true,
      restituisce false altrimenti
    */
    public boolean add ( Object x ) {
        if ( (x == null) || !(x instanceofComparable) )
            throw new IllegalArgumentException( );
        if ( isEmpty( ) ) {
            // crea l'albero inserendo x come radice
            root = new BinNode(x);
            modCount++;
            return true;
        }
        return ( addHelper( (Comparable) x, root ) );
    }

    /*
      inserisce l'oggetto x nell'albero non vuoto t
      e restituisce true se x non appartiene gia' all'albero,
      restituisce false altrimenti
    */
    protected boolean addHelper(Comparable x, BinNode t){
        if ( x.compareTo( t.key ) == 0 )
            // x e' la chiave contenuta nella radice
            return false;
        else
            if ( x.compareTo( t.key ) < 0 )
               if ( t.left == null ) {
                    //inserisce x come figlio sinistro
                    t.left = new BinNode(x, t);
                    modCount++;
                   return true;
               }
               else
               // inserisce nel sottoalbero sinistro
                   return( addHelper(x, t.left) );
            else
               if ( t.right == null ) {
                    // inserisce x come figlio destro
                    t.right = new BinNode(x, t);
                    modCount++;
                    return true;
                }
               else
                   // inserisce nel sottoalbero destro
                   return( addHelper(x, t.right) );
    }

Metodi min e max

I metodi min, max, successor e predecessor sono pubblici, quindi sono offerti da TreeSet in aggiunta ai metodi dell'interfaccia Set.

Se l'albero non è vuoto, il metodo min determina il nodo contenente la chiave più piccola dell'albero partendo dalla radice e passando da un nodo al suo figlio sinistro, fin quando non raggiunge un nodo senza figlio sinistro. La proprietà (ABR) garantisce che il nodo così individuato sia il minimo.

Il metodo max è realizzato in modo simmetrico.

    public BinNode min ( ) {
        return min (root);
    }

    protected BinNode min ( BinNode t ) {
        if ( t == null ) 
            return null;
        else 
            while ( t.left != null )
                t = t.left;
        return t;
    }

Metodi successor e predecessor

Il metodo successor restituisce il nodo contenente la chiave immediatamente successiva nell'ordinamento alla chiave del nodo t passato per argomento (null se t contiene il massimo).

La proprietà (ABR) permette di realizzare successor senza confrontare esplicitamente le chiavi contenute dell'albero. Si distinguono tre casi:

se l'argomento t è null viene sollevata un'eccezione;
se t ha il figlio destro, si restituisce il minimo del sottoalbero destro (nell'esempio sotto il successore del nodo 50 è 70);
se il sottoalbero destro di t è vuoto, si restituisce l'antenato più prossimo a t il cui figlio sinistro sia anch'esso antenato di t (nell'esempio il successore di 40 è 50).

    protected BinNode successor ( BinNode t ) {
        if ( t == null )
            throw new IllegalArgumentException( );
        else
            if ( t.right != null )
               return ( min(t.right) );
            else {
       /* se il sottoalbero destro e' vuoto restituisce
          l'antenato piu' prossimo a t il cui figlio
          sinistro sia anch'esso antenato di t */
               BinNode y = t.parent;
               while ( (y != null) && (t==y.right) ){
                    t = y;
                    y = y.parent;
                }
               return y;
            }
    }

TreeSet: metodo remove

Cancellazione di un elemento `x` da un albero di ricerca.

Il metodo remove individua il nodo z che contiene l'oggetto x da cancellare, invocando il metodo containsHelper già visto. Se esiste tale nodo, remove invoca il metodo ausiliario removeHelper, che elimina z dall'albero.

    public boolean remove( Object x ) {
        if ( (x == null) || !(x instanceof Comparable) )
            throw new IllegalArgumentException( );
        else
           if ( isEmpty( ) )
               return false;
           else {
              BinNode z = containsHelper((Comparable) x);
              if ( z == null )
                  // x non appartiene all'albero
                  return false;
              else {
                  // x e' contenuto nel nodo z dell'albero
                  removeHelper( z );
                  return true;
              }
           }
    }

Metodo ausiliario removeHelper

Per la cancellazione del nodo z dall'albero distinguiamo tre casi:

Se z è una foglia è sufficiente modificarne il padre (esempio: i nodi 10, 35, 80 nella figura sotto).
Se z ha un solo figlio è sufficiente collegare direttamente il padre di z con il figlio di z (esempio: la figura (b) sotto mostra l'albero ottenuto cancellando il nodo 70 da (a)).

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

Se z ha entrambi i figli (esempio: il nodo 20 della figura sotto (a)), allora si elimina dall'albero il successore di z, e si assegna al campo chiave di z la chiave del suo successore (vedi passaggi da (a) a (b) e da (b) a (c)). Questo funziona perché in un albero binario di ricerca, il successore di un nodo con figlio destro non ha figlio sinistro.

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

Il metodo removeHelper riportato di seguito tratta i tre casi appena descritti in modo leggermente diverso. In sintesi, nel codice sotto, prima si individuano il nodo da cancellare (z stesso se ha meno di due figli, il suo successore altrimenti) e l'eventuale figlio del nodo da cancellare, e quindi si elimina il nodo, sfruttando il fatto che ha un solo figlio.

protected void removeHelper ( BinNode z ) {

        //determina il nodo y da cancellare
        BinNode y;
        if ( (z.left != null) && (z.right != null) ) {
            /* z ha due figli, quindi deve essere eliminato
               il successore di z e deve essere aggiornata
               la chiave di z*/
            y = successor(z);
            z.key = y.key;
        }
        else
            y = z;

        /* determina l'eventuale figlio di y
           (y ha al piu' 1 figlio) */
        BinNode x = (y.left!=null ? y.left : y.right);

/* estrae il nodo y dall'albero */

        if ( x != null )
            // se y ha un figlio ne cambia
            // il padre a quello di y
            x.parent = y.parent;

        if ( y.parent == null )
            // se y era la radice, x diventa la radice
            root = x;
        else
            // x diventa il figlio giusto del padre di y
           if ( y == y.parent.left )
                y.parent.left = x;
           else
                y.parent.right = x;
    }

Iteratori su alberi binari di ricerca

Il metodo iterator della classe di TreeSet restituisce un iteratore che permette di visitare i nodi dell'albero binario di ricerca associato secondo l'ordine simmetrico, e quindi in ordine crescente.

    public Iterator iterator ( ) {
        return new ProtectedItr( );
    }

La classe interna ProtectedItr che realizza l'iteratore per TreeSet è molto simile alla sua omonima interna alla classe LinkedList. Le differenze sono:

l'utilizzo del metodo successor (anzichè il campo next) per passare da un elemento al successivo;
l'utilizzo del metodo ausiliario removeHelper di TreeSet per realizzare il metodo remove.

protected class ProtectedItr implements Iterator {

/* cursore gestito dall'iteratore */
protected BinNode cursor;

/* cursore che precede o coincide con cursor */
protected BinNode precursor;

        /* numero di modifiche al momento della creazione
           dell'iteratore */
        protected int expectedModCount;

        ProtectedItr( ) {
            precursor = cursor = null;
            expectedModCount = modCount;
        }

        public boolean hasNext( ) {
            if ( modCount != expectedModCount )
                throw new ConcurrentModificationException( );
            return ( !isEmpty( ) &&
                     ( (cursor == null) ||
                       (successor( cursor ) != null) ) );
        }

        public Object next( ) {
            if ( !hasNext( ) )
               throw new NoSuchElementException( );
            precursor = cursor;
            cursor = (cursor == null) ?
                         min( root ) : successor( cursor );
            return cursor.key;
        }

        public void remove( ) {
            if ( modCount++ != expectedModCount++ )
               throw new ConcurrentModificationException( );
            if ( cursor == precursor )
               throw new IllegalStateException( );
            removeHelper( cursor );
            cursor = precursor;
        }

}

Analisi di complessità

Qual'è il costo delle operazioni sugli alberi binari di ricerca realizzate nella classe TreeSet?

isEmpty e clear hanno costo costante;
tutte le altre (add, remove, contains, min, max, successor e predecessor) hanno un costo dell'ordine della profondità dell'albero, dato che si muovono sempre su un cammino dalla radice a una foglia (o viceversa). Si veda anche [CLR].

Dato che, come mostrato in [CLR], l'altezza di un albero binario di n nodi costruito in modo casuale è pari a $log_2 \ n$ , le operazioni considerate hanno mediamente costo $O(log_2 \ n)$ .

Diverso è il caso pessimo: l'altezza di un albero binario di ricerca varia a seconda di come gli elementi sono inseriti o cancellati.
Esempio: inserendo uno dopo l'altro i primi 10 interi in un albero vuoto si ottiene una catena lineare in cui la radice contiene 1 ed ha come figlio destro il nodo contenente 2, che a sua volta ha come figlio destro il nodo contenente 3 e così via.

Esistono molte estensioni degli alberi binari di ricerca, come gli alberi RB descritti in [CLR], gli alberi AVL e i 2-3 alberi, che mantengono costantemente la struttura dell'albero "quasi perfettamente bilanciata", garantendo un costo di $O(log_2 \ n)$ per tutte le operazioni.

Esercizi su alberi binari

1) Realizzare il metodo

   public static boolean foglia ( BinNode r )

che restituisce true se r è una foglia, false altrimenti.

2) Realizzare il metodo

   public static int contaInterni ( BinNode r )

che restituisce il numero di nodi interni dell'albero r.

3) Realizzare il metodo

   public static BinNode zio ( BinNode r )

che restituisce il nodo "zio" di r se esiste, null altrimenti.

4) Realizzare il metodo

   public static int altezza ( BinNode r )

che restituisce l'altezza dell'albero binario r (0 se l'albero è vuoto).

5) Realizzare il metodo

    public static int contaFU ( BinNode t )

che restituisce il numero di "figli unici" dell'albero binario di radice t. (Un nodo x è figlio unico se ha un padre il cui unico figlio è x.)

6) Realizzare il metodo

    public static int nodi ( BinNode t, int l )

che restituisce il numero di nodi presenti al livello l nell'albero radicato in t.

Esercizi su alberi binari di ricerca

1) Estendere la classe TreeSet con il metodo toArray( ) che restituisce un array contenente tutti gli oggetti contenuti nell'albero ordinati in ordine crescente.

2) L'elemento

è il mediano della sequenza crescente di valori

quando

è pari e se

quando

è dispari. Ad esempio 5 è il valore mediano della sequenza

ed anche della sequenza

. Estendere la classe TreeSet aggiungendo il metodo

    public Object mediano ( )

che restituisce il nodo contenente il valore mediano dell'insieme se l'insieme non è vuoto, restituisce null altrimenti.

3) Estendere la classe TreeSet aggiungendo il metodo

    public boolean isBalanced ( int k )

che restituisce true se l'albero è k-bilanciato, cioè per ogni nodo n, detti sn e dn le profondità rispettivamente del sottoalbero sinistro e destro, vale |sn - dn| <= k.

Cancellazione di un elemento x da un albero di ricerca.

Cancellazione di un elemento `x` da un albero di ricerca.