avl-cvs Mailing List for avl (Page 4)

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

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

Added Files:
	relazione.tex 
Log Message:
inizio relazione

--- NEW FILE: relazione.tex ---
\documentclass[12pt]{report}

\usepackage{enumerate}
\usepackage[latin1]{inputenc} %per usare direttamente da tastiera le vocali
                              %accentate
\usepackage[italian]{babel}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{setspace}

\pagestyle{fancy}
\title{\Huge\textbf{AVL \& BST Trees}\\\ \\\textbf{\LARGE{Relazione}}\\~\\}
\author{Patrizio Bassi, Gianlorenzo D'Angelo}

\begin{document}
\maketitle
\tableofcontents
\onehalfspacing
\chapter{Introduzione}\label{Introduzione}
L'evoluzione tecnologica degli ultimi anni sia stata
semplicemente travolgente, con una crescita sempre più accentuata della potenza
di calcolo a disposizione, non solo di grandi aziende e enti governativi,
ma anche per i cosiddetti "end-users", gli utenti domestici.

Macchine assemblate con processori con frequenze superiori ai 3 GHz, quantità di
RAM superiori al GB e spazio su HardDisk nell'ordine di centinaia di GB
sono disponibili a prezzi decisamente accessibili.

Tuttavia, è noto che l'hardware a sè stante è inutile.
E' (e sarà) sempre necessario del software per comandare tutte le varie periferiche in questione;
questa cosa fa capire quanto una macchian di per sè velocissima possa essere inutilizabile se il software che la comanda
contiene errori o è lento.

Per questo motivo la ricerca nel campo degli algoritmi non è affatto terminata.
Negli anni passati trovare un algoritmo ottimo era assolutamente necessario, dato che le risorse di calcolo a disposizione
erano limitate, ma ancora oggi esistono tanti problemi che non possono essere affrontati con il semplice approccio
"forza bruta", perchè impiegherebbero anche centinaia di anni ad essere risolti.

Davvero fervente è stata la ricerca su grafi ed alberi, poichè sono strutture dati che possono plasmare situazioni 
problematiche che sembrano assai differenti tra loro, risolvendo il problema con l'utilizzo di algoritmi già noti, di 
cui è nota anche l'efficenza, le prestazioni, gli eventuali problemi.

In questo ambito è collocato questo lavoro: lo studio e implementazione degli alberi AVL e BST, per individuare quali 
sono i vantaggi e svantaggi di entrambi gli algoritmi.

Nel prossimo capitolo verrà illustrato in generale in funzionamento e l'idea alla base delle due tecniche, poi verrà 
esaminata in generale l'implementazione proposta e le conclusioni che si possono trarre dopo aver sfruttato il codice 
prodotto.

\chapter{Breve Panoramica}
La premessa di questo capitolo è quella di non essere assolutamente un riferimento esaustivo sugli alberi AVL e BST.
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) 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 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 i BST, Binary Search Tree, e gli AVL trees, anagramma derivato dal nome dei loro ideatori.
In generale gli alberi superano alcune limitazioni delle altre soluzioni, ad esempio non soffrono di limiti di spazio fisso.
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.
In questo lavoro ci si concentrerà sull'operazione di ricerca, restringendo l'area agli alberi binari, ovvero quelli i cui nodi hanno al massimo 2 figli.
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
\item Le chiavi nel sotto albero sinistro di v sono tutte < o al più = della chiave di v
\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 è log(n).
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.
Chiaramente, come già detto in precedenza, avere un costo minore nella ricerca costringerà a performance infariori in altre
situazioni.
Il concetto di bilanciamento può essere riassunto nel mantenere un albero i cui rami hanno tutti la stessa lunghezza (con starti di +/-1), in modo da pagare un costo logaritmico per la ricerca.
Va considerato che questo costo è particolarmente importante, poichè è evidente che anche le operazioni di cancellazione e inserimento contengono una ricerca priliminare (per trovare dove inserire e per trovare il nodo da cancellare).

\chapter{Applicazione}\label{Applicazione}

\chapter{Conclusioni}\label{Conclusioni}
\end{document}

avl-cvs Mailing List for avl (Page 4)

avl-cvs — CVS Commits