Excluir
Lição 8 de 14 do curso Tries - Série de Estruturas de Dados #8 da Coddy.
Excluir de uma trie tem duas partes. A parte simples: encontre o nó terminal para a palavra e defina seu isEndOfWord de volta para false. Depois disso, a palavra não é mais reportada pelo search, que é o que importa para os usuários.
A parte mais complicada: podar os nós que agora são inúteis. Um nó filho é inútil se não tiver filhos próprios e não for ele mesmo o fim de alguma outra palavra - ele não pode ser alcançado por nenhuma busca futura ou caminhada de prefixo. Descobrimos esses nós descendo recursivamente e, em seguida, aparando no caminho de volta.
Tenha cuidado com dois casos. Se você tentar excluir uma palavra que nunca foi inserida, não faça nada. Se a palavra que você excluir for um prefixo de outra palavra armazenada (excluindo "car" quando "card" também estiver na trie), você deve limpar a flag, mas manter todos os nós - esses nós ainda são alcançáveis por "card".
Desafio
MédioAdicione um método delete à classe Trie.
Ele recebe uma string word:
- Se
wordestiver armazenada na trie, desmarque seu nó terminal (isEndOfWord = false) e remova quaisquer nós que agora se tornaram órfãos no caminho (nós sem filhos e que não são o fim de outra palavra). - Se
wordnão estiver na trie, não faça nada.
Uma maneira limpa de implementar a poda é um auxiliar recursivo que retorna um booleano informando ao chamador se o filho atual pode ser removido.
Experimente você mesmo
#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;
}