[Avl-cvs] avl/docs relazione.dvi,1.10,1.11 relazione.tex,1.16,1.17

[Gianlorenzo D\\'A. <ja...@us...>]

Update of /cvsroot/avl/avl/docs
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26298/docs

Modified Files:
	relazione.dvi relazione.tex 
Log Message:


Index: relazione.dvi
===================================================================
RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v
retrieving revision 1.10
retrieving revision 1.11
diff -C2 -d -r1.10 -r1.11
Binary files /tmp/cvsg5w8Bo and /tmp/cvszDFHHo differ

Index: relazione.tex
===================================================================
RCS file: /cvsroot/avl/avl/docs/relazione.tex,v
retrieving revision 1.16
retrieving revision 1.17
diff -C2 -d -r1.16 -r1.17
*** relazione.tex	19 Sep 2004 10:29:44 -0000	1.16
--- relazione.tex	19 Sep 2004 17:43:46 -0000	1.17
***************
*** 16,20 ****
  \makeatother
  
! \pagestyle{fancy}
  \title{\Huge\textbf{AVL \& BST Trees}\\\ \\\textbf{\LARGE{Relazione}}\\~\\}
  \author{Patrizio Bassi, Gianlorenzo D'Angelo}
--- 16,20 ----
  \makeatother
  
! %\pagestyle{fancy}
  \title{\Huge\textbf{AVL \& BST Trees}\\\ \\\textbf{\LARGE{Relazione}}\\~\\}
  \author{Patrizio Bassi, Gianlorenzo D'Angelo}
***************
*** 48,52 ****
  cui è nota anche l'efficenza, le prestazioni, gli eventuali problemi.
  
! In questo ambito è collocato questo lavoro: lo studio e implementazione degli alberi BST (Binary Search Tree) "semplici", e i BST gestiti tramite l'algoritmo AVL (anagramma derivato dal nome dei loro ideatori: Adelson-Velskii and Landis, 1962) per individuare quali sono i vantaggi e svantaggi di entrambe le soluzioni.
  
  Nel prossimo capitolo verrà illustrato in generale il funzionamento e l'idea alla base delle tecniche, poi verrà 
--- 48,52 ----
  cui è nota anche l'efficenza, le prestazioni, gli eventuali problemi.
  
! In questo ambito è collocato questo lavoro: lo studio e implementazione degli alberi BST (Binary Search Tree) "semplici", e i BST gestiti tramite l'algoritmo AVL (anagramma derivato dal nome dei loro ideatori: Adelson-Velskii and Landis \cite{AVL}) per individuare quali sono i vantaggi e svantaggi di entrambe le soluzioni.
  
  Nel prossimo capitolo verrà illustrato in generale il funzionamento e l'idea alla base delle tecniche, poi verrà 
***************
*** 59,62 ****
--- 59,63 ----
  Il contesto in cui si colloca questo lavoro è quello dei Dizionari. In ogni problema, di qualsiasi tipo esso sia, si ha a che fare con una certa tipologia e quantità di dati; generalmente si può modellare un problema utilizzando un tipo di dato generico, non ben specificato.
  Questo è il caso del Dizionario: un tipo di dato astratto (ADT, Abstract Data Type) che rappresenti un insieme di tipi di oggetti al quale vengono applicate operazioni di inserimento, cancellazione, ricerca. Sarebbe inutile infatti conoscere degli oggetti senza avere la possibilità di manipolarli o gestirli.
+ 
  La gestione di un dizionario può chiaramente essere effettuata in una infinità di soluzioni, come array (e qui si potrebbe parlare della disposizione degli oggetti nel contenitore array stesso), liste (con tutti i vari tipi di concatenazione) oppure alberi.
  Quest'ultima soluzione offre numerose alternative, tra queste ci sono proprio gli alberi BST e AVL.
***************
*** 64,69 ****
  Generalmente ogni tipo di implementazione ha una doppia faccia, nel senso che risulta ottima e veloce in una certa operazione o in una certa sequenza di dati, mentre ha performance inferiori in altri contesti.
  
! \section{BST}
! L'implementazione BST è basata su questi alberi binari, con in più le condizioni:
  \begin{itemize}
  \item Ogni nodo v ha associata una chiave, un numero (l'informazione)
--- 65,70 ----
  Generalmente ogni tipo di implementazione ha una doppia faccia, nel senso che risulta ottima e veloce in una certa operazione o in una certa sequenza di dati, mentre ha performance inferiori in altri contesti.
  
! \section{BST\cite{cormen}}
! Un albero binario \`e un albero nel quale ogni nodo possiede al pi\`u due figli che vengono denotati generalmente come figlio (o sottoalbero) destro e figlio (o sottoalbero) sinistro del nodo. L'implementazione BST è basata su questi alberi binari, con in più le condizioni:
  \begin{itemize}
  \item Ogni nodo v ha associata una chiave, un numero (l'informazione)
***************
*** 71,75 ****
  \item Le chiavi nel sotto albero destro di v sono tutte > o al più = della chiave di v
  \end{itemize}
! In poche parole in fase di inserimento di un nodo, si controlla il valore della chiave e si appende il nuovo nodo al giusto sottoalbero. In fase di ricerca questa disposizione permette di scartare interi sottoalberi, un sistema molto simile alla ricerca binaria su liste ordinate, il cui costo è logaritmico.
  \begin{figure}[htbp]
          \begin{center}
--- 72,76 ----
  \item Le chiavi nel sotto albero destro di v sono tutte > o al più = della chiave di v
  \end{itemize}
! In poche parole in fase di inserimento di un nodo, si controlla il valore della chiave e si appende il nuovo nodo al giusto sottoalbero. In fase di ricerca questa disposizione permette di scartare interi sottoalberi, un sistema molto simile alla ricerca binaria su array ordinati, il cui costo è logaritmico.
  \begin{figure}[htbp]
          \begin{center}
***************
*** 79,97 ****
          \label{fig:bst}
  \end{figure}
! Il problema fondamentale di questi alberi BST è il bilanciamento.
! Nel caso di una sequenza di nodi, la cui chiave è sempre maggiore del nodo precedente, l'albero diventa semplicemente una lista concatenata, i cui nodi hanno tutti un unico figlio.
! In questo modo, se l'albero è composto da n elementi, la ricerca nel caso peggiore costerà O(n), quindi un costo lineare, che in alcune circostanze può essere ritenuto troppo elevato.
! E' sorto quindi il problema di tenere l'albero bilanciato in modo di avere la ricerca più efficente possibile.
  
! Il concetto di bilanciamento può essere riassunto nel mantenere un albero i cui rami hanno tutti la stessa lunghezza (con differenze di +/-1), in modo da pagare sempre un costo logaritmico per la ricerca.
! Va considerato che questo costo è particolarmente importante, poichè è evidente che anche le operazioni di cancellazione e inserimento contengono sempre una ricerca preliminare (per trovare la posizione in cui inserire e per trovare il nodo da cancellare).
! Il bilanciamento di un albero può essere modificato a causa di inserimenti e cancellazioni: durante queste fasi va quindi aggiunta l'attività di ribilanciamento. Nell' implementazione BST il caso peggiore delle due operazioni è uguale a O(n), ancora un costo lineare.
! Sorge quindi la necessità di mantenere bilanciato l'albero in modo più efficiente: l'implementazione AVL è una buona soluzione.
! \section{AVL}
  Gli alberi AVL sono degli alberi BST, con associata un'informazione aggiuntiva per tutti i nodi: il fattore di bilanciamento (Fdb).
! L'Fdb è un intero che può assumere i valori 0 e +/-1 e rappresenta la differenza tra l'altezza del sotto albero sinistro e il sottoalbero destro di ogni nodo. I valori permettono quindi uno "sbilanciamento" di un solo livello.
! A seguito di un inserimento o cancellazione di un nodo un Fdb può assumere valori +/-2; questo significa che l'albero si è sbilanciato e va corretto.
  E' chiaro che si sta usando una nozione di bilanciamento un po' meno restrittiva, dato che si permette la differenza di un livello al massimo. 
! Dal punto di vista delle performance non c'è praticamente nessuna differenza, tuttavia questa approssimazione rende più complicata la dimostrazione matematica delle performance dell'algoritmo. Tuttavia gli autori dell'AVL han dimostrato che,sfruttando un albero di Fibonacci, nel caso peggiore il costo è pari a 1.44 log(n+2)-0.328, ovvero un costo approssimabile con O(log(n)) dove n è l'altezza dell'albero.
  La dimostrazione di questo risultato esula dallo scopo di questo lavoro.
  \begin{figure}[htbp]
--- 80,93 ----
          \label{fig:bst}
  \end{figure}
! Il problema fondamentale di questi alberi BST è il bilanciamento. Il costo delle operazioni di ricerca, inserimento e cancellazione di un nodo in un albero BST \`e $O\left(h\right)$ dove con $h$ si \`e indicata l'altezza dell'albero ovvero la lunghezza del cammino pi\`u lungo dalla radice fino ad una foglia.
! Nel caso in cui un albero BST viene costruito inserendo una sequenza di nodi in cui la chiave di un nodo è sempre maggiore di quella del nodo precedente, l'albero diventa semplicemente una lista concatenata, i cui nodi hanno tutti un unico figlio e la sua altezza diventa $h=n$ dove $n$ \`e il numero di nodi presenti nell'albero. In questo modo, se l'albero è composto da $n$ elementi, la ricerca nel caso peggiore costerà $O\left(n\right)$, quindi un costo lineare, che in alcune circostanze può essere ritenuto troppo elevato. E' sorto quindi il problema di tenere l'albero bilanciato in modo di avere la ricerca più efficente possibile. 
  
! Il concetto di bilanciamento può essere riassunto nel mantenere un albero i cui rami hanno tutti la stessa lunghezza (con differenze di $+/-1$), in modo da pagare sempre un costo logaritmico per la ricerca. Va considerato che questo costo è particolarmente importante, poichè è evidente che anche le operazioni di cancellazione e inserimento contengono sempre una ricerca preliminare (per trovare la posizione in cui inserire e per trovare il nodo da cancellare). Il bilanciamento di un albero può essere modificato a causa di inserimenti e cancellazioni: durante queste fasi va quindi aggiunta l'attività di ribilanciamento. Nell' implementazione BST il caso peggiore delle due operazioni è uguale a $O\left(n\right)$, ancora un costo lineare. Sorge quindi la necessità di mantenere bilanciato l'albero in modo più efficiente: l'implementazione AVL è una buona soluzione.
! \section{AVL\cite{AVL}}
  Gli alberi AVL sono degli alberi BST, con associata un'informazione aggiuntiva per tutti i nodi: il fattore di bilanciamento (Fdb).
! L'Fdb è un intero che può assumere i valori $0$ e $+/-1$ e rappresenta la differenza tra l'altezza del sotto albero sinistro e il sottoalbero destro di ogni nodo. I valori permettono quindi uno "sbilanciamento" di un solo livello.
! A seguito di un inserimento o cancellazione di un nodo un Fdb può assumere valori $+/-2$; questo significa che l'albero si è sbilanciato e va corretto.
  E' chiaro che si sta usando una nozione di bilanciamento un po' meno restrittiva, dato che si permette la differenza di un livello al massimo. 
! Dal punto di vista delle performance non c'è praticamente nessuna differenza, tuttavia questa approssimazione rende più complicata la dimostrazione matematica delle performance dell'algoritmo. Gli autori dell'AVL hanno per\`o dimostrato che, sfruttando un albero di Fibonacci, nel caso peggiore il costo è pari a $1.44 \log\left(n+2\right)-0.328$, ovvero un costo approssimabile con $O\left(\log\left(h\right)\right)$ dove $h$ è l'altezza dell'albero.
  La dimostrazione di questo risultato esula dallo scopo di questo lavoro.
  \begin{figure}[htbp]
***************
*** 104,108 ****
  Oltre al rilassamento del concetto di bilanciamento, gli AVL incorporano anche l'informazione relativa al Fdb e la sua gestione che ovviamente avrà un costo. L'idea è quella di spendere del tempo nel mantenere il bilanciamento dell'albero in modo da avere costi logaritmici per le operazioni fondamentali che interessano.
  \subsection{Ricerca}
! L'operazione base di ricerca in un albero AVL si svolge nello stesso identico modo di un BST: partendo dalla root si procede "camminando" sul figlio destro o sinistro a seconda che il valore da cercare sia rispettivamente maggiore o minore del valore del nodo in cui ci si trova. In questo modo si effettua una ricerca rapidissima dal costo logaritmico rispetto al numero di elementi che compongono l'albero. Il costo sarà sempre logaritmico perchè l'albero AVL viene sempre mantenuto bilanciato e non ha quindi il difetto dei BST semplici.
  
  \subsection{Inserimento}
--- 100,104 ----
  Oltre al rilassamento del concetto di bilanciamento, gli AVL incorporano anche l'informazione relativa al Fdb e la sua gestione che ovviamente avrà un costo. L'idea è quella di spendere del tempo nel mantenere il bilanciamento dell'albero in modo da avere costi logaritmici per le operazioni fondamentali che interessano.
  \subsection{Ricerca}
! L'operazione base di ricerca in un albero AVL si svolge nello stesso identico modo di un BST: partendo dalla root si procede "camminando" sul figlio destro o sinistro a seconda che il valore da cercare sia rispettivamente maggiore o minore del valore del nodo in cui ci si trova. In questo modo si effettua una ricerca rapidissima dal costo logaritmico rispetto al numero di elementi che compongono l'albero. Il costo sarà sempre logaritmico perchè l'albero AVL viene sempre mantenuto bilanciato e quindi la sua altezza sar\`a sempre pari a $h=\log\left(n\right)$ ed il suo costo nel caso peggiore $O\left(h\right) = O\left(\log\left(n\right)\right)$.
  
  \subsection{Inserimento}
***************
*** 113,117 ****
  Questa operazione non fa altro che ruotare (d'altronde il nome..) i vari nodi, in modo da poter sempre tenere l'albero bilanciato.
   
! L'inserimento in un albero AVL si può dividere in due momenti: nel primo c'è un inserimento identico agli alberi BST, ovvero la ricerca del nodo padre a cui appendere il nuovo nodo come una foglia. Successivamente si deve controllare che l'albero ottenuto non violi le proprietà degli AVL, in quanto, aggiungendo una nuova foglia è possibile che l'altezza di quel ramo dell'albero sia aumentata di uno. Quando un nodo si sbilancia (Fdb= a +/- 2) si possono presentare quattro situazioni, e quindi quattro possibili rotazioni:
  \begin{itemize}
  \item RR: inserimento nel sotto albero destro di un figlio destro
--- 109,113 ----
  Questa operazione non fa altro che ruotare (d'altronde il nome..) i vari nodi, in modo da poter sempre tenere l'albero bilanciato.
   
! L'inserimento in un albero AVL si può dividere in due momenti: nel primo c'è un inserimento identico agli alberi BST, ovvero la ricerca del nodo padre a cui appendere il nuovo nodo come una foglia. Successivamente si deve controllare che l'albero ottenuto non violi le proprietà degli AVL, in quanto, aggiungendo una nuova foglia è possibile che l'altezza di quel ramo dell'albero sia aumentata di uno. Quando un nodo si sbilancia ($Fdb = +/- 2$) si possono presentare quattro situazioni, e quindi quattro possibili rotazioni:
  \begin{itemize}
  \item RR: inserimento nel sotto albero destro di un figlio destro
***************
*** 130,134 ****
  \end{figure}
  
! La figura \ref{fig:ll} visualizza il comportamento della rotazione LL. Il punto a) illustra la situazione iniziale: il nodo di partenza ha Fdb pari a +1. E' evidente che se l'Fdb fosse uguale a 0 non ci sarebbe bisogno di ribilanciare l'albero in quando, ovunque un nodo venisse inserito, il nuovo Fdb sarebbe pari a +/- 1, compatibile con gli AVL. Nel punto b)  viene inserito un nuovo nodo (rappresentato con un pallino vuoto) nel ramo sinistro del sottoalbero sinistro, modificando in +2 il valore del Fdb della radice. A questo punto viene effettuata la rotazione LL: A sale di un livello e B scende, diventando figlio di A. Tuttavia A aveva già due sotto alberi, i cui valori erano sicuramente inferiori a B per la nozione di AVL. Il sotto albero destro di A viene quindi appeso come sottoalbero sinistro di B. Ora l'albero è di nuovo bilanciato. Da notate che sia A che B ora hanno Fdb pari a zero, quindi un successivo inserimento sarà privo di problemi di bilanciamento. Il punto c) mostra come si presenta l'albero dopo l'inserimento e la rotazione descritta.
  La rotazione RR lavora in modo simmetrico, ovviamente.
  
--- 126,130 ----
  \end{figure}
  
! La figura \ref{fig:ll} visualizza il comportamento della rotazione LL. Il punto a) illustra la situazione iniziale: il nodo di partenza ha Fdb pari a $+1$. E' evidente che se l'Fdb fosse uguale a $0$ non ci sarebbe bisogno di ribilanciare l'albero in quanto, ovunque un nodo venisse inserito, il nuovo Fdb sarebbe pari a $+/- 1$, compatibile con gli AVL. Nel punto b)  viene inserito un nuovo nodo (rappresentato con un pallino vuoto) nel ramo sinistro del sottoalbero sinistro, modificando in $+2$ il valore del Fdb della radice. A questo punto viene effettuata la rotazione LL: A sale di un livello e B scende, diventando figlio di A. Tuttavia A aveva già due sotto alberi, i cui valori erano sicuramente inferiori a B per la nozione di AVL. Il sotto albero destro di A viene quindi appeso come sottoalbero sinistro di B. Ora l'albero è di nuovo bilanciato. Da notate che sia A che B ora hanno Fdb pari a zero, quindi un successivo inserimento sarà privo di problemi di bilanciamento. Il punto c) mostra come si presenta l'albero dopo l'inserimento e la rotazione descritta.
  La rotazione RR lavora in modo simmetrico, ovviamente.
  
***************
*** 143,149 ****
  La figura \ref{fig:lr} illustra la rotazione LR: si tratta semplicemente di una rotazione RR (sul nodo A) seguita da una rotazione LL (sul nodo C).
  
! Facciamo alcune considerazioni: se lungo il cammino che porta dalla radice alla foglia appena inserita i nodi hanno tutti un Fdb pari a 0 sicuramente non sarà necessario bilanciare l'albero. Se dopo l'inserimento di una foglia l'altezza del nodo padre rimane invariata non è necessaria nessuna rotazione; se invece varia, il nodo padre potrebbe risultare bilanciato, ma i suoi predecessori potrebbe essersi sbilanciati e quindi potrebbe essere necessaria una rotazione sugli antenati.
  Un teorema dice che quando un albero AVL si sbilancia è necessaria una sola rotazione singola o doppia.
! Per tutte le osservazioni fatte, operativamente, dopo inserimento di una foglia si procede a ritroso dalla foglia in questione fino alla radice, controllando sempre l'Fdb: potrà esserci al massimo un unico nodo sbilanciato a cui si applicherà la giusta rotazione.
  \\
  Calcoliamo ora i costi di un inserimento in un albero AVL di n nodi (nel caso peggiore):
--- 139,145 ----
  La figura \ref{fig:lr} illustra la rotazione LR: si tratta semplicemente di una rotazione RR (sul nodo A) seguita da una rotazione LL (sul nodo C).
  
! Facciamo alcune considerazioni: se lungo il cammino che porta dalla radice alla foglia appena inserita i nodi hanno tutti un Fdb pari a $0$ sicuramente non sarà necessario bilanciare l'albero. Se dopo l'inserimento di una foglia l'altezza del nodo padre rimane invariata non è necessaria nessuna rotazione; se invece varia, il nodo padre potrebbe risultare bilanciato, ma i suoi predecessori potrebbe essersi sbilanciati e quindi potrebbe essere necessaria una rotazione sugli antenati.
  Un teorema dice che quando un albero AVL si sbilancia è necessaria una sola rotazione singola o doppia.
! Per tutte le osservazioni fatte, operativamente, dopo inserimento di una foglia si procede a ritroso dalla foglia in questione fino ad incontrare il primo nodo che prima dell'inserimento aveva Fdb pari a $+/- 1$, controllando sempre l'Fdb: potrà esserci al massimo un unico nodo sbilanciato a cui si applicherà la giusta rotazione.
  \\
  Calcoliamo ora i costi di un inserimento in un albero AVL di n nodi (nel caso peggiore):
***************
*** 158,169 ****
  In totale il costo di un inserimento è O(log(n)) nel caso peggiore.
  
! Ricapitolando: durante l'inserimento lo sbialnciamento è possibile solo nel caso in cui un nodo ha un Fdb pari a +/-1.
  \begin{itemize}
! \item Caso +1: Si sbilancia se viene inserito un nodo nel sotto albero sinistro.
  \begin{itemize}
  \item Se si inserisce nel sotto albero sinistro del nodo figlio sinistro (LL) è necessaria una Right Rotation (semplice).
  \item Se si inserisce nel sotto albero destro del nodo figlio sinistro (LR) è necessaria una Left Rotation e poi una Right Rotation (LR doppia).
  \end{itemize}
! \item Caso -1: Si sbilancia se viene inserito un nodo nel sotto albero destro.
  \begin{itemize}
  \item Se si inserisce nel sotto albero destro del nodo figlio destro (RR) è necessaria una Left Rotation (semplice).
--- 154,165 ----
  In totale il costo di un inserimento è O(log(n)) nel caso peggiore.
  
! Ricapitolando: durante l'inserimento lo sbialnciamento è possibile solo nel caso in cui un nodo ha un Fdb pari a $+/-1$.
  \begin{itemize}
! \item Caso $+1$: Si sbilancia se viene inserito un nodo nel sotto albero sinistro.
  \begin{itemize}
  \item Se si inserisce nel sotto albero sinistro del nodo figlio sinistro (LL) è necessaria una Right Rotation (semplice).
  \item Se si inserisce nel sotto albero destro del nodo figlio sinistro (LR) è necessaria una Left Rotation e poi una Right Rotation (LR doppia).
  \end{itemize}
! \item Caso $-1$: Si sbilancia se viene inserito un nodo nel sotto albero destro.
  \begin{itemize}
  \item Se si inserisce nel sotto albero destro del nodo figlio destro (RR) è necessaria una Left Rotation (semplice).
***************
*** 174,178 ****
  \subsection{Cancellazione}
  La cancellazione di un nodo AVL è identica a quella in un albero BST, tuttavia soffre degli stessi problemi dell'inserimento: a seguito dell'eliminazione di un nodo l'albero potrebbe essersi sbilanciato.
! E' quindi necessario ripetere gli stessi controlli di cui si è parlato in precedenza: partire dal nodo più basso del ramo interessato e risalire, bilanciando tutti i nodi con Fdb pari a +/- 2 con rotazioni singole o doppie.
  A causa di una sola cancellazione ogni nodo del ramo potrebbe aver perso il bilanciamento, quindi il costo sarà:
  \begin{itemize}
--- 170,174 ----
  \subsection{Cancellazione}
  La cancellazione di un nodo AVL è identica a quella in un albero BST, tuttavia soffre degli stessi problemi dell'inserimento: a seguito dell'eliminazione di un nodo l'albero potrebbe essersi sbilanciato.
! E' quindi necessario ripetere gli stessi controlli di cui si è parlato in precedenza: partire dal nodo più basso del ramo interessato e risalire, bilanciando tutti i nodi con Fdb pari a $+/- 2$ con rotazioni singole o doppie.
  A causa di una sola cancellazione ogni nodo del ramo potrebbe aver perso il bilanciamento, quindi il costo sarà:
  \begin{itemize}
***************
*** 185,189 ****
  \chapter{Implementazione}\label{Applicazione}
  \section{Struttura e caratteristiche del codice}
! Nei capitoli precedenti gli AVL sono stati descriti come dei BST a cui vengono applicate operazione di bilanciamento dette rotazioni. \`E quindi evidente che gli AVL sono a tutti gli effetti dei BST: è questa la ragione della implementazione in C++ (e non il semplice C), linguaggio orientato agli oggetti che permette di sfruttare l'ereditarietà tra gli AVL e i BST.
  L'implementazione proposta è costituita da quattro parti fondamentali.
  \begin{itemize}
--- 181,185 ----
  \chapter{Implementazione}\label{Applicazione}
  \section{Struttura e caratteristiche del codice}
! Nei capitoli precedenti gli AVL sono stati descritti come dei BST a cui vengono applicate operazione di bilanciamento dette rotazioni. \`E quindi evidente che gli AVL sono a tutti gli effetti dei BST: è questa la ragione della implementazione in C++ (e non il semplice C), linguaggio orientato agli oggetti che permette di sfruttare l'ereditarietà tra gli AVL e i BST.
  L'implementazione proposta è costituita da quattro parti fondamentali.
  \begin{itemize}
***************
*** 195,199 ****
  
  Il client (avl.cpp) e le funzioni di stampa contenute in bst.cpp hanno due modalità grafiche: una è basata sul semplice utilizzo delle funzioni C/C++ (printf, cout, scanf) che implementano un'applicazione a linea di comando.
! L'altra, molto più interessante, implementa una GUI attraverso l'uso delle librerie GTK (www.gtk.org).
  La GUI permette una visualizzazione degli alberi molto più completa, gradevole ed intuitiva, inoltre permette di effettuare più test senza riavviare l'applicazione e di manipolare gli alberi a proprio piacimento inserendo e cancellando valori scelti dall'utente (questa particolarità non è presente nel client a linea di comando).
  La scelta delle due interfacce va effettuata al momento della compilazione, il codice è separato e distinto tramite comandi del preprocessore del compilatore \#ifdef , in modo da mantenere il codice più snello e pulito possibile.
--- 191,195 ----
  
  Il client (avl.cpp) e le funzioni di stampa contenute in bst.cpp hanno due modalità grafiche: una è basata sul semplice utilizzo delle funzioni C/C++ (printf, cout, scanf) che implementano un'applicazione a linea di comando.
! L'altra, molto più interessante, implementa una GUI attraverso l'uso delle librerie GTK (\cite{GTK}).
  La GUI permette una visualizzazione degli alberi molto più completa, gradevole ed intuitiva, inoltre permette di effettuare più test senza riavviare l'applicazione e di manipolare gli alberi a proprio piacimento inserendo e cancellando valori scelti dall'utente (questa particolarità non è presente nel client a linea di comando).
  La scelta delle due interfacce va effettuata al momento della compilazione, il codice è separato e distinto tramite comandi del preprocessore del compilatore \#ifdef , in modo da mantenere il codice più snello e pulito possibile.
***************
*** 221,224 ****
--- 217,269 ----
  \end{figure}
  
+ \subsection{Metodi della classe Bst}
+ \begin{itemize}
+ \item Bst(), Bst(val:int) : Costruttori della classe.
+ \item getLeft() , getRight(), getParent(), getValue() : metodi di accesso agli attributi. Restituiscono rispettivamente: il puntatore al figlio sinistro, il puntatore al figlio destro, il puntatore al nodo padre ed il valore di un nodo.
+ \item setLeft(Bst * l) , setRight(Bst * r), setParent(Bst * p), setValue(int val) : metodi di accesso agli attributi. Impostano i valori rispettivamente di : figlio sinistro, figlio destro, nodo padre e valore.
+ \item root() : Restituisce la radice dell'albero a cui appartiene il nodo corrente.
+ \item isLeaf() : Indica se il nodo corrente è una foglia.
+ \item isRoot() : Indica se il nodo è la radice dell'albero.
+ \item level() : Calcola il livello del nodo (ovvero la lunghezza del cammino tra il nodo corrente e la radice).
+ \item nodes() : Calcola il numero di nodi dell'albero che ha come radice il nodo corrente.
+ \item leaves() : Calcola il numero di foglie dell'albero che ha come radice il nodo corrente.
+ \item height() : Calcola l'altezza (lunghezza del ramo più lungo) dell'albero che ha come radice il nodo.
+ \item search(int key) : Ricerca un nodo di valore key in modo iterativo e ne restituisce il puntatore, se la ricerca ha esito negativo restituisce NULL.
+ \item insert(int key) :  Aggiunge un nodo con valore key nell'albero.
+ \item erase() : Elimina il nodo corrente dall'albero ( viene richiamato da erase(int) ).
+ \item erase(int key) : Elimina il nodo di valore key dall'albero.
+ \item max() : Trova il nodo dell'albero che ha valore massimo e ne restituisce il puntatore.
+ \item min() : Trova il nodo dell'albero che ha valore minimo e ne restituisce il puntatore.
+ \item predecessor() : Restituisce il puntatore del nodo predecessore (Il nodo che ha valore maggiore tra quelli che hanno valore minore).
+ \item successor() :  Restituisce il puntatore del nodo successore (Il nodo che ha valore minore tra quelli che hanno valore maggiore).
+ \item print\_ric(int lev, int tab) , print() , c\_print(char *string) print\_best\_look() : funzioni di stampa per la modalit\`a testuale.
+ \item print\_gtk\_ric() , print\_best\_look() : funzioni di stampa per la modalit\`a visuale.
+ \end{itemize}
+ 
+ \subsection{Metodi della classe Avl}
+ \begin{itemize}
+ \item setFdb() : Calcola il FdB del nodo corrente impostando il valore dell'altezza.
+ \item setFdb( Avlt * start , Avlt * end) : Calcola il fattore di bilanciamento a di tutti i nodi del cammino da start a end.
+ \item getFdb() : Calcola e restituisce il FdB del nodo corrente.
+ \item getHeight() , setHeight(int he) : Metodi di accesso all'attributo height.
+ \item leftRotate() :  Effettua una rotazione verso sinistra e restituisce il nuovo nodo genitore (rotazione dd).
+ \item rightRotate() : Effettua una rotazione verso destra e restituisce il nuovo nodo genitore (rotazione ss).
+ \item insert(int key) : Inserisce un nuovo nodo con valore key utilizzando un algoritmo ricorsivo. Reimplementa il metodo analogo ereditato da Bst.
+ \item insert\_iter(int key) : Inserisce un nuovo nodo con valore key utilizzando un algoritmo iterativo.
+ \item erase(int key) : Elimina il nodo di valore key dall'albero. Reimplementa il metodo analogo ereditato da Bst.
+ \item checkBalance() : Verifica se l'albero è bilanciato.
+ \item getWrongs() : Restituisce un vettore di nodi che hanno FdB diverso da -1,0,+1. Questa funzione dovrebbe restituire sempre un vettore vuoto e, come la precedente \`e utile solo per testare l'effettivo funzionamento della classe.
+ \end{itemize}
+ 
+ Nella figura \ref{fig:applicazione} si è modellato il resto dell'implementazione: il main che crea un oggetto di tipo Test che al suo interno include due oggetti, un Avlt e un Bst, che andrà a manipolare e testare.
+ Si è fatto uso degli stereotipi UML, tuttavia la rappresentazione è abbastanza intuitiva anche per i non esperti di questo linguaggio.
+ \begin{figure}[htbp]
+         \begin{center}
+                 \includegraphics[height=420pt,angle=90]{application}
+ 	\end{center}
+         \caption{Applicazione}
+         \label{fig:applicazione}
+ \end{figure}
+ 
  \newpage
  
***************
*** 313,317 ****
  \item La misurazione del tempo impiegato è effettuata tramite chiamate alla funzione "clock()" e il calcolo della differenza tra i due istanti di misurazione. L'accuratezza della differenza non è quindi assicurata.
  \item Nel test comparativo si usano numeri estratti casualmente, ma non gli stessi per entrambi gli alberi.
! \item Come verr\`a detto pi\`u avanti un albero BST generato con sequenze casuali di valori e sottoposto ad operazioni casuali di inserimento e cancellazione avr\`a mediamente l'aspetto di un albero bilanciato pur non rispettando questa definizione.
  \end{itemize}
  
--- 358,362 ----
  \item La misurazione del tempo impiegato è effettuata tramite chiamate alla funzione "clock()" e il calcolo della differenza tra i due istanti di misurazione. L'accuratezza della differenza non è quindi assicurata.
  \item Nel test comparativo si usano numeri estratti casualmente, ma non gli stessi per entrambi gli alberi.
! \item Come verr\`a detto pi\`u avanti un albero BST generato con sequenze casuali di valori e sottoposto ad operazioni casuali di inserimento e cancellazione avr\`a mediamente l'aspetto di un albero bilanciato pur non rispettando alla lettera questa definizione.
  \end{itemize}
  
***************
*** 346,350 ****
  Questo risultato \`e giustificato dal fatto che un albero di ricerca costruito utilizzando l'implementazione BST inserendo una sequenza casuale di valori ha un'altezza media $h$ pari ad $h=O\left(lg\left(n\right)\right)$ (cfr. \cite{cormen}) uguale cio\`e all'altezza di un albero costruito utilizzando l'implementazione AVL (con la differenza che questo presenta tale valore di altezza per tutte le sequenze di input). L'albero BST ha inoltre il vantaggio di non dover eseguire le operazioni di rotazione e aggiornamento del fattore di bilanciamento.
  \begin{center}
!   \includegraphics[width=400pt]{ins_casuale}
  \end{center}
  \newpage
--- 391,395 ----
  Questo risultato \`e giustificato dal fatto che un albero di ricerca costruito utilizzando l'implementazione BST inserendo una sequenza casuale di valori ha un'altezza media $h$ pari ad $h=O\left(lg\left(n\right)\right)$ (cfr. \cite{cormen}) uguale cio\`e all'altezza di un albero costruito utilizzando l'implementazione AVL (con la differenza che questo presenta tale valore di altezza per tutte le sequenze di input). L'albero BST ha inoltre il vantaggio di non dover eseguire le operazioni di rotazione e aggiornamento del fattore di bilanciamento.
  \begin{center}
!   \includegraphics[width=380pt]{ins_casuale}
  \end{center}
  \newpage
***************
*** 420,424 ****
  L'inserimento di una sequenza di valori sempre crescenti in un albero binario rappresenta il caso peggiore (insieme a quello di inserimento di valori sempre decrescenti) se si sta utilizzando un'implementazione semplice BST ma non influisce in modo significativo nel caso in cui si utilizzi un'implementazione AVL. In questo caso, infatti, un albero BST degenera in una lista nella quale l'inserimento di un nuovo valore viene fatto sempre in coda e che quindi presenta un costo di inserimento pari a $O\left(n\right)$.
  
! In particolare il primo inserimento sull'albero vuoto ha un costo pari a $c$ ovvero una costante. Il secondo inserimento ha un costo pari a $c + c1 \approx c$ ovvero il costo della vistia del nodo inserito precedentemente pi\`u il costo del nuovo inserimento. Al generico inserimento (l'$i$-esimo) si ha un costo par a circa $ci$. Il costo totale si ottiente sommando tutti i costi parziali fino ad $i = n$.
  \[
  \sum_{i=1}^n ci = c \frac{n\left(n-1\right)}{2} = O\left(n^2\right)
--- 465,469 ----
  L'inserimento di una sequenza di valori sempre crescenti in un albero binario rappresenta il caso peggiore (insieme a quello di inserimento di valori sempre decrescenti) se si sta utilizzando un'implementazione semplice BST ma non influisce in modo significativo nel caso in cui si utilizzi un'implementazione AVL. In questo caso, infatti, un albero BST degenera in una lista nella quale l'inserimento di un nuovo valore viene fatto sempre in coda e che quindi presenta un costo di inserimento pari a $O\left(n\right)$.
  
! In particolare il primo inserimento sull'albero vuoto ha un costo pari a $c$ ovvero una costante. Il secondo inserimento ha un costo pari a $c + c1 \approx c$ ovvero il costo della visita del nodo inserito precedentemente pi\`u il costo del nuovo inserimento. Al generico inserimento (l'$i$-esimo) si ha un costo par a circa $ci$. Il costo totale si ottiente sommando tutti i costi parziali fino ad $i = n$.
  \[
  \sum_{i=1}^n ci = c \frac{n\left(n-1\right)}{2} = O\left(n^2\right)
***************
*** 471,477 ****
  
  \begin{center}
!   \includegraphics[width=420pt]{canc_casuale}
  \end{center}
! \newpage
  \begin{center}
  \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|}
--- 516,522 ----
  
  \begin{center}
!   \includegraphics[width=360pt]{canc_casuale}
  \end{center}
! %\newpage
  \begin{center}
  \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|}
***************
*** 506,510 ****
  Per come \`e costruita la sequenza ogni cancellazione \`e in realt\`a la cancellazione dell'elemento massimo dell'albero il quale ad ogni passo diventa pi\`u piccolo di 1 nodo. In questo modo se la prima cancellazione impiega un tempo pari a $cn$ (dove con $c$ si \`e indicata una costante moltiplicativa) allora la seconda cancellazione impiegher\`a un costo pari a $c\left(n-1\right)$ ed in generale la $i$ esima cancellazione (per $1\leq i \leq n$) impiegher\`a $c\left(n-i\right)$. Il costo totale della cancellazione sar\`a pari alla somma dei costi parziali:
  \[
! \sum_{i=0}^n c\left(n-i\right)
  \]
  sensibilmente superiore ad un costo lineare.
--- 551,558 ----
  Per come \`e costruita la sequenza ogni cancellazione \`e in realt\`a la cancellazione dell'elemento massimo dell'albero il quale ad ogni passo diventa pi\`u piccolo di 1 nodo. In questo modo se la prima cancellazione impiega un tempo pari a $cn$ (dove con $c$ si \`e indicata una costante moltiplicativa) allora la seconda cancellazione impiegher\`a un costo pari a $c\left(n-1\right)$ ed in generale la $i$ esima cancellazione (per $1\leq i \leq n$) impiegher\`a $c\left(n-i\right)$. Il costo totale della cancellazione sar\`a pari alla somma dei costi parziali:
  \[
! \sum_{i=0}^n c\left(n-i\right) = cn\left(n+1\right) -c\sum_{i=0}^n i = cn\left(n+1\right) -\frac{\left(n-1\right)n}{2} = cn\left( n+1-\frac{n-1}{2}\right)
! \]
! \[ 
! = cn \frac{n+3}{2} = O\left(n^2\right)
  \]
  sensibilmente superiore ad un costo lineare.
***************
*** 514,520 ****
  Il grafico mostra appunto come mentre la curva degli AVL rimane vicina ad un andamento lineare, quella relativa ai BST cresce con un pendenza sempre maggiore.
  \begin{center}
!   \includegraphics[width=420pt]{canc_crescente}
  \end{center}
- \newpage
  \begin{center}
  \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|}
--- 562,567 ----
  Il grafico mostra appunto come mentre la curva degli AVL rimane vicina ad un andamento lineare, quella relativa ai BST cresce con un pendenza sempre maggiore.
  \begin{center}
!   \includegraphics[width=360pt]{canc_crescente}
  \end{center}
  \begin{center}
  \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|}
***************
*** 553,556 ****
--- 600,605 ----
       {\it MIT Press},
     1999
+   \bibitem{GTK} 
+      {\it http://www.gtk.org}
    \end{thebibliography}