Insertar
Lección 5 de 14 del curso Tries - Serie de Estructuras de Datos #8 de Coddy.
Para insertar una palabra en el trie, descienda desde la raíz un carácter a la vez. Para cada carácter de la palabra: si el nodo actual no tiene un hijo para ese carácter, cree un nuevo TrieNode y adjúntelo. De cualquier manera, muévase a ese hijo y continúe con el siguiente carácter.
Cuando llegue al final de la palabra, marque el nodo en el que aterrizó con isEndOfWord = true. Esa bandera es lo que luego distingue una palabra real almacenada de una ruta que simplemente existe porque es un prefijo de otra cosa.
Insertar "cat" y luego "car" comparte la ruta c -> a y solo se ramifica en el tercer carácter. Ese intercambio es lo que hace que los tries sean tan eficientes en espacio para los diccionarios.
Desafío
FácilAgrega un método insert a la clase Trie.
Este recibe una cadena word y la almacena en el trie:
- Comienza en el
root. Para cada caráctercenword, si el nodo actual no tiene un hijo parac, agrega un nuevoTrieNodeallí. - Muévete hacia ese hijo y continúa.
- Después del último carácter, marca el
isEndOfWorddel nodo final comotrue.
Pruébalo tú mismo
#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;
}