[Avl-cvs] avl/docs relazione.tex,1.1,1.2

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

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

Modified Files:
	relazione.tex 
Log Message:
GTK GUI added


Index: relazione.tex
===================================================================
RCS file: /cvsroot/avl/avl/docs/relazione.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -C2 -d -r1.1 -r1.2
*** relazione.tex	18 Jul 2004 10:40:15 -0000	1.1
--- relazione.tex	4 Aug 2004 15:31:28 -0000	1.2
***************
*** 30,34 ****
  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.
  
--- 30,34 ----
  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 macchina di per sè velocissima possa essere inutilizabile se il software che la comanda
  contiene errori o è lento.
  
***************
*** 73,76 ****
--- 73,82 ----
  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).
+ 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), lineare.
+ Sorge quindi la necessità di mantenere bilanciato l'albero in modo più efficiente.
+ Gli alberi AVL sono degli alberi BST, con associata un'informazione aggiuntiva per tutti i nodi: il fattore di bilanciamento (Fsb).
+ L'Fsb è 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.
+ Quando un Fsb diventa di +/-2 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. Questo implica complicazioni dal punto dell'analisi del caso peggiore, tuttavia gli autori dell'AVL han dimostrato che