Eliminar
Lección 8 de 14 del curso Tries - Serie de Estructuras de Datos #8 de Coddy.
Eliminar de un trie consta de dos partes. La parte sencilla: encontrar el nodo terminal de la palabra y volver a establecer su isEndOfWord a false. Después de eso, la palabra ya no será reportada por search, que es lo que les importa a los usuarios.
La parte más complicada: podar los nodos que ahora son inútiles. Un nodo hijo es inútil si no tiene hijos propios y no es en sí mismo el final de alguna otra palabra; no se puede llegar a él mediante ninguna búsqueda futura o recorrido de prefijos. Descubrimos esos nodos bajando mediante recursión y luego recortando al volver a subir.
Tenga cuidado con dos casos. Si intenta eliminar una palabra que nunca fue insertada, no haga nada. Si la palabra que elimina es un prefijo de otra palabra almacenada (por ejemplo, eliminar "car" cuando "card" también está en el trie), debe limpiar la bandera pero mantener todos los nodos; esos nodos aún son accesibles mediante "card".
Desafío
IntermedioAgrega un método delete a la clase Trie.
Este recibe una cadena word:
- Si
wordestá almacenada en el trie, desmarca su nodo terminal (isEndOfWord = false) y elimina cualquier nodo que ahora sea huérfano en el camino (nodos sin hijos y que no sean el final de otra palabra). - Si
wordno está en el trie, no hagas nada.
Una forma limpia de implementar la poda es mediante un ayudante recursivo que devuelva un booleano indicando al llamador si el hijo actual puede ser eliminado.
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); }
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;
}