avl-cvs Mailing List for avl
Brought to you by:
hetfield666,
jah2003
Menu
▾
▴
avl-cvs — CVS Commits
You can subscribe to this list here.
| 2004 |
Jan
|
Feb
|
Mar
|
Apr
|
May
(2) |
Jun
(15) |
Jul
(16) |
Aug
(5) |
Sep
(65) |
Oct
|
Nov
|
Dec
|
|---|
|
From: Patrizio B. <het...@us...> - 2004-09-29 11:16:42
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv5559 Modified Files: ChangeLog Log Message: 1.0 stable out! Index: ChangeLog =================================================================== RCS file: /cvsroot/avl/avl/ChangeLog,v retrieving revision 1.11 retrieving revision 1.12 diff -C2 -d -r1.11 -r1.12 *** ChangeLog 8 Sep 2004 17:59:50 -0000 1.11 --- ChangeLog 29 Sep 2004 11:15:53 -0000 1.12 *************** *** 1,2 **** --- 1,15 ---- + --==28.09.2004==-- + ********************************************************************* + <hetfield666> && <jah2003> + - Cleaned all code + - Added comments in every methods/functions + - Updated relation with lastest improvement + - Added lots of new GTK GUI functionalities + + Project Goal has been Reached! 1.0 stable release out. + Now it's safe to use it. Enjoy and mail us bugs/problems/improvements! + ********************************************************************** + + --==08.09.2004==-- <hetfield666>: |
|
From: Patrizio B. <het...@us...> - 2004-09-29 11:16:08
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv5559/docs Modified Files: relazione.dvi relazione.pdf relazione.tex Log Message: 1.0 stable out! Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.12 retrieving revision 1.13 diff -C2 -d -r1.12 -r1.13 Binary files /tmp/cvsDKnJUR and /tmp/cvst2vI8r differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.15 retrieving revision 1.16 diff -C2 -d -r1.15 -r1.16 Binary files /tmp/cvsYYkFuC and /tmp/cvsL1x9Wc differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.21 retrieving revision 1.22 diff -C2 -d -r1.21 -r1.22 *** relazione.tex 21 Sep 2004 17:17:15 -0000 1.21 --- relazione.tex 29 Sep 2004 11:15:56 -0000 1.22 *************** *** 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à --- 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~\cite{cormen} (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à *************** *** 65,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\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} --- 65,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} 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} *************** *** 84,89 **** 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. --- 84,89 ---- 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} ! Gli alberi AVL~\cite{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. *************** *** 229,233 **** 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] --- 229,234 ---- 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, un linguaggio usato sempre più comunemente per la rappresentazione di classi, gerarchie e organizzazione delle stesse. Nella figura \ref{fig:trees} si notano le due classi AVL e BST, legate da una freccia: nella rappresentazione UML la freccia indica che la classe AVL eredita (e quindi contiene anche tutti i metodi e variabili della classe padre) dalla classe BST. ! Nella figura \ref{fig:applicazione} è presente il Main, ovvero la funzione principale richiamata all'avvio del programma, che richiama un'istanza della classe Test attraverso lo stereotivo Create. La classe Test include al suo interno metodi e variabili e contiene anche un oggetto di tipo AVL e un altro di tipo BST; questo "contenimento" è rappresentato attraverso il simbolo di rombo vuoto. \begin{figure}[htbp] *************** *** 287,295 **** \end{itemize} ! \section{Compilazione ed utilizzo} Il codice è distribuito sotto licenza GPL e include commenti esplicativi per tutte le funzioni. Viene distribuito un file compresso tramite gzip (avl.tar.gz). ! Dopo varlo scompattato (tar xzf avl.tar.gz) si troveranno due directory: "docs" e "src". ! La priam contine questa relazione in formato tex (latex), pdf e dvi. Per l'applicazione si entri nella directory "src". --- 288,296 ---- \end{itemize} ! \section{Compilazione} Il codice è distribuito sotto licenza GPL e include commenti esplicativi per tutte le funzioni. Viene distribuito un file compresso tramite gzip (avl.tar.gz). ! Dopo averlo scompattato (tar xzf avl.tar.gz) si troveranno due directory: "docs" e "src". ! La prima contiene questa relazione in formato tex (latex), pdf e dvi. Per l'applicazione si entri nella directory "src". *************** *** 306,313 **** \newpage \section{Screenshots} ! \begin{figure}[htbp] \begin{center} ! \includegraphics[height=440pt]{shell} \end{center} \caption{Client a linea di comando} --- 307,316 ---- \newpage \section{Screenshots} ! In questa sezione verrà presentato un elenco di screenshots rappresentanti l'applicazione implementata. ! Lo scopo è quello da fornire un'idea sommaria delle possibilità offerte e nello stesso tempo essere una breve guida. ! La figura \ref{fig:shell} mostra l'interfaccia a riga di comando: lanciato il programma all'utente vengono richiesti i dati (tipo di test, dimensione dell'albero iniziale e numero di modifiche da effettuare) e dopo la relativa elaborazione vengono visualizzati i risultati, sempre su linea di comando. \`E consigliata a chi non necessita di una GUI, a chi non ha server X (o server video) e a chi non ha le librerie GTK. \begin{figure}[htbp] \begin{center} ! \includegraphics[height=400pt]{shell} \end{center} \caption{Client a linea di comando} *************** *** 315,318 **** --- 318,325 ---- \end{figure} \newpage + Nella figura \ref{fig:start} viene mostrata la prima pagina all'avvio del programma compilato con GUI GTK. + La GUI è divisa in due parti essenzialmente: in alto c'è lo spazio riservato alla visualizzazione grafica dell'albero, + in basso ci sono i campi di input per la scelta del tipo di test (tramite il primo combobox), per la scelta del numero + di nodi dell'albero (tramite il primo spinbox) e per la scelta delle modifiche (tramite il secondo spinbox); questi non tutti per l'inizializzazione del test; una volta terminato si può procedere con la cancellazione/inserimento di un valore a scelta, tramite l'ultimo spinbox. Gli altri bottoni hanno le funzioni intuitive di applicare le modifiche, far partire il test, terminare il programma. \begin{figure}[htbp] \begin{center} *************** *** 324,327 **** --- 331,335 ---- \newpage + Dopo ogni operazione di inizializzazione e di test random vengono create delle finestre popup che aggiornano l'utente con i tempi impiegati e le quantità di dati. \begin{figure}[htbp] \begin{center} *************** *** 340,346 **** \end{figure} \newpage \begin{figure}[htbp] \begin{center} ! \includegraphics[width=480pt, height=480pt]{stampa} \end{center} \caption{Visualizzazione di un albero AVL} --- 348,355 ---- \end{figure} \newpage + A fine test l'albero viene sempre visualizzato in modalità grafica. Si è scelto di rappresentare il nodo destro come primo figlio, il nodo sinistro come secondo (quindi in alto e in basso). Tuttavia per creare un report ancora più dettagliato si è scelto di inserire esplicitamente la dicitura "Right/Left Value" e "son of" per ricordare il padre di ogni nodo. \begin{figure}[htbp] \begin{center} ! \includegraphics[width=480pt, height=440pt]{stampa} \end{center} \caption{Visualizzazione di un albero AVL} *************** *** 349,352 **** --- 358,363 ---- \newpage + Dopo ogni modifica di inserimento/cancellazione di un singolo valore viene creata una finestra popup che visualizza il nuovo albero: la vecchia visualizzazione non viene aggiornata, per permettere il confronto tra i due alberi prima e dopo la modifica. Dopo aver fatto gli opportuni controlli e calcoli, l'utente può chiudere la finestra popup, e la visualizzazione nell'applicazione verrà aggiornata automaticamente con l'ultima versione dell'albero. + Un esempio è proposto nella figura \ref{fig:cancel}. \begin{figure}[htbp] \begin{center} *************** *** 356,360 **** \label{fig:cancel} \end{figure} ! \begin{figure}[htbp] \begin{center} --- 367,374 ---- \label{fig:cancel} \end{figure} ! \newpage ! Se invece di testare un AVL o un BST si sceglie un test comparativo non è possibile visualizzare gli alberi ! (non si può prediligere la scelta su un AVL o un BST). Tuttavia, lo spazio grafico dedicato alla visualizzazione ! viene utilizzato per fornire all'utente un dettagliato report sui test effettuati. \begin{figure}[htbp] \begin{center} *************** *** 409,415 **** 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 \begin{center} --- 423,432 ---- 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{figure}[htbp] \begin{center} ! \includegraphics[height=220pt]{ins_casuale} \end{center} + \caption {Inserimento di una sequenza di valori casuali} + \end{figure} \newpage \begin{center} *************** *** 449,452 **** --- 466,470 ---- \end{tabular} \end{center} + \begin{table} \begin{center} \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} *************** *** 476,481 **** 490000&5.310000&2.120000\\ \hline ! \end{tabular} \end{center} --- 494,501 ---- 490000&5.310000&2.120000\\ \hline ! \end{tabular} \end{center} + \caption{Tempo di elaborazione in relazione con la dimensione di un dati di input casuali} + \end{table} *************** *** 492,500 **** Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maggiore rispetto ad un andamento lineare e con una pendenza molto elevata e crescente facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. ! \begin{center} \includegraphics[width=420pt]{ins_crescente} \end{center} \newpage \begin{center} \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} --- 512,523 ---- Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maggiore rispetto ad un andamento lineare e con una pendenza molto elevata e crescente facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. ! \begin{figure} \begin{center} \includegraphics[width=420pt]{ins_crescente} \end{center} + \caption{Tempo di elaborazione in relazione con un input di dati sempre crescenti} + \end{figure} \newpage + \begin{table} \begin{center} \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} *************** *** 524,528 **** \end{tabular} \end{center} ! \section{Cancellazione di una sequenza di valori casuali} --- 547,552 ---- \end{tabular} \end{center} ! \caption{Tempo di elaborazione in relazione con la dimensione di un dati di input sempre crescente} ! \end{table} \section{Cancellazione di una sequenza di valori casuali} *************** *** 533,541 **** Anche in questo caso come in quello del paragrafo \ref{ins_cas} l'implementazione BST risulta leggermente pi\`u performante rimanendo asintoticamente identica. I motivi perché ci\`o accade sono gli stessi enunciati in precedenza. ! \begin{center} \includegraphics[width=360pt]{canc_casuale} \end{center} ! %\newpage \begin{center} \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} --- 557,568 ---- Anche in questo caso come in quello del paragrafo \ref{ins_cas} l'implementazione BST risulta leggermente pi\`u performante rimanendo asintoticamente identica. I motivi perché ci\`o accade sono gli stessi enunciati in precedenza. ! \begin{figure} \begin{center} \includegraphics[width=360pt]{canc_casuale} \end{center} ! \caption{Tempo di elaborazione per la cancellazione di valori casuali} ! \end{figure} ! ! \begin{table} \begin{center} \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} *************** *** 564,567 **** --- 591,598 ---- \end{tabular} \end{center} + \caption{Tempo di elaborazione in relazione con la cancellazione di un dati di input casuali} + \end{table} + + \newpage \section{Cancellazione di una sequenza di valori decrescenti} *************** *** 577,586 **** sensibilmente superiore ad un costo lineare. ! Per le stesse considerazione fatte nel paragrafo \ref{ins_crescente} l'iplementazione AVL offre prestazioni paragonabili a quelle che si ottengono nel caso medio. 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}|} --- 608,621 ---- sensibilmente superiore ad un costo lineare. ! Per le stesse considerazione fatte nel paragrafo \ref{ins_crescente} l'implementazione AVL offre prestazioni paragonabili a quelle che si ottengono nel caso medio. 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{figure} \begin{center} \includegraphics[width=360pt]{canc_crescente} \end{center} + \caption{Andamento del tempo di cancellazione di un dati di input decrescenti} + \end{figure} + \begin{table} \begin{center} \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} *************** *** 609,612 **** --- 644,649 ---- \end{tabular} \end{center} + \caption{Tempo di elaborazione in relazione con la cacellazione di un dati di input decrescenti} + \end{table} \begin{thebibliography}{99} |
|
From: Patrizio B. <het...@us...> - 2004-09-21 17:17:28
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv4822 Modified Files: relazione.dvi relazione.pdf relazione.tex Log Message: fixed double png inclusion Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.11 retrieving revision 1.12 diff -C2 -d -r1.11 -r1.12 Binary files /tmp/cvsXE4yWY and /tmp/cvs7LkOjJ differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.14 retrieving revision 1.15 diff -C2 -d -r1.14 -r1.15 Binary files /tmp/cvspLZdgH and /tmp/cvsLRV6Rr differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.20 retrieving revision 1.21 diff -C2 -d -r1.20 -r1.21 *** relazione.tex 21 Sep 2004 14:34:32 -0000 1.20 --- relazione.tex 21 Sep 2004 17:17:15 -0000 1.21 *************** *** 287,302 **** \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] - \begin{center} - \includegraphics[height=420pt,angle=90]{application} - \end{center} - \caption{Applicazione} - \label{fig:applicazione2} - \end{figure} - - \newpage - \section{Compilazione ed utilizzo} Il codice è distribuito sotto licenza GPL e include commenti esplicativi per tutte le funzioni. --- 287,290 ---- |
|
From: Patrizio B. <het...@us...> - 2004-09-21 14:34:57
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv2580 Modified Files: relazione.dvi relazione.pdf relazione.tex Log Message: last commit (i hope) Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.10 retrieving revision 1.11 diff -C2 -d -r1.10 -r1.11 Binary files /tmp/cvs8LFzZd and /tmp/cvsk2TJMe differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.13 retrieving revision 1.14 diff -C2 -d -r1.13 -r1.14 Binary files /tmp/cvsqnBw8u and /tmp/cvsKMn80v differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.19 retrieving revision 1.20 diff -C2 -d -r1.19 -r1.20 *** relazione.tex 21 Sep 2004 11:40:32 -0000 1.19 --- relazione.tex 21 Sep 2004 14:34:32 -0000 1.20 *************** *** 170,177 **** \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. ! Se il nodo da eliminare è un foglia, si può procedere cone una rimozione diretta. ! Se il nodo da eliminare ha entrambi i figli è necessario effettuare uno swap con il suo successore (in questo caso sicuramente nel sottoalbero destro, un nodo foglia per definizione) e poi eliminarlo: in questo caso è possibile che si siano sbilanciati i nodi appartenenti al cammino che va dal nodo da eliminare al suo successore. ! 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) --- 170,188 ---- \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. ! Se il nodo da eliminare è un foglia, si può procedere cone una rimozione diretta, non avendo nodi figlio non ci sono ! ulteriori problemi da risolvere del tipo bilanciamento dei sottoalberi o swap. Se da una parte non ci sono problemi, ! la cancellazione di una foglia, rendendo un ramo più corto di un'unità, può portare ad un sbilanciamento dei nodi ! genitore e di livello superiore. ! Se il nodo da eliminare ha entrambi i figli è necessario effettuare uno swap con il suo successore. In questo caso il ! successore sarà sicuramente nel sottoalbero destro, e sarà un nodo foglia per la stessa definizione di successore; ! una volta effettuato lo swap, collegati i figli del nodo iniziale al successore si può procedere nell'eliminazione. ! Dopo lo swap infatti il nodo originale sarà diventato una foglia (e quindi valgono le considerazioni precedenti). ! Tuttavia in questo caso è possibile che si siano sbilanciati i nodi appartenenti al cammino che va dal nodo da ! eliminare al suo successore. ! E' quindi necessario ripetere gli stessi controlli di cui si è parlato in precedenza nel paragrafo relativo agli ! inserimenti: partire dal nodo più basso del ramo interessato dalla cancellazione 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: si possono sbilanciare i nodi ! che avevano un Fdb pari a $+/- 1$. \begin{itemize} \item Caso $-1$: Si sbilancia se viene eliminato un nodo nel sotto albero sinistro (l'albero si sbilancia verso destra) |
|
From: Patrizio B. <het...@us...> - 2004-09-21 11:41:09
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv908 Modified Files: TODO Log Message: delete: done! Index: TODO =================================================================== RCS file: /cvsroot/avl/avl/TODO,v retrieving revision 1.12 retrieving revision 1.13 diff -C2 -d -r1.12 -r1.13 *** TODO 20 Sep 2004 12:50:50 -0000 1.12 --- TODO 21 Sep 2004 11:40:29 -0000 1.13 *************** *** 3,8 **** - fixare il problema del loop infinito + swap se il num di modifiche è alto e l'albero è piccolo. problema di STL! - Documentazione: - - review --- 3,6 ---- |
|
From: Patrizio B. <het...@us...> - 2004-09-21 11:40:43
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv908/docs Modified Files: relazione.dvi relazione.pdf relazione.tex Log Message: delete: done! Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.9 retrieving revision 1.10 diff -C2 -d -r1.9 -r1.10 Binary files /tmp/cvsCs580U and /tmp/cvshGqmPw differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.12 retrieving revision 1.13 diff -C2 -d -r1.12 -r1.13 Binary files /tmp/cvsfxu8ch and /tmp/cvsTq3D9S differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.18 retrieving revision 1.19 diff -C2 -d -r1.18 -r1.19 *** relazione.tex 20 Sep 2004 12:50:51 -0000 1.18 --- relazione.tex 21 Sep 2004 11:40:32 -0000 1.19 *************** *** 170,173 **** --- 170,175 ---- \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. + Se il nodo da eliminare è un foglia, si può procedere cone una rimozione diretta. + Se il nodo da eliminare ha entrambi i figli è necessario effettuare uno swap con il suo successore (in questo caso sicuramente nel sottoalbero destro, un nodo foglia per definizione) e poi eliminarlo: in questo caso è possibile che si siano sbilanciati i nodi appartenenti al cammino che va dal nodo da eliminare al suo successore. 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. |
|
From: Patrizio B. <het...@us...> - 2004-09-21 11:40:43
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv908/src Modified Files: avlt.cpp Log Message: delete: done! Index: avlt.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.cpp,v retrieving revision 1.17 retrieving revision 1.18 diff -C2 -d -r1.17 -r1.18 *** avlt.cpp 20 Sep 2004 12:50:51 -0000 1.17 --- avlt.cpp 21 Sep 2004 11:40:32 -0000 1.18 *************** *** 328,332 **** // Il metodo consiste nella ricerca del nodo da eliminare tramite un algoritmo ricorsivo. Una volta trovato il nodo si elimina utilizzando un algoritmo simile a quello dei BST. Durante l'eliminazione l'albero potrebbe essersi sbilanciato lungo tutto il cammino che va dalla radice alla posizione del nodo da eliminare. Nel caso in cui il nodo da eliminare ha entrambi i figli l'albero potrebbe sbilanciarsi nel cammino che va dal nodo da eliminare ed il suo successore. ! Avlt * aux, *aux1, *aux2; aux1 = aux2 = NULL; aux = this; --- 328,332 ---- // Il metodo consiste nella ricerca del nodo da eliminare tramite un algoritmo ricorsivo. Una volta trovato il nodo si elimina utilizzando un algoritmo simile a quello dei BST. Durante l'eliminazione l'albero potrebbe essersi sbilanciato lungo tutto il cammino che va dalla radice alla posizione del nodo da eliminare. Nel caso in cui il nodo da eliminare ha entrambi i figli l'albero potrebbe sbilanciarsi nel cammino che va dal nodo da eliminare ed il suo successore. ! Avlt *aux, *aux1, *aux2; aux1 = aux2 = NULL; aux = this; |
|
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} |
|
From: Patrizio B. <het...@us...> - 2004-09-20 12:51:01
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv25341/src Modified Files: avl.cpp avlt.cpp test.cpp Log Message: added comments to code, added a pointer check added deletion in the relation. just a code bug left! Index: avlt.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.cpp,v retrieving revision 1.16 retrieving revision 1.17 diff -C2 -d -r1.16 -r1.17 *** avlt.cpp 19 Sep 2004 17:43:47 -0000 1.16 --- avlt.cpp 20 Sep 2004 12:50:51 -0000 1.17 *************** *** 19,29 **** #include "avlt.h" ! /* ! Avlt::Avlt() ! : Bst() ! { ! Avlt( 0,0 ); ! } ! */ Avlt::Avlt(int s ,int val) : Bst(val) --- 19,23 ---- #include "avlt.h" ! Avlt::Avlt(int s ,int val) : Bst(val) Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.23 retrieving revision 1.24 diff -C2 -d -r1.23 -r1.24 *** avl.cpp 18 Sep 2004 20:06:39 -0000 1.23 --- avl.cpp 20 Sep 2004 12:50:51 -0000 1.24 *************** *** 30,33 **** --- 30,34 ---- using namespace std; + //variabili shared int choice=0; int base_tree=10000; *************** *** 60,68 **** } void shutdown_window() { ! gtk_widget_destroy(node_list); ! node_list=nodelist; gtk_paned_add1 (GTK_PANED (vpaned1), node_list); gtk_widget_show (node_list); --- 61,71 ---- } + //viene richiamata alla chiusura della finestra popup per aggiornare la mail window void shutdown_window() { ! gtk_widget_destroy(node_list); //cancella la vecchia lista ! node_list=nodelist; //punta alla nuova lista + //finalizza la nuova lista e la mostra gtk_paned_add1 (GTK_PANED (vpaned1), node_list); gtk_widget_show (node_list); *************** *** 71,74 **** --- 74,78 ---- } + //crea una finestra popup con il nuovo albero dopo l'update void popup_window(int kind,char* operation="",int value=9999999){ *************** *** 97,105 **** gtk_container_set_border_width (GTK_CONTAINER (popup_window), 15); ! //crea i due pannelli verticali pane = gtk_vpaned_new (); gtk_container_add (GTK_CONTAINER (popup_window), pane); gtk_widget_show (pane); gtk_paned_add1 (GTK_PANED (pane), temp_node_list); gtk_widget_show (temp_node_list); --- 101,110 ---- gtk_container_set_border_width (GTK_CONTAINER (popup_window), 15); ! //crea il pannello verticale pane = gtk_vpaned_new (); gtk_container_add (GTK_CONTAINER (popup_window), pane); gtk_widget_show (pane); + // vi aggiunge la lista gtk_paned_add1 (GTK_PANED (pane), temp_node_list); gtk_widget_show (temp_node_list); *************** *** 107,118 **** } void test_single_operation() { int value=0; GtkWidget* dialog; ! value=gtk_spin_button_get_value_as_int(GTK_SPIN_BUTTON(spinbutton3)); switch(choice) { ! case 2: dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You must choice AVL or BST tree test"); gtk_dialog_run (GTK_DIALOG (dialog)); --- 112,127 ---- } + /* + effettua singoli test, come da input dell'utente + effettua anche controlli di inizializzazione + */ void test_single_operation() { int value=0; GtkWidget* dialog; ! value=gtk_spin_button_get_value_as_int(GTK_SPIN_BUTTON(spinbutton3)); //prende il valore da inserire/cancellare switch(choice) { ! case 2: //non si può fare se si è scelto il test comparativo! dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You must choice AVL or BST tree test"); gtk_dialog_run (GTK_DIALOG (dialog)); *************** *** 121,125 **** case 1: ! if (aux_bst==NULL) { dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You must initialise a BST tree before!"); gtk_dialog_run (GTK_DIALOG (dialog)); --- 130,134 ---- case 1: ! if (aux_bst==NULL) { //non inizializzato dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You must initialise a BST tree before!"); gtk_dialog_run (GTK_DIALOG (dialog)); *************** *** 129,136 **** if (insert) { aux_bst->insert(value); ! popup_window(1,"insertion",value ); } else { ! if (aux_bst->nodes() <2) { dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You can't delete, that's onlt one node left in the BST tree!"); gtk_dialog_run (GTK_DIALOG(dialog)); --- 138,145 ---- if (insert) { aux_bst->insert(value); ! popup_window(1,"insertion",value ); //popup il nuovo albero } else { ! if (aux_bst->nodes() <2) { //se c'è solo la root non fa cancellare dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You can't delete, that's onlt one node left in the BST tree!"); gtk_dialog_run (GTK_DIALOG(dialog)); *************** *** 146,150 **** case 0: ! if (aux_avl==NULL) { dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You must initialise an AVL tree before!"); gtk_dialog_run (GTK_DIALOG (dialog)); --- 155,159 ---- case 0: ! if (aux_avl==NULL) { //non inizializzato dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You must initialise an AVL tree before!"); gtk_dialog_run (GTK_DIALOG (dialog)); *************** *** 154,161 **** if (insert) { aux_avl=aux_avl->insert(value); ! popup_window(0,"insertion", value); } else { ! if (aux_avl->nodes() <2) { dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You can't delete, that's only one node left in the AVL tree!"); gtk_dialog_run (GTK_DIALOG(dialog)); --- 163,170 ---- if (insert) { aux_avl=aux_avl->insert(value); ! popup_window(0,"insertion", value); //popup il nuovo albero } else { ! if (aux_avl->nodes() <2) { //se c'è solo la root non fa cancellare dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_ERROR, GTK_BUTTONS_CLOSE, "You can't delete, that's only one node left in the AVL tree!"); gtk_dialog_run (GTK_DIALOG(dialog)); *************** *** 174,177 **** --- 183,187 ---- } + // servono per gestire i radio box void ins_select() { insert=true; *************** *** 193,197 **** // 1= test bst // 2= test comparativo ! /* if (base_tree<upperbound) { --- 203,211 ---- // 1= test bst // 2= test comparativo ! ! /* se il numero dei cambiamenti è superiore al numero dei nodi dell'albero ! si potrebbe verificare problemi dovuti all'uso delle STL. ! questo check li bypassa ! */ if (base_tree<upperbound) { *************** *** 205,210 **** } - */ if (choice==0) { prova = new Test(0,upperbound,base_tree); --- 219,224 ---- } + // scelta dell'albero avl if (choice==0) { prova = new Test(0,upperbound,base_tree); *************** *** 214,217 **** --- 228,232 ---- } + // scelta dell'albero bst if (choice==1) { *************** *** 222,225 **** --- 237,241 ---- } + //test comparativo, non visualizza gli alberi, ma il log report if (choice==2) { *************** *** 304,307 **** --- 320,329 ---- scanf("%d",&upperbound); + + /* se il numero dei cambiamenti è superiore al numero dei nodi dell'albero + si potrebbe verificare problemi dovuti all'uso delle STL. + questo check li bypassa + */ + if (base_tree<upperbound) { upperbound=base_tree-1; *************** *** 363,367 **** gtk_widget_show (vpaned2); ! //crea cinque contenitori orizzontali box1 = gtk_vbox_new (FALSE, 0); gtk_container_add (GTK_CONTAINER (vpaned2), box1); --- 385,389 ---- gtk_widget_show (vpaned2); ! //crea sei contenitori orizzontali box1 = gtk_vbox_new (FALSE, 0); gtk_container_add (GTK_CONTAINER (vpaned2), box1); *************** *** 449,452 **** --- 471,475 ---- gtk_widget_show (label); + //scelta di inserimento o cancellazione button = gtk_radio_button_new_with_label (NULL, "Insert"); g_signal_connect (G_OBJECT (button), "toggled", G_CALLBACK (ins_select),G_OBJECT (button)); Index: test.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/test.cpp,v retrieving revision 1.16 retrieving revision 1.17 diff -C2 -d -r1.16 -r1.17 *** test.cpp 17 Sep 2004 14:16:11 -0000 1.16 --- test.cpp 20 Sep 2004 12:50:51 -0000 1.17 *************** *** 26,30 **** } ! Test::~Test() { if(result_log) free(result_log); --- 26,30 ---- } ! //cancella il log Test::~Test() { if(result_log) free(result_log); *************** *** 58,70 **** #endif ! srand ( time(NULL) ); if (avlt && kind==0) { ! start = clock(); for (int i=0;i<base_limit;i++) { random=rand()%(tree_dimensions*10); avlt=avlt->insert(random); } ! end = clock(); ! init_timer = ((double) (end - start)) / CLOCKS_PER_SEC; #ifndef GUI printf("AVL Initialization of %d items tree took %lf seconds\n",base_limit,init_timer); --- 58,71 ---- #endif ! srand ( time(NULL) ); //inizializza il seme random if (avlt && kind==0) { ! start = clock(); //prende il tempo di inizio for (int i=0;i<base_limit;i++) { random=rand()%(tree_dimensions*10); avlt=avlt->insert(random); } ! end = clock(); //prende il tempo di fine ! init_timer = ((double) (end - start)) / CLOCKS_PER_SEC; //calcola i secondi impiegati ! //funzione di report #ifndef GUI printf("AVL Initialization of %d items tree took %lf seconds\n",base_limit,init_timer); *************** *** 77,87 **** if (bst && kind==1) { ! start = clock(); for (int i=0;i<base_limit;i++) { random=rand()%(tree_dimensions*10); bst->insert(random); } ! end = clock(); ! init_timer = ((double) (end - start)) / CLOCKS_PER_SEC; #ifndef GUI printf("BST Initialization of %d items tree took %lf seconds\n",base_limit,init_timer); --- 78,89 ---- if (bst && kind==1) { ! start = clock(); //prende il tempo di inizio for (int i=0;i<base_limit;i++) { random=rand()%(tree_dimensions*10); bst->insert(random); } ! end = clock(); //prende il tempo di fine ! init_timer = ((double) (end - start)) / CLOCKS_PER_SEC; //calcola i secondi impiegati ! //funzione di report #ifndef GUI printf("BST Initialization of %d items tree took %lf seconds\n",base_limit,init_timer); *************** *** 115,118 **** --- 117,124 ---- start=clock(); for (int i=0;i<upper_limit;i++) { + /* + estrae un numero e lo normalizza alle dimensioni dell'albero*10 + estrare un numero: se è pari inserisce, altrimenti cancella + */ random=rand()%(tree_dimensions*10); decision=rand()%2; *************** *** 122,126 **** insert_counter++; } ! else if (!insertion_list.empty()){ random_erase=rand()%insertion_list.size(); --- 128,132 ---- insert_counter++; } ! else if (!insertion_list.empty() && avlt){ random_erase=rand()%insertion_list.size(); *************** *** 129,133 **** erase_counter++; } ! else waste++; } --- 135,139 ---- erase_counter++; } ! else waste++; //non si è potuto cancellare } *************** *** 164,167 **** --- 170,177 ---- start=clock(); for (int i=0;i<upper_limit;i++) { + /* + estrae un numero e lo normalizza alle dimensioni dell'albero*10 + estrare un numero: se è pari inserisce, altrimenti cancella + */ random=rand()%(tree_dimensions*10); decision=rand()%2; *************** *** 171,175 **** insert_counter++; } ! else if (!insertion_list.empty()){ random_erase=rand()%insertion_list.size(); --- 181,185 ---- insert_counter++; } ! else if (!insertion_list.empty() && bst){ random_erase=rand()%insertion_list.size(); *************** *** 177,181 **** insertion_list.erase(insertion_list.begin()+random_erase); erase_counter++; ! } else waste++; } end=clock(); --- 187,191 ---- insertion_list.erase(insertion_list.begin()+random_erase); erase_counter++; ! } else waste++; //non si è potuto cancellare } end=clock(); *************** *** 206,215 **** avlt=new Avlt(); ! msg=(char*)malloc(400); ! Test_Init(base_tree_size,1); //bst temp_timer=getInitTimer(); ! sleep(2); ! Test_Init(base_tree_size,0); //avl sprintf(buffer,"\nInit Result:\nBST -> %lf, AVL -> %lf\n",temp_timer,getInitTimer()); --- 216,225 ---- avlt=new Avlt(); ! msg=(char*)malloc(400); //400 è più che sufficiente per la stringa di ritorno ! Test_Init(base_tree_size,1); //inizializza un bst temp_timer=getInitTimer(); ! sleep(2); //così si resetta scheduler, il seme random eccc ! Test_Init(base_tree_size,0); //inizializza un avl sprintf(buffer,"\nInit Result:\nBST -> %lf, AVL -> %lf\n",temp_timer,getInitTimer()); |
|
From: Patrizio B. <het...@us...> - 2004-09-20 12:50:59
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv25341 Modified Files: TODO Log Message: added comments to code, added a pointer check added deletion in the relation. just a code bug left! Index: TODO =================================================================== RCS file: /cvsroot/avl/avl/TODO,v retrieving revision 1.11 retrieving revision 1.12 diff -C2 -d -r1.11 -r1.12 *** TODO 19 Sep 2004 17:43:32 -0000 1.11 --- TODO 20 Sep 2004 12:50:50 -0000 1.12 *************** *** 1,10 **** Codice: ! - fixare il problema del loop infinito + swap se il num di modifiche è alto e l'albero è piccolo Documentazione: ! - aggiungere la cancellazione in dettaglio ! ! - Aggiustare le posizioni delle immagini nei primi 3 capitoli (il 4 già sta messo bene) --- 1,8 ---- Codice: ! - fixare il problema del loop infinito + swap se il num di modifiche è alto e l'albero è piccolo. problema di STL! Documentazione: ! - review |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-19 17:44:12
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26298 Modified Files: TODO Log Message: Index: TODO =================================================================== RCS file: /cvsroot/avl/avl/TODO,v retrieving revision 1.10 retrieving revision 1.11 diff -C2 -d -r1.10 -r1.11 *** TODO 18 Sep 2004 20:06:28 -0000 1.10 --- TODO 19 Sep 2004 17:43:32 -0000 1.11 *************** *** 8,12 **** - aggiungere la cancellazione in dettaglio ! - pulire una frase che dice (....) nel capitolo conclusioni ! ! - levare il titolo in alto del capito che si sovrappone in certi punti (capitolo applicazione e conclusione) --- 8,10 ---- - aggiungere la cancellazione in dettaglio ! - Aggiustare le posizioni delle immagini nei primi 3 capitoli (il 4 già sta messo bene) |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-19 17:43:57
|
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} |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-19 17:43:56
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26298/src Modified Files: avlt.cpp Log Message: Index: avlt.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avlt.cpp,v retrieving revision 1.15 retrieving revision 1.16 diff -C2 -d -r1.15 -r1.16 *** avlt.cpp 17 Sep 2004 11:57:34 -0000 1.15 --- avlt.cpp 19 Sep 2004 17:43:47 -0000 1.16 *************** *** 64,68 **** } ! /* Calcola il FdB del nodo corrente*/ int Avlt::getFdb() { --- 64,68 ---- } ! /* Calcola e restituisce il FdB del nodo corrente*/ int Avlt::getFdb() { |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-19 10:46:58
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv32187/docs Modified Files: relazione.dvi relazione.pdf Log Message: Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 Binary files /tmp/cvsVBGPKa and /tmp/cvseRgPlV differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.9 retrieving revision 1.10 diff -C2 -d -r1.9 -r1.10 Binary files /tmp/cvsdP2SNt and /tmp/cvs59MUve differ |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-19 10:38:22
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv30071/docs Modified Files: relazione.dvi relazione.pdf Log Message: Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -d -r1.6 -r1.7 Binary files /tmp/cvsO4EHWT and /tmp/cvso8zMjh differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.8 retrieving revision 1.9 diff -C2 -d -r1.8 -r1.9 Binary files /tmp/cvsmkLrU4 and /tmp/cvsxl0Ims differ |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-19 10:29:57
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv28133 Modified Files: relazione.dvi relazione.pdf relazione.tex Log Message: Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.5 retrieving revision 1.6 diff -C2 -d -r1.5 -r1.6 Binary files /tmp/cvstKt8CY and /tmp/cvsRXlnT8 differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 Binary files /tmp/cvsKDbpZm and /tmp/cvsq8CIqx differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.15 retrieving revision 1.16 diff -C2 -d -r1.15 -r1.16 *** relazione.tex 19 Sep 2004 10:07:27 -0000 1.15 --- relazione.tex 19 Sep 2004 10:29:44 -0000 1.16 *************** *** 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)$. ! Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maniera lineare con una pendenza molto elevata facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. \begin{center} --- 420,431 ---- 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) ! \]. ! ! Per quanto riguarda gli AVL ogni inserimento ha costo $O\left(h\right)$ dove $h$ \`e l'altezza dell'albero. Visto che si fanno $n$ inserimenti il costo sar\`a $O\left(nh\right)$. L'altezza dell'albero varia in base alla sua dimensione ma \`e sempre possibile maggiorarla con $\log\left(n\right)$ e quindi si pu\`o affermare che il costo totale per l'implementazione AVL sar\`a al pi\`u $O\left(n\log\left(n\right)\right)$. ! ! Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maggiore rispetto ad un andamento lineare e con una pendenza molto elevata e crescente facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. \begin{center} |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-19 10:07:36
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv23970 Modified Files: relazione.dvi relazione.tex Log Message: Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.6 retrieving revision 1.7 diff -C2 -d -r1.6 -r1.7 Binary files /tmp/cvs4cAmvO and /tmp/cvsywobUx differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.14 retrieving revision 1.15 diff -C2 -d -r1.14 -r1.15 *** relazione.tex 18 Sep 2004 20:06:39 -0000 1.14 --- relazione.tex 19 Sep 2004 10:07:27 -0000 1.15 *************** *** 303,307 **** - \chapter{Conclusioni}\label{Conclusioni} Nei test effettuati, ripetendo numerose volte la costruzione di alberi AVL e BST, e poi applicandovi numerose modifiche casuali di tipo inserimento e cancellazione si è notato come la differenza tra le due implementazioni sia davvero minima e poco percettibile. Se si considera la differenza di costi (uno lineare, l'altro logaritmico) questo risultato appare impossibile. --- 303,306 ---- *************** *** 339,343 **** \section{Inserimento di una sequenza di valori casuali}\label{ins_cas} ! L'inserimento di una sequenza di valori casuali \`e il caso che pi\`u si avvicina a quello medio. In questo caso infatti i valori della sequenza vengono scelti casualmente tra quelli di un insieme finito di cardinalit\`a $k$ in modo che la probabilit\`a che venga utilizzata una tra le possibili permutazioni degli elementi di tale insieme sia costante e pari a $\frac{1}{k!}$ il che equivale a dire che ogni sequenza di input \`e equiprobabile. Dal grafico si nota che le curve crescono linearmente con il crescere della dimensione dell'input. Il risultato di certo non stupisce per quanto riguarda gli alberi BST. L'andamento della curva relativa agli AVL \`e dovuto al fatto che, anche se l'operazione predominante nell'inserimento \`e quella di ricerca, ci sono altre operazioni che influiscono in maniera minima (con costo cio\`e di $O\left(1\right)$ ) ma significativa sul costo totale. Tali operazioni sono quelle di rotazione e di aggiornamento del fattore di bilanciamento in ogni nodo. --- 338,342 ---- \section{Inserimento di una sequenza di valori casuali}\label{ins_cas} ! L'inserimento di una sequenza di valori casuali \`e il caso che pi\`u si avvicina a quello medio. In questo caso infatti i valori della sequenza vengono scelti casualmente tra quelli di un insieme finito di cardinalit\`a $n$ in modo che la probabilit\`a che venga utilizzata una tra le possibili permutazioni degli elementi di tale insieme sia costante e pari a $\frac{1}{n!}$ il che equivale a dire che ogni sequenza di input \`e equiprobabile. Dal grafico si nota che le curve crescono linearmente con il crescere della dimensione dell'input. Il risultato di certo non stupisce per quanto riguarda gli alberi BST. L'andamento della curva relativa agli AVL \`e dovuto al fatto che, anche se l'operazione predominante nell'inserimento \`e quella di ricerca, ci sono altre operazioni che influiscono in maniera minima (con costo cio\`e di $O\left(1\right)$ ) ma significativa sul costo totale. Tali operazioni sono quelle di rotazione e di aggiornamento del fattore di bilanciamento in ogni nodo. *************** *** 345,349 **** \`E interessante notare che la curva relativa agli AVL, oltre che avere un andamento simile a quella relativa ai BST, rispetto a quest'ultima presenta anche una pendenza maggiore, il che significa che il tempo di esecuzione, al crescere della dimensione dell'input, cresce pi\`u velocemente nell'implementazione con AVL piuttosto che in quella con i BST. ! 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)$ (.........................) 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} --- 344,348 ---- \`E interessante notare che la curva relativa agli AVL, oltre che avere un andamento simile a quella relativa ai BST, rispetto a quest'ultima presenta anche una pendenza maggiore, il che significa che il tempo di esecuzione, al crescere della dimensione dell'input, cresce pi\`u velocemente nell'implementazione con AVL piuttosto che in quella con i BST. ! 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} *************** *** 417,423 **** ! \section{Inserimento di una sequenza di valori crescenti} ! 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'inseriemnto di un nuovo valore viene fatto sempre in coda e che quindi presenta un costo di inserimento pari a $O\left(n\right)$ Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maniera lineare con una pendenza molto elevata facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. --- 416,422 ---- ! \section{Inserimento di una sequenza di valori crescenti}\label{ins_crescente} ! 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)$. Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maniera lineare con una pendenza molto elevata facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. *************** *** 495,498 **** --- 494,509 ---- \end{center} \section{Cancellazione di una sequenza di valori decrescenti} + + Il test in questione consiste nella cancellazione di una sequenza di $n$ valori in un albero construito nel modo indicato nel paragrafo \ref{ins_crescente}. La sequenza di valori da cancellare \`e decrescente parte cio\`e dal valore pi\`u grande presente nell'albero e finisce con quello pi\`u piccolo. In questo modo l'implemetazione BST \`e costretta a lavorare nelle condizioni peggiori \footnote{un caso ulteriormente peggiore \`e quello in cui si cancella una sequenza di elementi tutti maggiori del massimo elemento presente nell'albero. In tal caso infattti la ricerca dell'elemento non avrebbe mai esito positivo ed ogni cancellazione avremme costo $cn$. \`E facile verificare come in questo caso la cancellazione di una tale sequenza di $m$ elementi costi $O\left(mn\right)$} infatti per come \`e costruito l'albero il valore pi\`u grande \`e l'unica foglia dell'albero e per cercarlo occorre quindi visitare tutti i nodi ottenendo un costo di $O\left(n\right)$. + + 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. + + Per le stesse considerazione fatte nel paragrafo \ref{ins_crescente} l'iplementazione AVL offre prestazioni paragonabili a quelle che si ottengono nel caso medio. + + 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} *************** *** 526,528 **** --- 537,550 ---- \end{center} + \begin{thebibliography}{99} + \bibitem{AVL} G.M. Adelson-Velskii G.M. , Y.M. Landis, + An algorithm for the organization of information + {\it Dokl. Akad. Nauk}, + SSr, 146, 263-266, 1962 + \bibitem{cormen} T.H. Cormen, C.E. Leiserson, R.L.Rivest, + Introduction to Algorithms, 2nd ed. + {\it MIT Press}, + 1999 + \end{thebibliography} + \end{document} |
|
From: Patrizio B. <het...@us...> - 2004-09-18 20:06:49
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv5617/src Modified Files: avl.cpp Log Message: wellllaaaaa! Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.22 retrieving revision 1.23 diff -C2 -d -r1.22 -r1.23 *** avl.cpp 17 Sep 2004 14:12:14 -0000 1.22 --- avl.cpp 18 Sep 2004 20:06:39 -0000 1.23 *************** *** 193,197 **** // 1= test bst // 2= test comparativo ! if (base_tree<upperbound) { --- 193,197 ---- // 1= test bst // 2= test comparativo ! /* if (base_tree<upperbound) { *************** *** 205,209 **** } ! if (choice==0) { --- 205,209 ---- } ! */ if (choice==0) { |
|
From: Patrizio B. <het...@us...> - 2004-09-18 20:06:49
|
Update of /cvsroot/avl/avl In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv5617 Modified Files: TODO Log Message: wellllaaaaa! Index: TODO =================================================================== RCS file: /cvsroot/avl/avl/TODO,v retrieving revision 1.9 retrieving revision 1.10 diff -C2 -d -r1.9 -r1.10 *** TODO 17 Sep 2004 12:44:15 -0000 1.9 --- TODO 18 Sep 2004 20:06:28 -0000 1.10 *************** *** 1,11 **** Codice: - - fixare il seg fault nella cancellazione della root di un bst. - - fixare il problema del loop infinito + swap se il num di modifiche è alto e l'albero è piccolo Documentazione: - aggiungere la cancellazione in dettaglio ! - aggiungeree un po di valori provati e una tabella (capitolo conclusione) --- 1,12 ---- Codice: - fixare il problema del loop infinito + swap se il num di modifiche è alto e l'albero è piccolo + Documentazione: - aggiungere la cancellazione in dettaglio ! - pulire una frase che dice (....) nel capitolo conclusioni ! ! - levare il titolo in alto del capito che si sovrappone in certi punti (capitolo applicazione e conclusione) |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-18 17:49:12
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv9828 Added Files: canc_casuale.eps canc_casuale.png canc_crescente.eps canc_crescente.png Log Message: --- NEW FILE: canc_crescente.eps --- %!PS-Adobe-3.0 EPSF-3.0 %%Creator: (ImageMagick) %%Title: (canc_crescente.eps) %%CreationDate: (Sat Sep 18 19:32:55 2004) %%BoundingBox: 0 0 1016 716 %%HiResBoundingBox: 0 0 1016 716 %%DocumentData: Clean7Bit %%LanguageLevel: 1 %%Pages: 1 %%EndComments %%BeginDefaults %%EndDefaults %%BeginProlog % % Display a color image. The image is displayed in color on % Postscript viewers or printers that support color, otherwise % it is displayed as grayscale. [...60861 lines suppressed...] DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDC end %%PageTrailer %%Trailer %%EOF --- NEW FILE: canc_crescente.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: canc_casuale.eps --- %!PS-Adobe-3.0 EPSF-3.0 %%Creator: (ImageMagick) %%Title: (canc_casuale.eps) %%CreationDate: (Sat Sep 18 19:25:16 2004) %%BoundingBox: 0 0 1016 716 %%HiResBoundingBox: 0 0 1016 716 %%DocumentData: Clean7Bit %%LanguageLevel: 1 %%Pages: 1 %%EndComments %%BeginDefaults %%EndDefaults %%BeginProlog % % Display a color image. The image is displayed in color on % Postscript viewers or printers that support color, otherwise % it is displayed as grayscale. [...60861 lines suppressed...] DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDC end %%PageTrailer %%Trailer %%EOF --- NEW FILE: canc_casuale.png --- (This appears to be a binary file; contents omitted.) |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-18 17:43:56
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv9695 Modified Files: relazione.dvi relazione.tex Log Message: Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 Binary files /tmp/cvssIXmZB and /tmp/cvsd71kIt differ Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.12 retrieving revision 1.13 diff -C2 -d -r1.12 -r1.13 *** relazione.tex 18 Sep 2004 16:45:19 -0000 1.12 --- relazione.tex 18 Sep 2004 17:43:47 -0000 1.13 *************** *** 11,15 **** \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} ! \makeatletter \usepackage{babel} --- 11,15 ---- \usepackage[T1]{fontenc} \usepackage[latin1]{inputenc} ! \usepackage{fullpage} \makeatletter \usepackage{babel} *************** *** 262,266 **** Va sempre considerato anche l'aspetto delle costanti: utilizzando sequenze di input di dimensioni non eccessivamente elevate, un costo logaritmico, ma con una costante moltiplicativa grande può risultare superiore ad un costo lineare. ! Nei paragrafi seguenti sono riportati e commentati i valori dei tempi di esecuzione espressi in funzione della dimensione dell'input (che nel seguito verr\`a indicata con $n$). Si noter\`a che, per quanto detto sopra, nei casi medi non ci saranno sostanziali differenze tra le due implementazioni. Se invece si forza il software a lavorare in condizioni particolari si notano i vantaggi di utilizzare un algoritmo pi\`u efficiente a scapito delle considerazioni precedenti. \section{Macchina utilizzata} --- 262,266 ---- Va sempre considerato anche l'aspetto delle costanti: utilizzando sequenze di input di dimensioni non eccessivamente elevate, un costo logaritmico, ma con una costante moltiplicativa grande può risultare superiore ad un costo lineare. ! Nei paragrafi seguenti sono riportati e commentati i valori dei tempi di esecuzione espressi in funzione della dimensione dell'input (che nel seguito verr\`a indicata con $n$). Si noter\`a che, per quanto detto sopra, nei casi medi non ci saranno sostanziali differenze tra le due implementazioni. Se invece si forza il software a lavorare in condizioni particolari si notano i vantaggi di utilizzare un algoritmo pi\`u efficiente malgrado le considerazioni precedenti. Proprio a questo sono dovuti i vantaggi che si ottengono ad utilizzare l'implementazione AVL. Tale implementazione infatti mantiene le stesse prestazioni nell'eseguire le tre operazioni principali indipendentemente dalla sequenza di input. \section{Macchina utilizzata} *************** *** 277,281 **** \end{itemize} ! \section{Inserimento di una sequenza di valori casuali} L'inserimento di una sequenza di valori casuali \`e il caso che pi\`u si avvicina a quello medio. In questo caso infatti i valori della sequenza vengono scelti casualmente tra quelli di un insieme finito di cardinalit\`a $k$ in modo che la probabilit\`a che venga utilizzata una tra le possibili permutazioni degli elementi di tale insieme sia costante e pari a $\frac{1}{k!}$ il che equivale a dire che ogni sequenza di input \`e equiprobabile. --- 277,281 ---- \end{itemize} ! \section{Inserimento di una sequenza di valori casuali}\label{ins_cas} L'inserimento di una sequenza di valori casuali \`e il caso che pi\`u si avvicina a quello medio. In questo caso infatti i valori della sequenza vengono scelti casualmente tra quelli di un insieme finito di cardinalit\`a $k$ in modo che la probabilit\`a che venga utilizzata una tra le possibili permutazioni degli elementi di tale insieme sia costante e pari a $\frac{1}{k!}$ il che equivale a dire che ogni sequenza di input \`e equiprobabile. *************** *** 283,291 **** Dal grafico si nota che le curve crescono linearmente con il crescere della dimensione dell'input. Il risultato di certo non stupisce per quanto riguarda gli alberi BST. L'andamento della curva relativa agli AVL \`e dovuto al fatto che, anche se l'operazione predominante nell'inserimento \`e quella di ricerca, ci sono altre operazioni che influiscono in maniera minima (con costo cio\`e di $O\left(1\right)$ ) ma significativa sul costo totale. Tali operazioni sono quelle di rotazione e di aggiornamento del fattore di bilanciamento in ogni nodo. ! \`E interessante notare che la curva relativa agli AVL, oltre che avere un andamento simile a quella relativa ai BST, rispetto a quest'ultima presenta anche una pendenza maggiore, il che significa che il tempo di esecuzone, al crescere della dimensione dell'input, cresce pi\`u velocemente nell'implementazione con AVL piuttosto che in quella con i BST. 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)$ (.........................) 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=420pt]{ins_casuale} \end{center} \newpage --- 283,291 ---- Dal grafico si nota che le curve crescono linearmente con il crescere della dimensione dell'input. Il risultato di certo non stupisce per quanto riguarda gli alberi BST. L'andamento della curva relativa agli AVL \`e dovuto al fatto che, anche se l'operazione predominante nell'inserimento \`e quella di ricerca, ci sono altre operazioni che influiscono in maniera minima (con costo cio\`e di $O\left(1\right)$ ) ma significativa sul costo totale. Tali operazioni sono quelle di rotazione e di aggiornamento del fattore di bilanciamento in ogni nodo. ! \`E interessante notare che la curva relativa agli AVL, oltre che avere un andamento simile a quella relativa ai BST, rispetto a quest'ultima presenta anche una pendenza maggiore, il che significa che il tempo di esecuzione, al crescere della dimensione dell'input, cresce pi\`u velocemente nell'implementazione con AVL piuttosto che in quella con i BST. 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)$ (.........................) 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 *************** *** 304,309 **** 80000&0.630000&0.210000\\ 90000&0.710000&0.240000\\ ! 100000&0.780000&0.290000\\ ! 110000&0.890000&0.280000\\ 120000&1.010000&0.320000\\ 130000&1.110000&0.360000\\ --- 304,309 ---- 80000&0.630000&0.210000\\ 90000&0.710000&0.240000\\ ! 100000&0.780000&0.280000\\ ! 110000&0.890000&0.300000\\ 120000&1.010000&0.320000\\ 130000&1.110000&0.360000\\ *************** *** 312,316 **** 160000&1.390000&0.470000\\ 170000&1.500000&0.560000\\ ! 180000&1.620000&0.560000\\ 190000&1.720000&0.610000\\ 200000&1.850000&0.650000\\ --- 312,316 ---- 160000&1.390000&0.470000\\ 170000&1.500000&0.560000\\ ! 180000&1.620000&0.580000\\ 190000&1.720000&0.610000\\ 200000&1.850000&0.650000\\ *************** *** 340,344 **** 360000&3.730000&1.410000\\ 370000&4.020000&1.380000\\ ! 380000&3.940000&1.450000\\ 390000&4.200000&1.590000\\ 400000&4.220000&1.610000\\ --- 340,344 ---- 360000&3.730000&1.410000\\ 370000&4.020000&1.380000\\ ! 380000&4.100000&1.450000\\ 390000&4.200000&1.590000\\ 400000&4.220000&1.610000\\ *************** *** 376,380 **** 1500&0.010000&0.030000\\ 2000&0.010000&0.060000\\ ! 2500&0.020000&0.130000\\ 3000&0.010000&0.160000\\ 3500&0.010000&0.260000\\ --- 376,380 ---- 1500&0.010000&0.030000\\ 2000&0.010000&0.060000\\ ! 2500&0.010000&0.130000\\ 3000&0.010000&0.160000\\ 3500&0.010000&0.260000\\ *************** *** 396,402 **** ! \section{Inserimento di una sequenza di valori casuali} ! \section{Inserimento di una sequenza di valori decrescenti} \end{document} --- 396,468 ---- ! \section{Cancellazione di una sequenza di valori casuali} ! Per effettuare questo test si \`e prima dovuto costruire un albero in modo casuale seguendo le considerazioni fatte nel paragrafo \ref{ins_cas}. In seguito si \`e eseguita una sequenza di cancellazioni lunga $n$ di elementi presenti nell'albero che ha quindi cancellato tutti i nodi dell'albero. ! ! I risultati evidenziano come non ci sia una differenza rilevante tra le due implemetazioni, infatti entrambe le curve riportate seguono un andamento lineare con una pendenza maggiore nel caso di AVL. ! ! Anche in questo caso come in quello del paragrafo \ref{ins_cas} l'implementazione BST risulta leggermente pi\`u performante rimanendo asintoticamente identica. I motivi perché ci\`o accade sono gli stessi enunciati in precedenza. ! ! \begin{center} ! \includegraphics[width=420pt]{canc_casuale} ! \end{center} ! \newpage ! \begin{center} ! \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} ! \hline ! \textbf{Dimensione dell'input}&\textbf{Tempo Avl (s)}&\textbf{Tempo Bst (s)}\\ ! \hline ! 1000&0.000000&0.000000\\ ! 1500&0.010000&0.000000\\ ! 2000&0.010000&0.000000\\ ! 2500&0.010000&0.010000\\ ! 3000&0.010000&0.010000\\ ! 3500&0.010000&0.010000\\ ! 4000&0.020000&0.010000\\ ! 4500&0.020000&0.010000\\ ! 5000&0.030000&0.020000\\ ! 5500&0.030000&0.020000\\ ! 6000&0.030000&0.020000\\ ! 6500&0.030000&0.030000\\ ! 7000&0.030000&0.030000\\ ! 7500&0.040000&0.030000\\ ! 8000&0.040000&0.030000\\ ! 8500&0.040000&0.040000\\ ! 9000&0.040000&0.040000\\ ! 9500&0.050000&0.040000\\ ! \hline ! \end{tabular} ! \end{center} ! \section{Cancellazione di una sequenza di valori decrescenti} ! \begin{center} ! \includegraphics[width=420pt]{canc_crescente} ! \end{center} ! \newpage ! \begin{center} ! \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} ! \hline ! \textbf{Dimensione dell'input}&\textbf{Tempo Avl (s)}&\textbf{Tempo Bst (s)}\\ ! \hline ! 1000&0.000000&0.000000\\ ! 1500&0.010000&0.010000\\ ! 2000&0.010000&0.020000\\ ! 2500&0.010000&0.040000\\ ! 3000&0.010000&0.050000\\ ! 3500&0.020000&0.060000\\ ! 4000&0.020000&0.080000\\ ! 4500&0.020000&0.090000\\ ! 5000&0.020000&0.120000\\ ! 5500&0.030000&0.150000\\ ! 6000&0.030000&0.170000\\ ! 6500&0.030000&0.200000\\ ! 7000&0.040000&0.250000\\ ! 7500&0.040000&0.340000\\ ! 8000&0.040000&0.380000\\ ! 8500&0.040000&0.420000\\ ! 9000&0.050000&0.490000\\ ! 9500&0.050000&0.550000\\ ! \hline ! \end{tabular} ! \end{center} \end{document} |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-18 16:45:32
|
Update of /cvsroot/avl/avl/docs In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv28906 Modified Files: relazione.dvi relazione.pdf relazione.tex Added Files: ins_casuale.eps ins_casuale.png ins_crescente.eps ins_crescente.png Log Message: --- NEW FILE: ins_crescente.eps --- %!PS-Adobe-3.0 EPSF-3.0 %%Creator: (ImageMagick) %%Title: (ins_crescente.eps) %%CreationDate: (Sat Sep 18 18:36:08 2004) %%BoundingBox: 0 0 1016 716 %%HiResBoundingBox: 0 0 1016 716 %%DocumentData: Clean7Bit %%LanguageLevel: 1 %%Pages: 1 %%EndComments %%BeginDefaults %%EndDefaults %%BeginProlog % % Display a color image. The image is displayed in color on % Postscript viewers or printers that support color, otherwise % it is displayed as grayscale. [...60861 lines suppressed...] DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDC end %%PageTrailer %%Trailer %%EOF --- NEW FILE: ins_crescente.png --- (This appears to be a binary file; contents omitted.) Index: relazione.tex =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.tex,v retrieving revision 1.11 retrieving revision 1.12 diff -C2 -d -r1.11 -r1.12 *** relazione.tex 17 Sep 2004 12:29:45 -0000 1.11 --- relazione.tex 18 Sep 2004 16:45:19 -0000 1.12 *************** *** 1,3 **** ! \documentclass[12pt]{report} \usepackage{enumerate} --- 1,3 ---- ! \documentclass[12pt,fullpage]{report} \usepackage{enumerate} *************** *** 246,261 **** \chapter{Conclusioni}\label{Conclusioni} Nei test effettuati, ripetendo numerose volte la costruzione di alberi AVL e BST, e poi applicandovi numerose modifiche casuali di tipo inserimento e cancellazione si è notato come la differenza tra le due implementazioni sia davvero minima e poco percettibile. Se si considera la differenza di costi (uno lineare, l'altro logaritmico) questo risultato appare impossibile. In realtà il risultato è giustificabile con diversi punti: \begin{itemize} ! \item il generatore di numeri casuali, in realtà non è puramente casuale. E' un limite di quasi tutti i sistemi operativi e processori attuali ! \item la misurazione delle prestazione non è accurata, il programma realizzato è soggetto a scheduler e quindi non è garantito che il sistema operativo assegni al programma le stesse risorse in ogni momento ! \item la quantità di numeri generata e la loro grandezza non è in grado si mettere in seria difficoltà i processori attuali e le differenze di tempo sono minime ! \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} --- 246,402 ---- \chapter{Conclusioni}\label{Conclusioni} Nei test effettuati, ripetendo numerose volte la costruzione di alberi AVL e BST, e poi applicandovi numerose modifiche casuali di tipo inserimento e cancellazione si è notato come la differenza tra le due implementazioni sia davvero minima e poco percettibile. Se si considera la differenza di costi (uno lineare, l'altro logaritmico) questo risultato appare impossibile. + In realtà il risultato è giustificabile con diversi punti: \begin{itemize} ! \item La misurazione delle prestazione non è accurata, il programma realizzato è soggetto a scheduler e quindi non è garantito che il sistema operativo assegni al programma le stesse risorse in ogni momento. ! \item La quantità di numeri generata e la loro grandezza non è in grado si mettere in seria difficoltà i processori attuali e le differenze di tempo sono minime. ! \item L'uso di strutture dati differenti (per l'implementazione con AVL rispetto a quella con BST), 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. + \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} + 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 pi\`u performanti (e talvolta anche più lenti!). ! ! Va sempre considerato anche l'aspetto delle costanti: utilizzando sequenze di input di dimensioni non eccessivamente elevate, un costo logaritmico, ma con una costante moltiplicativa grande può risultare superiore ad un costo lineare. ! ! Nei paragrafi seguenti sono riportati e commentati i valori dei tempi di esecuzione espressi in funzione della dimensione dell'input (che nel seguito verr\`a indicata con $n$). Si noter\`a che, per quanto detto sopra, nei casi medi non ci saranno sostanziali differenze tra le due implementazioni. Se invece si forza il software a lavorare in condizioni particolari si notano i vantaggi di utilizzare un algoritmo pi\`u efficiente a scapito delle considerazioni precedenti. ! ! \section{Macchina utilizzata} ! ! Nell'analizzare i tempi di esecuzione riportati nei paragrafi seguenti è opportuno considerare che essi sono stati ottenuti eseguendo il software sempre sulla stessa macchina ed in condizioni il pi\`u possibile prossime a quelle ideali. ! ! Si \`e cercato cio\`e di tenere in esecuzione solo i processi necessari per l'esecuzione dell'applicativo di test in modo da disporre di un maggior quantitativo di memoria e di non essere soggetti a scheduling da parte del sistema operativo. ! ! La macchina utilizzata \`e cos\`i configurata: ! \begin{itemize} ! \item CPU: AMD Athlon 600 MHz ! \item RAM: 256 Mb 100MHz CL2 ! \item Sistema operativo: Linux v2.6.9-rc2 ! \end{itemize} ! ! \section{Inserimento di una sequenza di valori casuali} ! ! L'inserimento di una sequenza di valori casuali \`e il caso che pi\`u si avvicina a quello medio. In questo caso infatti i valori della sequenza vengono scelti casualmente tra quelli di un insieme finito di cardinalit\`a $k$ in modo che la probabilit\`a che venga utilizzata una tra le possibili permutazioni degli elementi di tale insieme sia costante e pari a $\frac{1}{k!}$ il che equivale a dire che ogni sequenza di input \`e equiprobabile. ! ! Dal grafico si nota che le curve crescono linearmente con il crescere della dimensione dell'input. Il risultato di certo non stupisce per quanto riguarda gli alberi BST. L'andamento della curva relativa agli AVL \`e dovuto al fatto che, anche se l'operazione predominante nell'inserimento \`e quella di ricerca, ci sono altre operazioni che influiscono in maniera minima (con costo cio\`e di $O\left(1\right)$ ) ma significativa sul costo totale. Tali operazioni sono quelle di rotazione e di aggiornamento del fattore di bilanciamento in ogni nodo. ! ! \`E interessante notare che la curva relativa agli AVL, oltre che avere un andamento simile a quella relativa ai BST, rispetto a quest'ultima presenta anche una pendenza maggiore, il che significa che il tempo di esecuzone, al crescere della dimensione dell'input, cresce pi\`u velocemente nell'implementazione con AVL piuttosto che in quella con i BST. ! ! 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)$ (.........................) 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=420pt]{ins_casuale} ! \end{center} ! \newpage ! \begin{center} ! \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} ! \hline ! \textbf{Dimensione dell'input}&\textbf{Tempo Avl (s)}&\textbf{Tempo Bst (s)}\\ ! \hline ! 10000&0.050000&0.020000\\ ! 20000&0.110000&0.040000\\ ! 30000&0.190000&0.070000\\ ! 40000&0.260000&0.080000\\ ! 50000&0.350000&0.110000\\ ! 60000&0.420000&0.130000\\ ! 70000&0.520000&0.170000\\ ! 80000&0.630000&0.210000\\ ! 90000&0.710000&0.240000\\ ! 100000&0.780000&0.290000\\ ! 110000&0.890000&0.280000\\ ! 120000&1.010000&0.320000\\ ! 130000&1.110000&0.360000\\ ! 140000&1.200000&0.420000\\ ! 150000&1.280000&0.440000\\ ! 160000&1.390000&0.470000\\ ! 170000&1.500000&0.560000\\ ! 180000&1.620000&0.560000\\ ! 190000&1.720000&0.610000\\ ! 200000&1.850000&0.650000\\ ! 210000&1.920000&0.670000\\ ! 220000&2.040000&0.690000\\ ! 230000&2.140000&0.760000\\ ! 240000&2.280000&0.790000\\ ! 250000&2.430000&0.890000\\ ! 260000&2.500000&0.900000\\ ! 270000&2.630000&0.950000\\ ! 280000&2.750000&0.990000\\ ! \hline ! \end{tabular} ! \end{center} ! \begin{center} ! \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} ! \hline ! \textbf{Dimensione dell'input}&\textbf{Tempo Avl (s)}&\textbf{Tempo Bst (s)}\\ ! \hline ! 290000&2.910000&1.090000\\ ! 300000&3.030000&1.170000\\ ! 310000&3.260000&1.120000\\ ! 320000&3.290000&1.210000\\ ! 330000&3.410000&1.270000\\ ! 340000&3.480000&1.330000\\ ! 350000&3.610000&1.350000\\ ! 360000&3.730000&1.410000\\ ! 370000&4.020000&1.380000\\ ! 380000&3.940000&1.450000\\ ! 390000&4.200000&1.590000\\ ! 400000&4.220000&1.610000\\ ! 410000&4.370000&1.700000\\ ! 420000&4.480000&1.700000\\ ! 430000&4.670000&1.800000\\ ! 440000&4.830000&1.770000\\ ! 450000&4.990000&1.870000\\ ! 460000&5.020000&1.880000\\ ! 470000&5.150000&1.950000\\ ! 480000&5.370000&2.050000\\ ! 490000&5.310000&2.120000\\ ! \hline ! \end{tabular} ! \end{center} ! ! ! \section{Inserimento di una sequenza di valori crescenti} ! ! 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'inseriemnto di un nuovo valore viene fatto sempre in coda e che quindi presenta un costo di inserimento pari a $O\left(n\right)$ ! ! Il grafico avvalora quanto detto. Infatti la curva relativa agli AVL si presenta con un andamento grossomodo costante, ovvero logaritmico mentre quella relativa ai BST cresce in maniera lineare con una pendenza molto elevata facendo in modo che la prima curva sia sempre minore della seconda anche per dimensioni di input non troppo elevate. ! ! \begin{center} ! \includegraphics[width=420pt]{ins_crescente} ! \end{center} ! \newpage ! \begin{center} ! \begin{tabular}{|p{2.3cm}|p{2cm}|p{2cm}|} ! \hline ! \textbf{Dimensione dell'input}&\textbf{Tempo Avl (s)}&\textbf{Tempo Bst (s)}\\ ! \hline ! 500&0.000000&0.010000\\ ! 1000&0.000000&0.020000\\ ! 1500&0.010000&0.030000\\ ! 2000&0.010000&0.060000\\ ! 2500&0.020000&0.130000\\ ! 3000&0.010000&0.160000\\ ! 3500&0.010000&0.260000\\ ! 4000&0.020000&0.280000\\ ! 4500&0.020000&0.340000\\ ! 5000&0.020000&0.420000\\ ! 5500&0.030000&0.520000\\ ! 6000&0.030000&0.640000\\ ! 6500&0.030000&0.730000\\ ! 7000&0.030000&0.940000\\ ! 7500&0.040000&1.130000\\ ! 8000&0.040000&1.210000\\ ! 8500&0.040000&1.420000\\ ! 9000&0.040000&1.620000\\ ! 9500&0.050000&1.810000\\ ! \hline ! \end{tabular} ! \end{center} ! ! ! \section{Inserimento di una sequenza di valori casuali} ! ! \section{Inserimento di una sequenza di valori decrescenti} ! \end{document} Index: relazione.pdf =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.pdf,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 Binary files /tmp/cvsA2MeHE and /tmp/cvsSWFM4r differ Index: relazione.dvi =================================================================== RCS file: /cvsroot/avl/avl/docs/relazione.dvi,v retrieving revision 1.3 retrieving revision 1.4 diff -C2 -d -r1.3 -r1.4 Binary files /tmp/cvsIHYkCP and /tmp/cvs5lsB5C differ --- NEW FILE: ins_casuale.png --- (This appears to be a binary file; contents omitted.) --- NEW FILE: ins_casuale.eps --- %!PS-Adobe-3.0 EPSF-3.0 %%Creator: (ImageMagick) %%Title: (ins_casuale.eps) %%CreationDate: (Sat Sep 18 18:27:41 2004) %%BoundingBox: 0 0 1016 716 %%HiResBoundingBox: 0 0 1016 716 %%DocumentData: Clean7Bit %%LanguageLevel: 1 %%Pages: 1 %%EndComments %%BeginDefaults %%EndDefaults %%BeginProlog % % Display a color image. The image is displayed in color on % Postscript viewers or printers that support color, otherwise % it is displayed as grayscale. [...60861 lines suppressed...] DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDCDC DCDCDCDCDCDCDCDCDCDCDCDC end %%PageTrailer %%Trailer %%EOF |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-17 14:16:30
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv4653 Modified Files: bst.cpp test.cpp Log Message: Index: bst.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/bst.cpp,v retrieving revision 1.20 retrieving revision 1.21 diff -C2 -d -r1.20 -r1.21 *** bst.cpp 17 Sep 2004 14:12:14 -0000 1.20 --- bst.cpp 17 Sep 2004 14:16:11 -0000 1.21 *************** *** 248,252 **** { aux1 = aux->erase(); - fprintf(stderr,"1"); if( aux == this ) return aux1; --- 248,251 ---- Index: test.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/test.cpp,v retrieving revision 1.15 retrieving revision 1.16 diff -C2 -d -r1.15 -r1.16 *** test.cpp 16 Sep 2004 17:51:16 -0000 1.15 --- test.cpp 17 Sep 2004 14:16:11 -0000 1.16 *************** *** 174,178 **** random_erase=rand()%insertion_list.size(); ! bst->erase(insertion_list[random_erase]); insertion_list.erase(insertion_list.begin()+random_erase); erase_counter++; --- 174,178 ---- random_erase=rand()%insertion_list.size(); ! bst = bst->erase(insertion_list[random_erase]); insertion_list.erase(insertion_list.begin()+random_erase); erase_counter++; |
|
From: Gianlorenzo D\\'A. <ja...@us...> - 2004-09-17 14:12:23
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv3720 Modified Files: avl.cpp bst.cpp bst.h Log Message: Index: bst.h =================================================================== RCS file: /cvsroot/avl/avl/src/bst.h,v retrieving revision 1.7 retrieving revision 1.8 diff -C2 -d -r1.7 -r1.8 *** bst.h 8 Sep 2004 10:14:46 -0000 1.7 --- bst.h 17 Sep 2004 14:12:14 -0000 1.8 *************** *** 36,40 **** Bst *parent; ! void erase(); void print_ric( int, int ); #ifdef GUI --- 36,40 ---- Bst *parent; ! Bst *erase(); void print_ric( int, int ); #ifdef GUI *************** *** 71,75 **** Bst *search(int); void insert(int); ! void erase(int); Bst *max(); Bst *min(); --- 71,75 ---- Bst *search(int); void insert(int); ! Bst *erase(int); Bst *max(); Bst *min(); Index: bst.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/bst.cpp,v retrieving revision 1.19 retrieving revision 1.20 diff -C2 -d -r1.19 -r1.20 *** bst.cpp 17 Sep 2004 10:41:17 -0000 1.19 --- bst.cpp 17 Sep 2004 14:12:14 -0000 1.20 *************** *** 201,205 **** /*Elimina il nodo corrente dall'albero ( viene richiamato da erase(int) ) */ ! void Bst::erase() { Bst *aux1, *aux2; --- 201,205 ---- /*Elimina il nodo corrente dall'albero ( viene richiamato da erase(int) ) */ ! Bst *Bst::erase() { Bst *aux1, *aux2; *************** *** 234,249 **** delete aux1; //ATT!!!!!!! } /* Elimina il nodo di valore key dall'albero*/ ! void Bst::erase(int key) { ! Bst *aux; aux = search( key ); //si cerca il nodo da eliminare if( aux ) //Se la ricerca ha avuto esito positivo si elimina il nodo { ! aux->erase(); //delete aux; } } --- 234,258 ---- delete aux1; //ATT!!!!!!! + if( aux2 ) + return aux2; + else + return this; } /* Elimina il nodo di valore key dall'albero*/ ! Bst *Bst::erase(int key) { ! Bst *aux, *aux1; aux = search( key ); //si cerca il nodo da eliminare if( aux ) //Se la ricerca ha avuto esito positivo si elimina il nodo { ! aux1 = aux->erase(); ! fprintf(stderr,"1"); ! if( aux == this ) ! return aux1; //delete aux; } + return this; + } Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.21 retrieving revision 1.22 diff -C2 -d -r1.21 -r1.22 *** avl.cpp 17 Sep 2004 12:46:43 -0000 1.21 --- avl.cpp 17 Sep 2004 14:12:14 -0000 1.22 *************** *** 137,141 **** gtk_widget_destroy (dialog);} else { ! aux_bst->erase(value); popup_window(1,"deletion", value); } --- 137,141 ---- gtk_widget_destroy (dialog);} else { ! aux_bst = aux_bst->erase(value); popup_window(1,"deletion", value); } |
|
From: Patrizio B. <het...@us...> - 2004-09-17 12:46:53
|
Update of /cvsroot/avl/avl/src In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv18119/src Modified Files: avl.cpp Log Message: sanity checks Index: avl.cpp =================================================================== RCS file: /cvsroot/avl/avl/src/avl.cpp,v retrieving revision 1.20 retrieving revision 1.21 diff -C2 -d -r1.20 -r1.21 *** avl.cpp 17 Sep 2004 12:44:16 -0000 1.20 --- avl.cpp 17 Sep 2004 12:46:43 -0000 1.21 *************** *** 197,200 **** --- 197,201 ---- upperbound=base_tree-1; + if (upperbound<0) upperbound=0; gtk_spin_button_set_value(GTK_SPIN_BUTTON(spinbutton2),upperbound); GtkWidget *dialog=gtk_message_dialog_new (NULL, GTK_DIALOG_DESTROY_WITH_PARENT, GTK_MESSAGE_INFO, *************** *** 305,309 **** if (base_tree<upperbound) { upperbound=base_tree-1; ! printf("The changement number you entered is bigger than the tree start dimension. Reduced to %d\n",upperbound); } --- 306,311 ---- if (base_tree<upperbound) { upperbound=base_tree-1; ! if (upperbound<0) upperbound=0; ! printf("The changement number you entered is bigger than the tree start dimension. Reduced to %d\n",upperbound); } |
