[C] - Esercizio albero di ricerca binaria

[Gabry610]

Buongiorno a tutti!
Sto studiando per l'esame di programmazione di settembre e sono incappato in un esercizio che non mi convince del tutto.
Mi sto preparando sul noto libro di Deitel & Deitel - "C Corso completo di programmazione". Il materiale che vi allego è completamente opensource e scaricabile dal sito dell'editore.

L'esercizio in questione è il "Fig12.19" del capitolo "Le strutture dati in C", per coloro che avessero a disposizione il testo.
In sostanza, il programma mostra l'inserimento di dati all'interno di un albero binario. Il codice è il seguente:

/* Fig. 12.19: fig12_19.c
   Create a binary tree and traverse it 
   preorder, inorder, and postorder */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* self-referential structure */
struct treeNode { 
   struct treeNode *leftPtr; /* pointer to left subtree */
   int data; /* node value */
   struct treeNode *rightPtr; /* pointer to right subtree */
}; /* end structure treeNode */

typedef struct treeNode TreeNode; /* synonym for struct treeNode */
typedef TreeNode *TreeNodePtr; /* synonym for TreeNode* */

/* prototypes */
void insertNode( TreeNodePtr *treePtr, int value );
void inOrder( TreeNodePtr treePtr );
void preOrder( TreeNodePtr treePtr );
void postOrder( TreeNodePtr treePtr );

/* function main begins program execution */
int main( void )
{ 
   int i; /* counter to loop from 1-10 */
   int item; /* variable to hold random values */
   TreeNodePtr rootPtr = NULL; /* tree initially empty */

   srand( time( NULL ) ); 
   printf( "The numbers being placed in the tree are:\n" );

   /* insert random values between 0 and 14 in the tree */
   for ( i = 1; i <= 10; i++ ) { 
      item = rand() % 15;
      printf( "%3d", item );
      insertNode( &rootPtr, item );
   } /* end for */

   /* traverse the tree preOrder */
   printf( "\n\nThe preOrder traversal is:\n" );
   preOrder( rootPtr );

   /* traverse the tree inOrder */
   printf( "\n\nThe inOrder traversal is:\n" );
   inOrder( rootPtr );

   /* traverse the tree postOrder */
   printf( "\n\nThe postOrder traversal is:\n" );
   postOrder( rootPtr );
   return 0; /* indicates successful termination */
} /* end main */

/* insert node into tree */
void insertNode( TreeNodePtr *treePtr, int value )
{ 
   /* if tree is empty */
   if ( *treePtr == NULL ) {   
      *treePtr = malloc( sizeof( TreeNode ) );

      /* if memory was allocated then assign data */
      if ( *treePtr != NULL ) { 
         ( *treePtr )->data = value;
         ( *treePtr )->leftPtr = NULL;
         ( *treePtr )->rightPtr = NULL;
      } /* end if */
      else {
         printf( "%d not inserted. No memory available.\n", value );
      } /* end else */
   } /* end if */
   else { /* tree is not empty */
      /* data to insert is less than data in current node */
      if ( value < ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->leftPtr ), value );
      } /* end if */

      /* data to insert is greater than data in current node */
      else if ( value > ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->rightPtr ), value );
      } /* end else if */
      else { /* duplicate data value ignored */
         printf( "dup" );
      } /* end else */
   } /* end else */
} /* end function insertNode */

/* begin inorder traversal of tree */
void inOrder( TreeNodePtr treePtr )
{ 
   /* if tree is not empty then traverse */
   if ( treePtr != NULL ) { 
      inOrder( treePtr->leftPtr );
      printf( "%3d", treePtr->data );
      inOrder( treePtr->rightPtr );
   } /* end if */
} /* end function inOrder */

/* begin preorder traversal of tree */
void preOrder( TreeNodePtr treePtr )
{ 
   /* if tree is not empty then traverse */
   if ( treePtr != NULL ) { 
      printf( "%3d", treePtr->data );
      preOrder( treePtr->leftPtr );
      preOrder( treePtr->rightPtr );
   } /* end if */
} /* end function preOrder */

/* begin postorder traversal of tree */
void postOrder( TreeNodePtr treePtr )
{ 
   /* if tree is not empty then traverse */
   if ( treePtr != NULL ) { 
      postOrder( treePtr->leftPtr );
      postOrder( treePtr->rightPtr );
      printf( "%3d", treePtr->data );
   } /* end if */
} /* end function postOrder */



/**************************************************************************
 * (C) Copyright 1992-2010 by Deitel & Associates, Inc. and               *
 * Pearson Education, Inc. All Rights Reserved.                           *
 *                                                                        *
 * DISCLAIMER: The authors and publisher of this book have used their     *
 * best efforts in preparing the book. These efforts include the          *
 * development, research, and testing of the theories and programs        *
 * to determine their effectiveness. The authors and publisher make       *
 * no warranty of any kind, expressed or implied, with regard to these    *
 * programs or to the documentation contained in these books. The authors *
 * and publisher shall not be liable in any event for incidental or       *
 * consequential damages in connection with, or arising out of, the       *
 * furnishing, performance, or use of these programs.                     *
 *************************************************************************/

La mia attenzione va soprattutto all'utilizzo della funzione insertNode. L'inizio mi è chiaro, cioè ho capito che se l'albero è vuoto, il nuovo dato farà parte di un nodo che verrà inserito come nodo "iniziale" dell'albero (nodo padre esclusivo). Il problema che ho io è nel comprendere appieno la parte seguente, ovvero:

if ( value < ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->leftPtr ), value );
      } /* end if */

      /* data to insert is greater than data in current node */
      else if ( value > ( *treePtr )->data ) {
         insertNode( &( ( *treePtr )->rightPtr ), value );
      } /* end else if */

Se il valore passato a insertNode è minore o maggiore del nodo corrente, la funzione verrà richiamata in modo ricorsivo passando rispettivamente l'indirizzo del sottoalbero sinistro o destro.
E' chiaro, ma secondo me non è del tutto esatto!
Mi spiego: così facendo, viene ignorato ad ogni ciclo un ramo di (sotto)albero.
Se un certo valore è minore del nodo, verrà considerato il suo sottonodo sinistro (il sottonodo DESTRO non verrà più riconsiderato e rimarrà senza sottonodi). Il sottonodo destro è destinato a rimanere così, perchè mi sembra che il passaggio iterativo continui a partire dal sottonodo sinistro: ancora se si considera un altro valore (maggiore o minore) di questo sottonodo sinistro, verrà rievocata la funzione insertNode con l'indirizzo del suo sottonodo (destro o sinistro). In altre parole, scelto un nodo si considereranno sempre i suoi sottonodi e così via, perdendo il legame col nodo "fratello".

Secondo voi è corretta come interpretazione?
Mi scuso, mi rendo pienamente conto che a parole possa risultare estremamente contorto; vi chiedo se per favore potete fare questo sforzo per aiutarmi a dileguare i miei dubbi!

[wingman87]

Mi spiego: così facendo, viene ignorato ad ogni ciclo un ramo di (sotto)albero.
Se un certo valore è minore del nodo, verrà considerato il suo sottonodo sinistro (il sottonodo DESTRO non verrà più riconsiderato e rimarrà senza sottonodi).

Il ramo destro rimarrà senza nodi fintantoché non verrà inserito un valore > della radice.
Inserendo i nodi in questo modo con una visita in preordine ottieni i numeri ordinati.
Ma forse questo non risponde ai tuoi dubbi?

[demos88]

Originariamente inviato da Gabry610

Mi spiego: così facendo, viene ignorato ad ogni ciclo un ramo di (sotto)albero.
Se un certo valore è minore del nodo, verrà considerato il suo sottonodo sinistro (il sottonodo DESTRO non verrà più riconsiderato e rimarrà senza sottonodi). Il sottonodo destro è destinato a rimanere così, perchè mi sembra che il passaggio iterativo continui a partire dal sottonodo sinistro: ancora se si considera un altro valore (maggiore o minore) di questo sottonodo sinistro, verrà rievocata la funzione insertNode con l'indirizzo del suo sottonodo (destro o sinistro). In altre parole, scelto un nodo si considereranno sempre i suoi sottonodi e così via, perdendo il legame col nodo "fratello".

A me sembra corretto... non capisco il tuo dubbio sul sottonodo sinistro.
Partendo dalla radice, l'insert va a cercare la posizione nell'albero dove inserire il nodo. Se il valore da inserire è minore del nodo corrente, scende nel sottoalbero sinistro, altrimenti destro (se è uguale viene ignorato e finisce) ricorsivamente fino a che non trova un nodo NULL, ovvero un figlio sinistro o destro che ancora non esiste, e lo crea.
Non capisco quale sia il problema di "ignorare" un sottoalbero ad ogni ciclo, un valore può essere o maggiore o minore o uguale a un altro, non può essere sia minore che maggiore. Se è minore, lascio perdere il sottoalbero destro e viceversa per ogni nodo. Il fatto di ignorare ad ogni passaggio una parte dell'albero è il motivo principale per cui si usano gli alberi, ovvero poter ottenere l'estrazione o l'inserimento ordinato di valori mediante una operazione di complessità O(log(n)).
Nel caso peggiore, che forse è quello che ti sta creando confusione, ho un albero i cui nodi hanno solo figli sinistri o solo figli destri, ma tale situazione è possibile solo se inserisco un set di valori ordinatamente crescenti o descrescenti. In questo caso il BST (albero di ricerca binario) diventa meno efficiente e gli inserimenti comportano una complessità O(n).
Questa problematica è mitigata dagli alberi AVL che integrano un meccanismo di bilanciamento dell'albero.


ps: Hai provato il codice?

[Gabry610]

A me non sembra. Supponiamo ad esempio di avere un albero con un solo nodo che contiene il valore 10.
Viene passato alla funzione il valore 9. A questo punto la funzione richiamerà se stessa in questo modo:

 insertNode( &( ( *treePtr )->leftPtr ), value );

Supponiamo adesso che venga passato il valore 11.
La funzione richiamerà se stessa in questo modo:

 insertNode( &( ( *treePtr )->rightPtr ), value );

Ma a questo punto:

( *treePtr )->rightPtr

indicherà il nodo DESTRO di quello che prima era il SINISTRO di quello iniziale secondo me.

Schematizzerei in questo modo:



P.S. Scusami demos, ho fatto crossposting con te quindi ho letto la tua risposta dopo questo messaggio!

[demos88]

Ah ho capito il tuo dubbio, ma l'albero fa proprio quello che tu ti aspetti sia giusto, solo che forse ti perdi sulla ricorsione e sulla visibilità di quei puntatori. Infatti ogni inserimento non parte dall'ultimo nodo inserito o dal suo padre, ma parte sempre dalla radice.
Ne hai un esempio proprio nel codice che hai postato:

 /* insert random values between 0 and 14 in the tree */
   for ( i = 1; i <= 10; i++ ) { 
      item = rand() % 15;
      printf( "%3d", item );
      insertNode( &rootPtr, item );
   } /* end for */

per ogni valore random, viene effettuato un inserimento richiamando insertNode sulla radice dell'albero. Proprio come deve essere

[Gabry610]

Hai ragione. Riparte sempre dall'inizio dell'albero a fare il controllo

Ti ringrazio demos