Suppression
Leçon 8 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
Supprimer d'un trie comporte deux parties. La partie simple : trouver le nœud terminal pour le mot et remettre son isEndOfWord à false. Après cela, le mot n'est plus renvoyé par search, ce qui est ce qui importe aux utilisateurs.
La partie la plus délicate : élaguer les nœuds qui sont désormais inutiles. Un nœud enfant est inutile s'il n'a pas d'enfants propres et n'est pas lui-même la fin d'un autre mot - il ne peut être atteint par aucune recherche future ou parcours de préfixe. Nous découvrons ces nœuds en descendant par récursion, puis en les supprimant lors de la remontée.
Faites attention à deux cas. Si vous essayez de supprimer un mot qui n'a jamais été inséré, ne faites rien. Si le mot que vous supprimez est un préfixe d'un autre mot stocké (supprimer "car" quand "card" est également dans le trie), vous devez effacer le drapeau mais conserver tous les nœuds - ces nœuds sont toujours accessibles par "card".
Défi
MoyenAjoutez une méthode delete à la classe Trie.
Elle reçoit une chaîne de caractères word :
- Si
wordest stocké dans le trie, décochez son nœud terminal (isEndOfWord = false) et supprimez tous les nœuds devenus orphelins en chemin (nœuds sans enfants et qui ne sont pas la fin d'un autre mot). - Si
wordn'est pas dans le trie, ne faites rien.
Une manière propre d'implémenter l'élagage est d'utiliser un assistant récursif qui renvoie un booléen indiquant à l'appelant si l'enfant actuel peut être supprimé.
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); }
if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "delete") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_delete(&t, arg); }
}
return 0;
}