[Avl-cvs] avl/src avlt.cpp,1.9,1.10 bst.cpp,1.14,1.15

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

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

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


Index: avlt.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/avlt.cpp,v
retrieving revision 1.9
retrieving revision 1.10
diff -C2 -d -r1.9 -r1.10
*** avlt.cpp	7 Sep 2004 13:03:21 -0000	1.9
--- avlt.cpp	7 Sep 2004 17:15:20 -0000	1.10
***************
*** 36,40 ****
  {
    //Il fattore di bilanciamento è la differenza tra l'altezza del sottoallbero di destra e quella del sottoalbero di sinistra
!   if(isLeaf())
      setHeight(0);
    else
--- 36,40 ----
  {
    //Il fattore di bilanciamento è la differenza tra l'altezza del sottoallbero di destra e quella del sottoalbero di sinistra
!   if(isLeaf()) //nel caso in cui il nodo non ha foglie l'altezza del nodo è pari a 0
      setHeight(0);
    else
***************
*** 43,50 ****
      l = r = 0;
      if( getLeft() )
!       l = ((Avlt *)getLeft())->getHeight(); // l contiene l'altezza del sottoalbero sinistro
      if( getRight() )
!       r = ((Avlt *)getRight())->getHeight(); // r contiene l'altezza del sottoalbero destro
!     setHeight( 1 + ( l>r ? l : r ) ); // viene restituita l'altezza del sottoalbero più lungo incrementata di 1
    }
  }
--- 43,50 ----
      l = r = 0;
      if( getLeft() )
!       l = ((Avlt *)getLeft())->getHeight(); // l contiene l'altezza del ramo sinistro
      if( getRight() )
!       r = ((Avlt *)getRight())->getHeight(); // r contiene l'altezza del ramo destro
!     setHeight( 1 + ( l>r ? l : r ) ); // l'altezza del sottoalbero più lungo incrementata di 1 viene posta come altezza del nodo
    }
  }
***************
*** 53,60 ****
  void Avlt::setFdb( Avlt * start , Avlt * end)
  {
! 
!   while( end != start ) 
    {
!     end->setFdb();  //forse si può migliorare
      end = (Avlt *)end->getParent();
    }
--- 53,60 ----
  void Avlt::setFdb( Avlt * start , Avlt * end)
  {
!   //l'albero viene percorso dal basso verso l'alto
!   while( end != start )
    {
!     end->setFdb();
      end = (Avlt *)end->getParent();
    }
***************
*** 64,76 ****
  }
  
  int Avlt::getFdb()
  {
    int l, r;
    l = r = 0;
    if( getLeft() )
!     l = ((Avlt *)getLeft())->getHeight() + 1; //Altezza del sottoalbero di sinistra
    if( getRight() )
!     r = ((Avlt *)getRight())->getHeight() + 1; //Altezza del sottoalbero di destra
!   return l-r;
  }
  
--- 64,78 ----
  }
  
+ /* Calcola il FdB del nodo corrente*/
  int Avlt::getFdb()
  {
+   //Il fattore di bilanciamento è la differenza tra l'altezza del sottoallbero di destra e quella del sottoalbero di sinistra
    int l, r;
    l = r = 0;
    if( getLeft() )
!     l = ((Avlt *)getLeft())->getHeight() + 1; //Altezza del ramo di sinistra incrementata di 1
    if( getRight() )
!     r = ((Avlt *)getRight())->getHeight() + 1; //Altezza del ramo di destra incrementata di 1
!   return l-r; //Restituisce la differenza tra l'altezza del ramo di sinistra e quella del ramo di destra (secondo la definizione di FdB)
  }
  
***************
*** 85,105 ****
  }
  
! /* Effettua una rotazione verso sinistra e restituisce il nuovo nodo genitore*/
! Avlt *Avlt::leftRotate() //dd
  {
    Avlt *aux;
    
!   aux = (Avlt *)getRight();
    
    if( aux )
    {
      setRight( getRight()->getLeft() );
-   
      if( getRight() )
        getRight()->setParent( this );
!     
      aux->setLeft( this );
      aux->setParent( getParent() );
!   
      if( getParent() )
        if( this == getParent()->getLeft() )
--- 87,110 ----
  }
  
! /* Effettua una rotazione verso sinistra e restituisce il nuovo nodo genitore (rotazione dd)*/
! Avlt *Avlt::leftRotate()
  {
    Avlt *aux;
    
!   aux = (Avlt *)getRight(); //aux punta al nodo che diverrà la nuova "radice"
    
    if( aux )
    {
+     //il sottoalbero sx del nodo puntato da aux viene messo come sottoalbero destro del nodo corrente
      setRight( getRight()->getLeft() );
      if( getRight() )
        getRight()->setParent( this );
! 
!     //il nodo corrente viene messo alla sx di aux
      aux->setLeft( this );
+ 
+     //viene collegato aux al nuovo padre
      aux->setParent( getParent() );
!     //viene collegato il nuovo padre di aux ad aux
      if( getParent() )
        if( this == getParent()->getLeft() )
***************
*** 107,116 ****
        else
          getParent()->setRight( aux );
!     
      setParent( aux );
      
      ((Avlt *)(aux->getLeft()))->setFdb();
      aux->setFdb();
      
      return aux;
    }
--- 112,124 ----
        else
          getParent()->setRight( aux );
! 
!     //il nodo corrente può ora essere collegato al nuovo padre    
      setParent( aux );
      
+     //viene sistemato il Fdb dove potrebbe essere cambiato ovvero nel ramo di sx e nella nuova radice
      ((Avlt *)(aux->getLeft()))->setFdb();
      aux->setFdb();
      
+     //viene restituita la nuova "radice"
      return aux;
    }
***************
*** 119,139 ****
  }
  
! /* Effettua una rotazione verso destra e restituisce il nuovo nodo genitore*/
! Avlt *Avlt::rightRotate() //ss
  {
    Avlt *aux;
    
!   aux = (Avlt *)getLeft();
    
    if( aux )
    {
      setLeft( getLeft()->getRight() );
-   
      if( getLeft() )
        getLeft()->setParent( this );
! 
      aux->setRight( this );
      aux->setParent( getParent() );
!   
      if( getParent() )
        if( this == getParent()->getLeft() )
--- 127,150 ----
  }
  
! /* Effettua una rotazione verso destra e restituisce il nuovo nodo genitore (rotazione ss)*/
! Avlt *Avlt::rightRotate()
  {
    Avlt *aux;
    
!   aux = (Avlt *)getLeft(); //aux punta al nodo che diverrà la nuova "radice"
    
    if( aux )
    {
+     //il sottoalbero dx del nodo puntato da aux viene messo come sottoalbero sinistro del nodo corrente
      setLeft( getLeft()->getRight() );
      if( getLeft() )
        getLeft()->setParent( this );
!   
!     //il nodo corrente viene messo alla dx di aux
      aux->setRight( this );
+     
+     //viene collegato aux al nuovo padre
      aux->setParent( getParent() );
!     //viene collegato il nuovo padre di aux ad aux
      if( getParent() )
        if( this == getParent()->getLeft() )
***************
*** 142,150 ****
          getParent()->setRight( aux );
      
      setParent( aux );
      
      ((Avlt *)(aux->getRight()))->setFdb();
      aux->setFdb();
!     
      return aux;
    }
--- 153,164 ----
          getParent()->setRight( aux );
      
+     //il nodo corrente può ora essere collegato al nuovo padre
      setParent( aux );
      
+     //viene sistemato il Fdb dove potrebbe essere cambiato ovvero nel ramo di dx e nella nuova radice
      ((Avlt *)(aux->getRight()))->setFdb();
      aux->setFdb();
! 
!     //viene restituita la nuova "radice"    
      return aux;
    }
***************
*** 158,173 ****
    Avlt *aux;
    aux = this;
!   if(key == getValue())
      return this;
!   if(key < getValue())
    {
!     if( getLeft() )
      {
        ((Avlt *)getLeft())->insert(key);
!       setFdb();
!       if( getFdb() == 2 )
!         if( key < getLeft()->getValue() )
            aux = rightRotate();
!         else
          {
            ((Avlt *)(getLeft()))->leftRotate();
--- 172,187 ----
    Avlt *aux;
    aux = this;
!   if(key == getValue()) //Se il valore è già presente si esce
      return this;
!   if(key < getValue()) // Se il valore da inserire è < di quello del nodo attuale si inserisce verso sinistra, altrimenti verso destra
    {
!     if( getLeft() ) //Se il nodo corrente ha un figlio sinistro si richiama insert su tale nodo. Altrimenti si crea un nuovo nodo e lo si appende come figlio sinistro
      {
        ((Avlt *)getLeft())->insert(key);
!       setFdb(); //dopo l'inserimento potrebbe essere cambiato il FdB (notare che questa operazione viene effettuata solo nel ramo percorso per inserire il nodo)
!       if( getFdb() == 2 ) //Se l'albero si è sbilanciato a seguito dell'inserimento
!         if( key < getLeft()->getValue() ) //Se si è inserito a sinistra-sinistra allora si deve fare una rightrotate per ribilanciare
            aux = rightRotate();
!         else //Altrimenti si è inserito in sinistra-destra allora si deve fare una leftrotate sul ramo si sinistra seguita da una rightrotate sul ramo di destra (rotazione di tipo sd)
          {
            ((Avlt *)(getLeft()))->leftRotate();
***************
*** 185,189 ****
    }
    else
!   {
      if( getRight() )
      {
--- 199,203 ----
    }
    else
!   {  //si effettuano operazioni simmetriche a sopra
      if( getRight() )
      {
***************
*** 329,333 ****
        aux1 = (Avlt *)successor();
  
!     if( aux1->getLeft() ) //verificare se non è aux1->getLeft()
        aux2 = (Avlt *)(aux1->getLeft());
      else
--- 343,347 ----
        aux1 = (Avlt *)successor();
  
!     if( aux1->getLeft() )
        aux2 = (Avlt *)(aux1->getLeft());
      else
***************
*** 351,355 ****
        do{
          aux2=(Avlt *)(aux2->getParent());
! 	if(aux2)//verificare se necessario
  	{
            aux2->setFdb();
--- 365,369 ----
        do{
          aux2=(Avlt *)(aux2->getParent());
! 	if(aux2)
  	{
            aux2->setFdb();
***************
*** 422,431 ****
    bool l, r;
    l = r = true;
!   setFdb();
    if( getLeft() )
!     l = ((Avlt *)getLeft())->checkBalance();
    if( getRight() )
!     r = ((Avlt *)getRight())->checkBalance();
    
    return l && r && (getFdb()==0 || getFdb()==-1 || getFdb()==1);
  }
--- 436,446 ----
    bool l, r;
    l = r = true;
!   setFdb();  //viene prima ricalcolato il bilanciamento
    if( getLeft() )
!     l = ((Avlt *)getLeft())->checkBalance(); //l inidica se il sottoalbero sinistro è bilanciato
    if( getRight() )
!     r = ((Avlt *)getRight())->checkBalance();//r inidica se il sottoalbero destro è bilanciato
    
+   // restituisce vero se i sottoalberi destro e sinistro sono bilanciati e se il fattore di bilanciamento del nodo corrente è 1, -1 oppure 0
    return l && r && (getFdb()==0 || getFdb()==-1 || getFdb()==1);
  }
***************
*** 435,439 ****
  {
    vector<Avlt *> v , aux;
!   if( getLeft() )
    {
      aux = ((Avlt *)getLeft())->getWrongs();
--- 450,454 ----
  {
    vector<Avlt *> v , aux;
!   if( getLeft() ) //vengono aggiunti a v i nodi sbilanciati del sottoalbero sinistro
    {
      aux = ((Avlt *)getLeft())->getWrongs();
***************
*** 441,445 ****
        v.push_back(aux[i]);
    }  
!   if( getRight() )
    {
      aux = ((Avlt *)getRight())->getWrongs();
--- 456,460 ----
        v.push_back(aux[i]);
    }  
!   if( getRight() ) //vengono aggiunti a v i nodi sbilanciati del sottoalbero destro
    {
      aux = ((Avlt *)getRight())->getWrongs();
***************
*** 448,452 ****
    }  
    
!   if( getFdb()!=0 && getFdb()!=-1 && getFdb()!=1 )
      v.push_back(this);
    
--- 463,467 ----
    }  
    
!   if( getFdb()!=0 && getFdb()!=-1 && getFdb()!=1 ) //viene aggiunto a v il nodo corrente se è sbilanciato
      v.push_back(this);
    

Index: bst.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/bst.cpp,v
retrieving revision 1.14
retrieving revision 1.15
diff -C2 -d -r1.14 -r1.15
*** bst.cpp	7 Sep 2004 14:37:01 -0000	1.14
--- bst.cpp	7 Sep 2004 17:15:20 -0000	1.15
***************
*** 199,203 ****
    aux1 = new Bst( key );
    aux1->setParent( aux2 );
- //  aux1->setValue( key );
    
    // il nuovo nodo viene appeso a sinistra o a destra di aux2 in base al suo valore
--- 199,202 ----
***************
*** 210,214 ****
  }
  
! 
  void Bst::erase()
  {
--- 209,213 ----
  }
  
! /*Elimina il nodo corrente dall'albero ( viene richiamato da erase(int) ) */
  void Bst::erase()
  {
***************
*** 248,253 ****
  {
    Bst *aux;
!   aux = search( key );
!   if( aux )
    {
      aux->erase();
--- 247,252 ----
  {
    Bst *aux;
!   aux = search( key ); //si cerca il nodo da eliminare
!   if( aux ) //Se la ricerca ha avuto esito positivo si elimina il nodo
    {
      aux->erase();