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