[Avl-cvs] avl/src avlt.cpp,1.4,1.5 avlt.h,1.5,1.6 bst.cpp,1.7,1.8

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

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

Modified Files:
	avlt.cpp avlt.h bst.cpp 
Log Message:
added comments

Index: avlt.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/avlt.cpp,v
retrieving revision 1.4
retrieving revision 1.5
diff -C2 -d -r1.4 -r1.5
*** avlt.cpp	25 Jun 2004 16:05:57 -0000	1.4
--- avlt.cpp	18 Jul 2004 16:57:10 -0000	1.5
***************
*** 32,35 ****
--- 32,36 ----
  }
  
+ /** Imposta il Fattore di Bilanciamento a s*/
  void Avlt::setFdb( int s )
  {
***************
*** 37,51 ****
  }
  
  void Avlt::setFdb()
  {
    int l, r;
    l = r = 0;
    if( getLeft() )
!     l = getLeft()->height() + 1;
    if( getRight() )
!     r = getRight()->height() + 1;
    setFdb( l-r );
  }
  
  void Avlt::setFdb( Avlt * start , Avlt * end)
  {
--- 38,55 ----
  }
  
+ /** Calcola il FdB del nodo corrente*/
  void Avlt::setFdb()
  {
+   //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 = getLeft()->height() + 1; //Altezza del sottoalbero di sinistra
    if( getRight() )
!     r = getRight()->height() + 1; //Altezza del sottoalbero di destra
    setFdb( l-r );
  }
  
+ /** Calcola il fattore di bilanciamento a di tutti i nodi del cammino da start a end*/
  void Avlt::setFdb( Avlt * start , Avlt * end)
  {
***************
*** 66,70 ****
  }
  
! 
  Avlt *Avlt::leftRotate() //dd
  {
--- 70,74 ----
  }
  
! /** Effettua una rotazione verso sinistra e restituisce il nuovo nodo genitore*/
  Avlt *Avlt::leftRotate() //dd
  {
***************
*** 99,102 ****
--- 103,107 ----
  }
  
+ /** Effettua una rotazione verso destra e restituisce il nuovo nodo genitore*/
  Avlt *Avlt::rightRotate() //ss
  {
***************
*** 131,134 ****
--- 136,140 ----
  }
  
+ /** Inserisce un nuovo nodo con valore key utilizzando un algoritmo ricorsivo*/
  Avlt *Avlt::insert(int key)
  {
***************
*** 186,189 ****
--- 192,196 ----
  }
  
+ /** Inserisce un nuovo nodo con valore key utilizzando un algoritmo iterativo*/
  Avlt *Avlt::insert_iter(int key)
  {
***************
*** 289,292 ****
--- 296,300 ----
  }
  
+ /** Elimina il nodo di valore key dall'albero*/
  Avlt *Avlt::erase(int key)
  {
***************
*** 388,391 ****
--- 396,400 ----
  }
  
+ /** Verifica se l'albero è bilanciato*/
  bool Avlt::checkBalance()
  {
***************
*** 403,406 ****
--- 412,416 ----
  }
  
+ /** Restituisce un vettore di nodi che hanno FdB diverso da -1,0,+1*/
  vector<Avlt *> Avlt::getWrongs()
  {

Index: bst.cpp
===================================================================
RCS file: /cvsroot/avl/avl/src/bst.cpp,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** bst.cpp	17 Jul 2004 19:48:27 -0000	1.7
--- bst.cpp	18 Jul 2004 16:57:10 -0000	1.8
***************
*** 75,91 ****
    value = val;
  }
!   
  Bst *Bst::root()
  {
    Bst *aux;
    for( aux=this; aux->getParent(); aux=aux->getParent() );
    return aux;
  }
  
  bool Bst::isLeaf()
  {
    return !(getLeft()||getRight());
  }
  
  bool Bst::isRoot()
  {
--- 75,96 ----
    value = val;
  }
! 
! /** Restituisce la radice dell'albero a cui appartiene il nodo corrente*/
  Bst *Bst::root()
  {
    Bst *aux;
+   //scorre l'albero dal basso verso l'alto a partire dal nodo corrente fino a che non trova un nodo che non ha genitore
    for( aux=this; aux->getParent(); aux=aux->getParent() );
    return aux;
  }
  
+ /** Indica se il nodo corrente è una foglia */
  bool Bst::isLeaf()
  {
+   //testa (getLeft()==NULL && getRight()==NULL) <==> (!getLeft() && !getRight()) <==> !(getLeft()||getRight())
    return !(getLeft()||getRight());
  }
  
+ /** Indica se il nodo è la radice dell'albero*/
  bool Bst::isRoot()
  {
***************
*** 93,130 ****
  }
  
  int Bst::level()
  {
    Bst *aux;
    int count;
    for( count=0,aux=this; aux->getParent(); aux=aux->getParent(),count++ );
    return count;
  }
  
  int Bst::nodes()
  {
    if( isLeaf() )
      return 1;
!   int node = 1;
    if( getLeft() )
!     node += getLeft()->nodes();
    if( getRight() )
!     node += getRight()->nodes();
    return node;
  }
  
  int Bst::leaves()
  {
    if( isLeaf() )
      return 1;
!   int node = 0;
    if( getLeft() )
!     node = getLeft()->leaves();
    if( getRight() )
!     node += getRight()->leaves();
!   return node;
  }
  
  int Bst::height()
  {
    if( isLeaf() )
      return 0;
--- 98,143 ----
  }
  
+ /** Calcola il livello del nodo (ovvero la lunghezza del cammino tra il nodo e la radice)*/
  int Bst::level()
  {
    Bst *aux;
    int count;
+   //scorre l'albero dal basso verso l'alto a partire dal nodo corrente fino a che non trova un nodo che non ha genitore e conta i passi che compie attraverso la variabile cont
    for( count=0,aux=this; aux->getParent(); aux=aux->getParent(),count++ );
    return count;
  }
  
+ /** Calcola il numero di nodi dell'albero che ha come radice il nodo*/
  int Bst::nodes()
  {
+   //Il numero di nodi è pari a 1 se il nodo è una foglia oppure al numero di nodi del sottoalbero di sinistra + il numero di nodi del sottoalbero di destra + 1 (se stesso) ovvero node = 1 + getLeft()->nodes() + getRight()->nodes()
    if( isLeaf() )
      return 1;
!   int node = 1; // node = 1
    if( getLeft() )
!     node += getLeft()->nodes(); // node = 1 + getLeft()->nodes()
    if( getRight() )
!     node += getRight()->nodes(); // node = 1 + getLeft()->nodes() + getRight()->nodes()
    return node;
  }
  
+ /** Calcola il numero di foglie dell'albero che ha come radice il nodo*/
  int Bst::leaves()
  {
+   //Il numero di foglie è pari a 1 se il nodo è una foglia oppure al numero di foglie del sottoalbero di sinistra + il numero di foglie del sottoalbero di destra ovvero leave = getLeft()->leaves() + getRight()->leaves()
    if( isLeaf() )
      return 1;
!   int leave = 0;
    if( getLeft() )
!     leave = getLeft()->leaves(); // leave = getLeft()->leaves()
    if( getRight() )
!     leave += getRight()->leaves(); // leave = getLeft()->leaves() + getRight()->leaves()
!   return leave;
  }
  
+ /** Calcola l'altezza (lunghezza del ramo più lungo) dell'albero che ha come radice il nodo*/
  int Bst::height()
  {
+   // L'altezza di un nodo è pari all'altezza del sottoalbero più lungo incrementata di 1 (il nodo corrente)
    if( isLeaf() )
      return 0;
***************
*** 132,142 ****
    l = r = 0;
    if( getLeft() )
!     l = getLeft()->height();
    if( getRight() )
!     r = getRight()->height();
   
!   return 1 + ( l>r ? l : r );
  }
  
  Bst *Bst::search(int key)
  {
--- 145,156 ----
    l = r = 0;
    if( getLeft() )
!     l = getLeft()->height(); // l contiene l'altezza del sottoalbero sinistro
    if( getRight() )
!     r = getRight()->height(); // r contiene l'altezza del sottoalbero destro
   
!   return 1 + ( l>r ? l : r ); // viene restituita l'altezza del sottoalbero più lungo incrementata di 1
  }
  
+ /** Ricerca un nodo di valore key in modo iterativo e ne restituisce il puntatore, se la ricerca ha esito negativo restituisce NULL*/
  Bst *Bst::search(int key)
  {
***************
*** 146,160 ****
    while( aux )
    {
!     if( aux->getValue() == key )
        return aux;
!     if( key < aux->getValue() )
        aux = aux->getLeft();
!     else
!       aux = aux->getRight();
    }
    
!   return NULL;
  }
  
  void Bst::insert(int key)
  {
--- 160,175 ----
    while( aux )
    {
!     if( aux->getValue() == key ) //Si è trovato il nodo cercato: si restituisce il puntatore e si esce
        return aux;
!     if( key < aux->getValue() ) //Se il valore di aux è < di quello di key si cerca a sinistra
        aux = aux->getLeft();
!     else //altrimenti si cerca a destra
!       aux = aux->getRight();  
    }
    
!   return NULL; //Si arriva a questo punto solo se il valore non è stato trovato
  }
  
+ /** Aggiunge un nodo con valore key nell'albero*/
  void Bst::insert(int key)
  {
***************
*** 164,175 ****
    aux2 = NULL;
    
!   while( aux1 )
    {  
      if ( key == aux1->getValue() )
      {
        //printf("The number -> %d is already in the Binary Search Tree\n",key);
!       return;
      }
!     aux2 = aux1;
      if ( key < aux1->getValue() )
        aux1 = aux1->getLeft();
--- 179,190 ----
    aux2 = NULL;
    
!   while( aux1 ) //ricerca del nodo
    {  
      if ( key == aux1->getValue() )
      {
        //printf("The number -> %d is already in the Binary Search Tree\n",key);
!       return; // se il valore si trova già nell'albero si esce
      }
!     aux2 = aux1; //aux2 mantiene il puntatore al nodo al quale si deve appendere il nuovo nodo
      if ( key < aux1->getValue() )
        aux1 = aux1->getLeft();
***************
*** 178,185 ****
--- 193,202 ----
    }
    
+   // viene istanziato il nuovo nodo e gli viene assegnato key come valore e aux2 come genitore
    aux1 = new Bst;
    aux1->setParent( aux2 );
    aux1->setValue( key );
    
+   // il nuovo nodo viene appeso a sinistra o a destra di aux2 in base al suo valore
    if ( key < aux2->getValue() )
      aux2->setLeft( aux1 );
***************
*** 189,192 ****
--- 206,210 ----
  }
  
+ 
  void Bst::erase()
  {
***************
*** 222,229 ****
  }
  
! void Bst::erase(int val)
  {
    Bst *aux;
!   aux = search( val );
    if( aux )
    {
--- 240,248 ----
  }
  
! /** Elimina il nodo di valore key dall'albero*/
! void Bst::erase(int key)
  {
    Bst *aux;
!   aux = search( key );
    if( aux )
    {
***************
*** 233,255 ****
--- 252,281 ----
  }
  
+ /** Trova il nodo dell'albero che ha valore massimo e ne restituisce il puntatore*/
  Bst *Bst::max()
  {
    Bst *aux;
+   // Si scorre l'albero verso il figlio di destra a partire dal nodo corrente fino ad arrivare ad una foglia
    for( aux=this; aux->getRight(); aux=aux->getRight() );
    return aux;
  }
  
+ /** Trova il nodo dell'albero che ha valore minimo e ne restituisce il puntatore*/
  Bst *Bst::min()
  {
    Bst *aux;
+   // Si scorre l'albero verso il figlio di sinistra a partire dal nodo corrente fino ad arrivare ad una foglia  
    for( aux=this; aux->getLeft(); aux=aux->getLeft() );
    return aux;
  }
  
+ /** Restituisce il puntatore del nodo predecessore (Il nodo che ha valore maggiore tra quelli che hanno valore minore)*/
  Bst *Bst::predecessor()
  {
+   //Se il nodo corrente ha un figlio sinistro allora il predecessore è il massimo del sottoalbero di sinistra
    if ( getLeft() )
      return getLeft()->max();
  
+   //Altrimenti si risale l'albero fino ad arrivare al nodo che è il più basso antenato il cui figlio destro è un antenato. Si risale l'albero fino ad arrivare alla radice oppure alla prima svolta a sinistra
    Bst *aux1, *aux2;
    aux1 = getParent();
***************
*** 263,271 ****
  }
  
  Bst *Bst::successor()
  {
    if ( getRight() )
      return getRight()->min();
!   
    Bst *aux1, *aux2;
    aux1 = getParent();
--- 289,300 ----
  }
  
+ /** Restituisce il puntatore del nodo successore (Il nodo che ha valore minore tra quelli che hanno valore maggiore)*/
  Bst *Bst::successor()
  {
+   //Se il nodo corrente ha un figlio destro allora il successore è il minimo del sottoalbero di destra
    if ( getRight() )
      return getRight()->min();
!     
!   //Altrimenti si risale l'albero fino ad arrivare al nodo che è il più basso antenato il cui figlio sinistro è un antenato. Si risale l'albero fino ad arrivare alla radice oppure alla prima svolta a destra
    Bst *aux1, *aux2;
    aux1 = getParent();

Index: avlt.h
===================================================================
RCS file: /cvsroot/avl/avl/src/avlt.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** avlt.h	25 Jun 2004 16:05:57 -0000	1.5
--- avlt.h	18 Jul 2004 16:57:10 -0000	1.6
***************
*** 32,36 ****
  {
  private:
!   int fdb;
    Avlt *rightRotate();
    Avlt *leftRotate();
--- 32,36 ----
  {
  private:
!   int fdb; //Fattore di Bilanciamento
    Avlt *rightRotate();
    Avlt *leftRotate();