Silme
Coddy'nin Trie - Veri Yapıları Serisi #8 kursunda ders 8 / 14.
Bir trie'den silme işleminin iki bölümü vardır. Basit kısım: kelime için terminal düğümünü bulun ve isEndOfWord değerini tekrar false olarak ayarlayın. Bundan sonra kelime artık search tarafından raporlanmaz, ki kullanıcıların önemsediği de budur.
Daha zor kısım: artık işe yaramayan düğümleri budayın. Bir çocuk düğüm, kendi çocukları yoksa ve kendisi başka bir kelimenin sonu değilse işe yaramazdır - gelecekteki herhangi bir arama veya önek gezintisi ile ona ulaşılamaz. Bu düğümleri aşağı doğru özyineleme yaparak keşfederiz, ardından yukarı dönüş yolunda budama yaparız.
İki duruma dikkat edin. Hiç eklenmemiş bir kelimeyi silmeye çalışırsanız hiçbir şey yapmayın. Sildiğiniz kelime saklanan başka bir kelimenin önekiyse (trie'de "card" varken "car" kelimesini silmek gibi), bayrağı temizlemeli ancak tüm düğümleri tutmalısınız - bu düğümlere hala "card" üzerinden ulaşılabilir.
Görev
OrtaTrie sınıfına bir delete metodu ekleyin.
Bu metot bir word dizesi alır:
- Eğer
wordtrie içinde saklanıyorsa, terminal düğümünün işaretini kaldırın (isEndOfWord = false) ve yol üzerindeki artık yetim kalan düğümleri (hiç çocuğu olmayan ve başka bir kelimenin sonu olmayan düğümler) kaldırın. - Eğer
wordtrie içinde değilse, hiçbir şey yapmayın.
Budama işlemini uygulamanın temiz bir yolu, çağırana mevcut çocuğun kaldırılıp kaldırılamayacağını söyleyen bir boolean döndüren özyinelemeli (recursive) bir yardımcı fonksiyon kullanmaktır.
Kendin dene
#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;
}