Eliminazione
Lezione 8 di 14 del corso Trie - Serie sulle strutture dati n. 8 di Coddy.
L’eliminazione da un trie ha due parti. La parte semplice: trova il nodo terminale della parola e reimposta il suo isEndOfWord su false. Dopodiché, la parola non viene più restituita da search, che è ciò che interessa agli utenti.
La parte più complicata: elimina i nodi che ora sono inutili. Un nodo figlio è inutile se non ha figli propri e non è a sua volta la fine di un’altra parola: non può essere raggiunto da alcuna ricerca o visita di prefisso futura. Individuiamo questi nodi ricorrendo verso il basso, quindi li rimuoviamo risalendo.
Fai attenzione a due casi. Se provi a eliminare una parola che non è mai stata inserita, non fare nulla. Se la parola che elimini è un prefisso di un’altra parola memorizzata (eliminando "car" quando "card" è anch’essa nel trie), devi azzerare il flag ma mantenere tutti i nodi: questi nodi sono ancora raggiungibili tramite "card".
Sfida
MedioAggiungi un metodo delete alla classe Trie.
Riceve una stringa word:
- Se
wordè memorizzata nel trie, deseleziona il nodo terminale (isEndOfWord = false) e rimuovi gli eventuali nodi rimasti orfani lungo il percorso (nodi senza figli e che non sono la fine di un'altra parola). - Se
wordnon è nel trie, non fare nulla.
Un modo semplice per implementare la potatura consiste nell'usare una funzione ausiliaria ricorsiva che restituisce un booleano per indicare al chiamante se il figlio corrente può essere rimosso.
Provalo tu
#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;
}
Tutte le lezioni di Trie - Serie sulle strutture dati n. 8
Esercitati da solo: Compilatore C online