|
From: Patrizio B. <het...@us...> - 2004-09-20 12:51:19
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv25341/docs Modified Files: relazione.dvi relazione.pdf relazione.tex Log Message: added comments to code, added a pointer check added deletion in the relation. just a code bug left! Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 Binary files /tmp/cvsewgm88 and /tmp/cvssOf0VB differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.11 retrieving revision 1.12 diff -C2 -d -r1.11 -r1.12 Binary files /tmp/cvstN5Fg9 and /tmp/cvs6DkPLC differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.17 retrieving revision 1.18 diff -C2 -d -r1.17 -r1.18 *** relazione.tex 19 Sep 2004 17:43:46 -0000 1.17 --- relazione.tex 20 Sep 2004 12:50:51 -0000 1.18 *************** *** 171,176 **** 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} \item Risalire fino alla root -> costo O(log(n)) \item Controllare se ogni nodo è bilanciato -> costo O(1) --- 171,192 ---- 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. ! L'algoritmo di controllo opera nella stessa modalità utilizzata durante l'inserimento. ! \begin{itemize} ! \item Caso $-1$: Si sbilancia se viene eliminato un nodo nel sotto albero sinistro (l'albero si sbilancia verso destra) ! \begin{itemize} ! \item Se il subalbero di destra ha il ramo sinistra più lungo si opera una rotazione doppia RL. ! \item Se il subalbero di destra ha il ramo destra più lungo si opera una rotazione semplice RR (Left Rotation). ! \end{itemize} ! \item Caso $+1$: Si sbilancia se viene eliminato un nodo nel sotto albero destro (l'albero si sbilancia verso sinistra) ! \begin{itemize} ! \item Se il subalbero di sinistra ha il ramo sinistra più lungo si opera una rotazione semplice LL (Right Rotation). ! \item Se il subalbero di sinistra ha il ramo destra più lungo si opera una rotazione doppia LR. ! \end{itemize} ! \end{itemize} ! Si nota, quindi, che cancellare un nodo su un ramo fondamentalmente è equivalente (dal punto di vista dei controlli e rotazioni) all'inserimento di un nodo sull'altro ramo. ! Tuttavia la differenza sta nel fatto che la cancellazione potrebbe sbilanciare tutti i nodi presenti sul percorso che porta dal nodo da cancellare alla radice; questo comporta un ciclo di risalita e di controlli, quindi il costo sarà: \begin{itemize} + \item Si scende nell'albero alla ricerca del nodo da eliminare -> costo O(log(n)) + \item Cancellare il nodo -> costo O(1) \item Risalire fino alla root -> costo O(log(n)) \item Controllare se ogni nodo è bilanciato -> costo O(1) *************** *** 199,202 **** --- 215,221 ---- Nella figura \ref{fig:trees} si è modellato tramite UML la struttura delle classi degli alberi, indicando l'ereditarietà, i metodi (distinguendo tra pubblici e privati), le variabili (sempre distinguendo tra pubbliche e private), quindi le interfacce delle classi. + 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} *************** *** 207,212 **** \end{figure} ! 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} --- 226,230 ---- \end{figure} ! \begin{figure}[htbp] \begin{center} *************** *** 216,220 **** \label{fig:applicazione} \end{figure} ! \subsection{Metodi della classe Bst} \begin{itemize} --- 234,238 ---- \label{fig:applicazione} \end{figure} ! \newpage \subsection{Metodi della classe Bst} \begin{itemize} *************** *** 256,260 **** \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] --- 274,278 ---- \end{itemize} ! Nella figura \ref{fig:applicazione2} 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] *************** *** 263,267 **** \end{center} \caption{Applicazione} ! \label{fig:applicazione} \end{figure} --- 281,285 ---- \end{center} \caption{Applicazione} ! \label{fig:applicazione2} \end{figure} |
