[Avl-cvs] avl/src avlt.cpp,1.10,1.11 bst.cpp,1.15,1.16

[Gianlorenzo D\\'A. <ja...@us...>]

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

Modified Files:
	avlt.cpp bst.cpp 
Log Message:


Index: avlt.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/avlt.cpp,v
retrieving revision 1.10
retrieving revision 1.11
diff -C2 -d -r1.10 -r1.11
*** avlt.cpp	7 Sep 2004 17:15:20 -0000	1.10
--- avlt.cpp	8 Sep 2004 10:10:41 -0000	1.11
***************
*** 332,335 ****
--- 332,337 ----
  Avlt *Avlt::erase(int key)
  {
+ 
+   // 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;
    
***************
*** 337,341 ****
    
    if(key == getValue())
!   {
      if ( !getLeft() || !getRight() )
        aux1 = this;
--- 339,343 ----
    
    if(key == getValue())
!   { //Questi passaggi sono simili a quelli utilizzati per i bst
      if ( !getLeft() || !getRight() )
        aux1 = this;
***************
*** 362,365 ****
--- 364,368 ----
      {
        setValue( aux1->getValue() );
+       //Se si sta eliminando il successore cambiano i FdB nel cammino che va da aux1 (il nodo che verrà eliminato) al nodo corrente e l'albero potrebbe sbilanciarsi lungo tale cammino
        aux2 = aux1;
        do{
***************
*** 368,373 ****
  	{
            aux2->setFdb();
!           if( aux2->getFdb() == -2 )
!             if( ((Avlt *)(aux2->getRight()))->getFdb() == +1)
  	    {
  	      ((Avlt *)(aux2->getRight()))->rightRotate();
--- 371,376 ----
  	{
            aux2->setFdb();
!           if( aux2->getFdb() == -2 ) //Se l'albero si è sbilanciato verso destra
!             if( ((Avlt *)(aux2->getRight()))->getFdb() == +1) //Se il sottoalbero di destra ha il ramo sinistro più lungo si opera una rotazione ds altrimenti una rotazione dd
  	    {
  	      ((Avlt *)(aux2->getRight()))->rightRotate();
***************
*** 376,380 ****
  	    else
  	      aux2->leftRotate();
!           else
              if( aux2->getFdb() == 2 )
                if( ((Avlt *)(aux2->getLeft()))->getFdb() == -1)
--- 379,383 ----
  	    else
  	      aux2->leftRotate();
!           else //condizioni simmetriche a sopra
              if( aux2->getFdb() == 2 )
                if( ((Avlt *)(aux2->getLeft()))->getFdb() == -1)
***************
*** 394,405 ****
    }
    
!   if(key < getValue())
    {
      if( getLeft() )
      {
!       ((Avlt *)getLeft())->erase( key );
!       setFdb();
        if( getFdb() == -2 )
!         if( ((Avlt *)getRight())->getFdb() == +1)
  	{
  	  ((Avlt *)getRight())->rightRotate();
--- 397,408 ----
    }
    
!   if(key < getValue()) //Se il nodo corrente ha valore maggiore di quello da eliminare si va verso sinistra altrimenti verso destra
    {
      if( getLeft() )
      {
!       ((Avlt *)getLeft())->erase( key ); //chiamata ricorsiva
!       setFdb(); //L'eliminazione in questo sottoalbero potrebbe aver cambiato l'fdb del nodo corrente e di conseguenza potrebbe essersi sbilanciato verso destra
        if( getFdb() == -2 )
!         if( ((Avlt *)getRight())->getFdb() == +1)//Se il sottoalbero di destra ha il ramo sinistro più lungo si opera una rotazione ds altrimenti una rotazione dd
  	{
  	  ((Avlt *)getRight())->rightRotate();
***************
*** 411,415 ****
    }
    else  
!   {
      if( getRight() )
      {
--- 414,418 ----
    }
    else  
!   {  //operazioni simmetriche a sopra
      if( getRight() )
      {

Index: bst.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/bst.cpp,v
retrieving revision 1.15
retrieving revision 1.16
diff -C2 -d -r1.15 -r1.16
*** bst.cpp	7 Sep 2004 17:15:20 -0000	1.15
--- bst.cpp	8 Sep 2004 10:10:41 -0000	1.16
***************
*** 213,235 ****
  {
    Bst *aux1, *aux2;
!   if ( !getLeft() || !getRight() )
      aux1 = this;
    else
      aux1 = successor();
    
    if( aux1->getLeft() )
-   {
      aux2 = aux1->getLeft();
-     //setLeft( NULL );
-   }
    else
-   {
      aux2 = aux1->getRight();
-     //setRight( NULL );
-   }
    
    if( aux2 )
      aux2->setParent( aux1->getParent() );
!     
    if( aux1->getParent() )
      if( aux1 == aux1->getParent()->getLeft() )
--- 213,235 ----
  {
    Bst *aux1, *aux2;
!   
!   //aux1 contiene il nodo che verrà eliminato
!   if ( !getLeft() || !getRight() ) //se il nodo corrente ha al più un figlio allora è il nodo da eliminare altrimenti (cioè se ha entrambi i figli - la condizione  (!getLeft() || !getRight()) è identica a !(getLeft() && getRight()) ) è il suo successore
      aux1 = this;
    else
      aux1 = successor();
    
+   //aux2 viene fatto puntare al figlio sinistro, se esiste, di aux1 altrimenti al figlio destro oppure a NULL nel caso in cui aux1 non ha figli
    if( aux1->getLeft() )
      aux2 = aux1->getLeft();
    else
      aux2 = aux1->getRight();
    
+   //Viene scambiato aux1 con aux2
+   //Prima si assegna il padre di aux1 al padre di aux2
    if( aux2 )
      aux2->setParent( aux1->getParent() );
!   
!   //Poi si assegna aux2 come figlio del padre di aux1
    if( aux1->getParent() )
      if( aux1 == aux1->getParent()->getLeft() )
***************
*** 237,243 ****
      else
        aux1->getParent()->setRight( aux2 );
!       
    if( aux1 != this )
      setValue( aux1->getValue() );
    delete aux1; //ATT!!!!!!!
  }
--- 237,245 ----
      else
        aux1->getParent()->setRight( aux2 );
!   
!   //Se il nodo che verrà eliminato è il successore del nodo corrente allora il suo valore viene assegnato al nodo corrente
    if( aux1 != this )
      setValue( aux1->getValue() );
+     
    delete aux1; //ATT!!!!!!!
  }