Implementazione di 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à:

Per ogni nodo n dell'albero:

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

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

Un ABR è implementato usando BinNode<E>, con alcune condizioni ulteriori

In un ABR non ci possono essere due nodi con la stessa chiave.

L'ordinamento totale che useremo per confrontare le chiavi è quello definito dal metodo compareTo: quindi assumiamo che le chiavi siano oggetti che implementano l'interfaccia Comparable<E> ovvero del tipo <E extends Comparable<E>>

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 assume che l'oggetto da cercare implementi Comparable, per poterlo confrontare con le chiavi dell'albero utilizzando il metodo compareTo().

// Ricerca di un oggetto in un albero binario di ricerca, // algoritmo ricorsivo public static <E extends Comparable<E>> boolean cercaABR(E x, BinNode<E> r){ // caso base (albero vuoto) if (r == null) return false; // caso ricorsivo (albero non vuoto) if (x.compareTo(r.key) < 0) return cercaABR(x, r.left); if (x.compareTo(r.key) > 0) return cercaABR(x, r.right); return true; }

A ogni passo si visita un solo sottoalbero: infatti le due chiamate ricorsive compaiono nel metodo in rami mutuamente esclusivi. Di conseguenza nel caso pessimo la ricerca ha una complessità proporzionale alla profondità dell'albero, cioè logaritmica nel numero di nodi dell'albero (se bilanciato).

Ricordiamo invece che la ricerca in un albero binario, nel caso pessimo (ad esempio, se la chiave cercata non esiste) dobbiamo visitare tutti i nodi, quindi la complessità è lineare nel numero dei nodi. D'altra parte non vi è la restrizione sul tipo di E

// Ricerca di un oggetto in un albero binario, public static <E> boolean cercaAB(E x, BinNode<E> r){ //caso base (albero vuoto) if (r == null) return false; //caso ricorsivo (albero non vuoto) if (x.equals(r.key)) return true; if (cercaAB(x,r.left)) return true; return cercaAB(x,r.right);

Ricorsione ed iterazione su ABR

Nel caso degli alberi binari, gli algoritmi sono basati tipicamente sulla definizione ricorsiva: poiché comprendono una doppia chiamata ricorsiva, in genere non è semplice trovare algoritmi iterativi equivalenti.

Negli alberi binari di ricerca, gli algoritmi di fatto effettuano una singola chiamata ricorsiva in ogni esecuzione, e questo permette di sostituire la ricorsione con una semplice iterazione.

Si confronti il seguente algoritmo con quello visto sopra.

// Ricerca di un oggetto in un albero binario di ricerca, // algoritmo iterativo public static <E extends Comparable<E>> boolean cercaWhile(E x, BinNode<E> r){ while (r != null) { if(x.compareTo(r.key) < 0) r = r.left; else if (x.compareTo(r.key) > 0) r = r.right; else return true; } return false; }

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 (assumendo che l'albero non sia vuoto):

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.

public static <E extends Comparable<E>> boolean inserisci(E x, BinNode<E> t){ if(t==null || x==null) throw new IllegalArgumentException(); if(x.compareTo(t.key) == 0) return false; // x e' gia' presente nell'albero else if (x.compareTo(t.key) < 0) // x va inserito nel sottoalbero sinistro if(t.left == null) { // inserisce x come figlio sinistro t.left = new BinNode<E>(x); return true; } else return(inserisci(x,t.left)); // chiamata ricorsiva else // x va inserito nel sottoalbero destro if(t.right == null) { // inserisce x come figlio destro t.right = new BinNode<E>(x); return true; } else return(inserisci(x,t.right)); // chiamata ricorsiva }

Esercizi su alberi binari di ricerca

Si scrivano i seguenti metodi statici in una classe BinSearchTreeUtil.

1) Scrivere il metodo

   public static <E extends Comparable<E>> boolean isABR (BinNode<E> r)

che restituisce true se e solo se l'albero binario avente come radice r è un albero binario di ricerca.

2) Scrivere il metodo

   public static <E extends Comparable<E>> Vector<E> toVector (BinNode<E> r)

che, assumendo che r sia la radice di un albero binario di ricerca, restituisce un vettore che contiene tutti gli oggetti dell'albero, in ordine crescente.

3) Scrivere il metodo

   public static <E extends Comparable<E>>  boolean  isBalanced (BinNode<E> r)

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

4) Scrivere il metodo

   public static  int[]  data (BinNode<Integer> r)

che restituisce un array di 6 elementi di tipo int che contiene i valori {isNull, isABR, isBalanced, min, max, altezza} con il seguente significato

isNull vale 1 se l'albero è vuoto, 0 altrimenti;
isABR vale 1 se l'albero è ABR, 0 altrimenti;
isBalanced vale 1 se l'albero è bilanciato, 0 altrimenti;
min è il minimo valore contenuto nell'albero (se ABR);
max è il massimo valore contenuto nell'albero (se ABR);
altezza è l'altezza dell'albero.

SOLUZIONE