|
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) |
