Usuwanie
Lekcja 8 z 14 w kursie Drzewa Trie — struktury danych #8 w Coddy.
Usuwanie z trie składa się z dwóch części. Prosta część: znajdź węzeł końcowy dla słowa i ustaw jego isEndOfWord z powrotem na false. Po tym słowo nie będzie już zwracane przez search, na czym zależy użytkownikom.
Trudniejsza część: usuń węzły, które są teraz bezużyteczne. Węzeł potomny jest bezużyteczny, jeśli nie ma własnych potomków i sam nie jest końcem żadnego innego słowa — nie można do niego dotrzeć podczas żadnego przyszłego wyszukiwania ani przechodzenia po prefiksach. Odkrywamy te węzły, rekurencyjnie przechodząc w dół, a następnie usuwamy je podczas powrotu w górę.
Uważaj na dwa przypadki. Jeśli spróbujesz usunąć słowo, które nigdy nie zostało wstawione, nic nie rób. Jeśli usuwane słowo jest prefiksem innego przechowywanego słowa (usuwasz "car", gdy "card" również znajduje się w trie), musisz wyczyścić flagę, ale zachować wszystkie węzły — nadal można do nich dotrzeć za pomocą "card".
Wyzwanie
ŚredniDodaj metodę delete do klasy Trie.
Przyjmuje ona ciąg znaków word:
- Jeśli
wordjest zapisane w drzewie trie, odznacz jego węzeł końcowy (isEndOfWord = false) i usuń wszystkie osierocone węzły powstałe po drodze (węzły bez dzieci, które nie są końcem innego słowa). - Jeśli
wordnie ma w drzewie trie, nie rób nic.
Przejrzystym sposobem implementacji przycinania jest rekurencyjna funkcja pomocnicza, która zwraca wartość logiczną informującą wywołującego, czy bieżące dziecko można usunąć.
Spróbuj swoich sił
#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;
}
Wszystkie lekcje w sekcji Drzewa Trie — struktury danych #8
Poćwicz samodzielnie: Kompilator C online