[Avl-cvs] avl/src avl.cpp,1.2,1.3 avlt.cpp,1.2,1.3 avlt.h,1.2,1.3

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

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

Modified Files:
	avl.cpp avlt.cpp avlt.h 
Log Message:
avltree's class is almoust complete

Index: avlt.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/avlt.cpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** avlt.cpp	23 Jun 2004 14:25:05 -0000	1.2
--- avlt.cpp	24 Jun 2004 17:03:23 -0000	1.3
***************
*** 286,295 ****
    setFdb( aux , aux2 );
    
!   return (Avlt *)root();
  }
  
! void Avlt::erase(int key)
  {
!   Avlt *aux1, *aux2;
    
    if(key == getValue())
--- 286,297 ----
    setFdb( aux , aux2 );
    
!   return (Avlt *)root(); //si può fare di meglio
  }
  
! Avlt *Avlt::erase(int key)
  {
!   Avlt * aux, *aux1, *aux2;
!   
!   aux = this;
    
    if(key == getValue())
***************
*** 299,329 ****
      else
        aux1 = (Avlt *)successor();
!   
!     if( getLeft() )
!     {
!       aux2 = (Avlt *)getLeft();
!       setLeft( NULL );
!     }
      else
!     {
!       aux2 = (Avlt *)getRight();
!       setRight( NULL );
!     }
    
      if( aux2 )
        aux2->setParent( aux1->getParent() );
      
!     if( !aux1->getParent() )
!       aux2 = (Avlt *)root();//Il contrario
!     else
        if( aux1 == aux1->getParent()->getLeft() )
          aux1->getParent()->setLeft( aux2 );
        else
          aux1->getParent()->setRight( aux2 );
!       
      if( aux1 != this )
        setValue( aux1->getValue() );
      setFdb();
!     return;
    }
    
--- 301,354 ----
      else
        aux1 = (Avlt *)successor();
! 
!     if( aux1->getLeft() ) //verificare se non è aux1->getLeft()
!       aux2 = (Avlt *)(aux1->getLeft());
      else
!       aux2 = (Avlt *)(aux1->getRight());
    
      if( aux2 )
        aux2->setParent( aux1->getParent() );
      
!     if( aux1->getParent() )
        if( aux1 == aux1->getParent()->getLeft() )
          aux1->getParent()->setLeft( aux2 );
        else
          aux1->getParent()->setRight( aux2 );
!     
!     aux1->setLeft( NULL );
!     aux1->setRight( NULL );  
      if( aux1 != this )
+     {
        setValue( aux1->getValue() );
+       aux2 = aux1;
+       do{
+         aux2=(Avlt *)(aux2->getParent());
+ 	if(aux2)//verificare se necessario
+ 	{
+           aux2->setFdb();
+           if( aux2->getFdb() == -2 )
+             if( ((Avlt *)(aux2->getRight()))->getFdb() == +1)
+ 	    {
+ 	      ((Avlt *)(aux2->getRight()))->rightRotate();
+ 	      aux2->leftRotate();
+ 	    }  
+ 	    else
+ 	      aux2->leftRotate();
+           else
+             if( aux2->getFdb() == 2 )
+               if( ((Avlt *)(aux2->getLeft()))->getFdb() == -1)
+               {
+ 	        ((Avlt *)(aux2->getLeft()))->leftRotate();
+ 	        aux2->rightRotate();
+ 	      }
+ 	      else
+ 	        aux2->rightRotate();
+         }
+       }while( aux2 != this && aux2 );
+     }
+     
      setFdb();
!     delete( aux1 );  //ATT!!!!!!!
!     return aux;
    }
    
***************
*** 338,345 ****
  	{
  	  ((Avlt *)getRight())->rightRotate();
! 	  leftRotate();
  	}  
  	else
! 	  leftRotate();
      }
    }
--- 363,370 ----
  	{
  	  ((Avlt *)getRight())->rightRotate();
! 	  aux = leftRotate();
  	}  
  	else
! 	  aux = leftRotate();
      }
    }
***************
*** 351,363 ****
        setFdb();
        if( getFdb() == 2 )
!         if( ((Avlt *)getRight())->getFdb() == -1)
  	{
  	  ((Avlt *)getLeft())->leftRotate();
! 	  rightRotate();
  	}  
  	else
! 	  rightRotate();
      }
    }
  }
  
--- 376,389 ----
        setFdb();
        if( getFdb() == 2 )
!         if( ((Avlt *)getLeft())->getFdb() == -1)
  	{
  	  ((Avlt *)getLeft())->leftRotate();
! 	  aux = rightRotate();
  	}  
  	else
! 	  aux = rightRotate();
      }
    }
+   return aux;
  }
  

Index: avl.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/avl.cpp,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** avl.cpp	23 Jun 2004 14:25:05 -0000	1.2
--- avl.cpp	24 Jun 2004 17:03:23 -0000	1.3
***************
*** 62,66 ****
   a = new Avlt(0,1);
   
!   for (int i=0;i<600;i++)
    {
      int aaa=(rand()%1000)-500;
--- 62,66 ----
   a = new Avlt(0,1);
   
!   for (int i=0;i<567;i++)
    {
      int aaa=(rand()%1000)-500;
***************
*** 68,72 ****
      //if(i>=19)
      {
!   /*    printf("%d->%d\n",i,aaa);
        if(!a->checkBalance())
        {
--- 68,72 ----
      //if(i>=19)
      {
! /*      printf("%d->%d\n",i,aaa);
        if(!a->checkBalance())
        {
***************
*** 76,81 ****
      }
    }
!   a->erase(1);
!   printf("%d",a->checkBalance());
   // a->print();
    /*vector<Avlt *> v;
--- 76,110 ----
      }
    }
!  
!  // a->search(-8)->print1();
!   printf("%d\n",a->nodes());
!   a = a->erase(277);
!   a = a->erase(3);
!   a = a->erase(-3);
!   a = a->erase(-8);
!   a = a->erase(-165);
!   a = a->erase(190);
!   a = a->erase(415);
!   a = a->erase(a->root()->getValue());
!  // a = a->erase(-7);
!   printf("\n%d\n",a->nodes());
!   
!   printf("\n%d",a->checkBalance());
! //a->print1();
!  // a->search(3)->print1();
!   //a->print();
!   /*
!   a = a->insert(-98);
!   a = a->insert(100);
!   a = a->insert(-1000);
!   a = a->insert(-10);
!   a = a->insert(50);
!   a = a->insert(102);
!   a = a->insert(1000);
!   
!   a->print();
!   
!   a->erase(50);
!   a->print1();*/
   // a->print();
    /*vector<Avlt *> v;

Index: avlt.h
===================================================================
RCS file: /cvsroot/avl/avl/src/avlt.h,v
retrieving revision 1.2
retrieving revision 1.3
diff -C2 -d -r1.2 -r1.3
*** avlt.h	23 Jun 2004 14:25:05 -0000	1.2
--- avlt.h	24 Jun 2004 17:03:23 -0000	1.3
***************
*** 54,58 ****
    Avlt *insert_ric(int);
    
!   void erase(int);
    
    
--- 54,58 ----
    Avlt *insert_ric(int);
    
!   Avlt *erase(int);