Löschen
Lektion 8 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Das Löschen aus einem Trie besteht aus zwei Teilen. Der einfache Teil: Finden Sie den Endknoten für das Wort und setzen Sie dessen isEndOfWord zurück auf false. Danach wird das Wort nicht mehr von search gemeldet, was das ist, was die Benutzer interessiert.
Der schwierigere Teil: Knoten entfernen, die nun nutzlos sind. Ein Kindknoten ist nutzlos, wenn er selbst keine Kinder hat und nicht selbst das Ende eines anderen Wortes ist – er kann durch keine zukünftige Suche oder Präfix-Durchquerung erreicht werden. Wir entdecken diese Knoten, indem wir rekursiv nach unten gehen und sie dann auf dem Rückweg nach oben kürzen.
Seien Sie bei zwei Fällen vorsichtig. Wenn Sie versuchen, ein Wort zu löschen, das nie eingefügt wurde, tun Sie nichts. Wenn das Wort, das Sie löschen, ein Präfix eines anderen gespeicherten Wortes ist (beim Löschen von "car", wenn "card" ebenfalls im Trie enthalten ist), müssen Sie das Flag löschen, aber alle Knoten behalten – diese Knoten sind weiterhin über "card" erreichbar.
Aufgabe
MittelFügen Sie der Klasse Trie eine Methode delete hinzu.
Sie erhält einen String word:
- Wenn
wordim Trie gespeichert ist, heben Sie die Markierung des Endknotens auf (isEndOfWord = false) und entfernen Sie alle nun verwaisten Knoten auf dem Weg (Knoten ohne Kinder, die nicht das Ende eines anderen Wortes sind). - Wenn
wordnicht im Trie enthalten ist, unternehmen Sie nichts.
Ein sauberer Weg, das Bereinigen (Pruning) zu implementieren, ist ein rekursiver Helfer, der einen booleschen Wert zurückgibt, der dem Aufrufer mitteilt, ob das aktuelle Kind entfernt werden kann.
Probier es selbst
#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;
}