Insérer des données dans un trie

Question

Donc j'essaye de insert des données dans un trie, et mon code fonctionne bien. Mais alors je change un peu ma fonction d'insertion et cela ne fonctionne plus et provoque également la fuite de mémoire. Pour moi, les deux versions de insert font la même chose mais évidemment, elles ne le sont pas. Quelqu'un peut-il m'expliquer pourquoi? Merci d'avance.

Voici le code qui fonctionne

#include <stdio.h> 
#include <stdbool.h> 
#include <ctype.h> 
#include <stdlib.h> 
#include <string.h> 

#define SIZE 26 

#define hash(c) (tolower(c) - (int)'a') 

typedef struct node{ 
    bool endWord; 
    struct node* children[SIZE]; 
} node; 

void freeTrie(node* root){ 

    if(root == NULL) return; 

    for (size_t i = 0; i < SIZE; i++) { 
     freeTrie(root->children[i]); 
    } 

    free(root); 
} 

node* newNode(){ 
    node* new = NULL; 

    new = (node*) malloc(sizeof(node)); 

    if(new != NULL){ 

     new->endWord = false; 

     for(int i = 0; i < SIZE; i++) 
      new->children[i] = NULL; 
    } 

    return new; 
} 

void insert(node* root, const char* data){ 

    node* temp = root; 

    for (size_t i = 0, len = strlen(data); i < len; i++) { 

     int index = hash(data[i]); 

     if(temp->children[index] == NULL){ 

      temp->children[index] = newNode(); 

      if (temp->children[index] /*still*/ == NULL){ 
       printf("Something went wrong\n"); 
       return; 
      } 
     } 

     temp = temp->children[index]; 
    } 
    temp->endWord = true; 
} 

bool search(node* root, const char* data){ 

    node* temp = root; 

    for (size_t i = 0, len = strlen(data); i < len; i++) { 

     int index = hash(data[i]); 

     temp = temp->children[index]; 

     if (temp == NULL){ 
      printf("search end here\n"); 
      return false; 
     } 
    } 

    return (temp != NULL && temp->endWord); 
} 

int main() { 

    char data[][8] = {"fox", "foo", "dog", "do"}; 

    node* root = newNode(); 

    if(root == NULL){ 
     printf("Something went wrong\n"); 
     return 1; 
    } 

    for (size_t i = 0, dataSize = sizeof(data)/sizeof(data[0]); i < dataSize; i++) { 
     insert(root, data[i]); 
    } 

    printf("Check: \n"); 

    char output[][32] = {"not found", "found"}; 

    // char s[5]; 
    // fscanf(stdin, "%s", s); 

    printf("%s\n", output[search(root, "fox")]); 

    freeTrie(root); 

    printf("Done\n"); 

    return 0; 
} 

Voici le insert qui me rend confus

void insert(node* root, const char* data){ 

    node* temp = root; 

    for (size_t i = 0, len = strlen(data); i < len; i++) { 

     int index = hash(data[i]); 

     temp = temp->children[index]; 

     if(temp == NULL){ 

      temp = newNode(); 

      if (temp /*still*/ == NULL){ 
       printf("Something went wrong\n"); 
       return; 
      } 
     } 
    } 

    temp->endWord = true; 
} 

PS: Je fais cela pour un problème posé du cours CS50x, où je charger un dictionnaire de 143091 mots (par ordre alphabétique) dans mon dictionnaire. Mon programme prend environ 0,1s à charger et 0,06s à décharger lorsque le personnel fait le même travail avec seulement 0.02s et 0.01s. Je ne suis pas autorisé à voir le code source du personnel, mais je suppose qu'ils ont utilisé un trie pour stocker des données. Comment puis-je améliorer mon code pour une exécution plus rapide? Serait-il plus rapide si je stocke des données dans un tableau, puis la recherche binaire à la place?

Answer 1

Lorsque vous écrivez

temp = temp->children[index]; 

vous copie valeur contenue dans temp->children[index] (je vais l'appeler A) dans une variable totalement indépendante nommée temp. Lorsque vous modifiez par la suite temp, vous modifiez temp uniquement, pas A. C'est-à-dire que tous les nouveaux noeuds ne sont pas insérés dans le trie.