[Avl-cvs] avl/docs relazione.tex,1.7,1.8

[Patrizio B. <het...@us...>]

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

Modified Files:
	relazione.tex 
Log Message:
finished, lacks images and image impagination only


Index: relazione.tex
===================================================================
RCS file: /cvsroot/avl/avl/docs/relazione.tex,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** relazione.tex	6 Sep 2004 16:01:52 -0000	1.7
--- relazione.tex	7 Sep 2004 16:33:51 -0000	1.8
***************
*** 109,116 ****
  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 DD: inserimento nel sotto albero destro di un figlio destro
! \item SD: inserimento nel sotto albero sinistro di un figlio destro
! \item DS: inserimento nel sotto albero destro di un figlio sinistro
! \item SS: inserimento nel sotto albero sinistro di un figlio sinistro
  \end {itemize}
  Cosiderando il tipo di bilanciamento considerato la rotazione è un'operazione che fa "girare" i nodi, facendo scendere di  livello il nodo sbilanciato e far risalire il nodo centrale: in questo modo i Fdb verranno equilibrati.
--- 109,116 ----
  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
! \item LR: inserimento nel sotto albero sinistro di un figlio destro
! \item RL: inserimento nel sotto albero destro di un figlio sinistro
! \item LL: inserimento nel sotto albero sinistro di un figlio sinistro
  \end {itemize}
  Cosiderando il tipo di bilanciamento considerato la rotazione è un'operazione che fa "girare" i nodi, facendo scendere di  livello il nodo sbilanciato e far risalire il nodo centrale: in questo modo i Fdb verranno equilibrati.
***************
*** 125,131 ****
  
  La figura \ref{fig:ll} visualizza il comportamento della rotazione LL. 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. In questo caso viene inserito un nuovo nodo 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.
! La rotazione DD lavora in modo simmetrico, ovviamente.
  
! Si è visto come le rotazioni effettuabili siano quattro, ma in realtà quelle fondamentali sono due: DD e SS, quelle definite "semplici" e DS e SD ("doppie") che non sono altro che una doppia rotazione semplice.
  \begin{figure}[htbp]
          \begin{center}
--- 125,131 ----
  
  La figura \ref{fig:ll} visualizza il comportamento della rotazione LL. 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. In questo caso viene inserito un nuovo nodo 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.
! La rotazione RR lavora in modo simmetrico, ovviamente.
  
! Si è visto come le rotazioni effettuabili siano quattro, ma in realtà quelle fondamentali sono due: RR e LL, quelle definite "semplici" e RL e LR ("doppie") che non sono altro che una doppia rotazione semplice.
  \begin{figure}[htbp]
          \begin{center}
***************
*** 151,155 ****
  \end{itemize}
  In totale il costo di un inserimento è O(log(n)) nel caso peggiore.
! \\
  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.
--- 151,169 ----
  \end{itemize}
  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).
! \item Se si inserisce nel sotto albero sinistro del nodo figlio destro (RL) è necessaria una Right Rotation e poi una Left Rotation (RL doppia).
! \end{itemize}
! \end{itemize}
! 
  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.
***************
*** 206,211 ****
  \item non è sicuro che l'implementazione proposta sia la più performante in entrambi i casi. L'uso di strutture dati differenti, compilatori e ottimizzazioni specifiche per architetture e sistemi operativi potrebbe in qualche modo sbilanciare a favore di una implementazione l'esito dei test.
  \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.
  \end{itemize}
  Alla luce del lavoro effettuato si possono trarre le seguenti conclusioni:
! gli alberi AVL, teoricamente molto più veloci dei semplici BST nelle tre operazioni fondamentali di ricerca, cancellazione e inserimento, nella pratica sono risultati più performanti ma con prestazioni al di sotto dell'aspettiva, fermo restando che dei test più accurati, quantità di input maggiori e specificatamente disegnati per gli AVL possano smentire i risultati ottenuti.
  \end{document}
--- 220,228 ----
  \item non è sicuro che l'implementazione proposta sia la più performante in entrambi i casi. L'uso di strutture dati differenti, compilatori e ottimizzazioni specifiche per architetture e sistemi operativi potrebbe in qualche modo sbilanciare a favore di una implementazione l'esito dei test.
  \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.
  \end{itemize}
  Alla luce del lavoro effettuato si possono trarre le seguenti conclusioni:
! gli alberi AVL, teoricamente molto più veloci dei semplici BST nelle tre operazioni fondamentali di ricerca, cancellazione e inserimento, nella pratica sono risultati leggermente performanti (e talvolta anche più lenti!) ma con prestazioni al di sotto dell'aspettiva, fermo restando che dei test più accurati, quantità di input maggiori e specificatamente disegnati per gli AVL possano smentire i risultati ottenuti.
! Va sempre considerato anche l'aspetto delle costanti: utilizzando dei set di numeri non immensi, un costo logaritmico, ma con una costante moltiplicativa grande può risultare superiore ad un costo lineare.
! Considerando che nell'implementazione proposta gli alberi AVL derivano dagli alberi BST è possibile che ci sia un overhead dovuto proprio all'esecuzione di questo codice.
  \end{document}