Insertion
Leçon 5 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
Pour insérer un mot dans le trie, descendez à partir de la racine un caractère à la fois. Pour chaque caractère du mot : si le nœud actuel n'a pas d'enfant pour ce caractère, créez un nouveau TrieNode et attachez-le. Dans les deux cas, déplacez-vous dans cet enfant et continuez avec le caractère suivant.
Lorsque vous atteignez la fin du mot, marquez le nœud sur lequel vous vous trouvez avec isEndOfWord = true. Ce drapeau est ce qui permet plus tard de distinguer un mot réellement stocké d'un chemin qui existe simplement parce qu'il est le préfixe d'autre chose.
L'insertion de "cat" puis de "car" partage le chemin c -> a et ne bifurque qu'au troisième caractère. Ce partage est ce qui rend les tries si économes en espace pour les dictionnaires.
Défi
FacileAjoutez une méthode insert à la classe Trie.
Elle reçoit une chaîne de caractères word et la stocke dans le trie :
- Commencez à la
root. Pour chaque caractèrecdansword, si le nœud actuel n'a pas d'enfant pourc, ajoutez un nouveauTrieNodeà cet endroit. - Déplacez-vous vers cet enfant et continuez.
- Après le dernier caractère, marquez le
isEndOfWorddu nœud final commetrue.
Essayez vous-même
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
}
return 0;
}