حذف
الدرس 8 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
يتكون الحذف من شجرة trie من جزأين. الجزء البسيط: ابحث عن العقدة الطرفية للكلمة واضبط isEndOfWord الخاصة بها مرة أخرى على false. بعد ذلك، لن يتم الإبلاغ عن الكلمة بواسطة search، وهو ما يهتم به المستخدمون.
الجزء الأكثر تعقيداً: تقليم العقد التي أصبحت الآن عديمة الفائدة. تكون العقدة الفرعية عديمة الفائدة إذا لم يكن لديها أطفال خاصون بها ولم تكن هي نفسها نهاية لكلمة أخرى - حيث لا يمكن الوصول إليها من خلال أي بحث مستقبلي أو تصفح للبادئات (prefix walk). نكتشف تلك العقد من خلال النزول بشكل متكرر، ثم التقليم أثناء العودة للأعلى.
كن حذراً في حالتين. إذا حاولت حذف كلمة لم يتم إدراجها مطلقاً، فلا تفعل شيئاً. إذا كانت الكلمة التي تحذفها هي بادئة لكلمة أخرى مخزنة (حذف "car" عندما تكون "card" موجودة أيضاً في الـ trie)، فيجب عليك مسح العلامة ولكن الاحتفاظ بجميع العقد - لا يزال من الممكن الوصول إلى تلك العقد بواسطة "card".
التحدي
متوسطأضف طريقة delete إلى فئة Trie.
تستقبل هذه الطريقة سلسلة نصية word:
- إذا كانت
wordمخزنة في الـ trie، فقم بإلغاء تحديد عقدتها الطرفية (isEndOfWord = false) وقم بإزالة أي عقد أصبحت الآن "يتيمة" في الطريق (العقد التي ليس لها أبناء وليست نهاية كلمة أخرى). - إذا لم تكن
wordموجودة في الـ trie، فلا تفعل شيئاً.
الطريقة الأنيقة لتنفيذ عملية التقليم (pruning) هي استخدام دالة مساعدة عودية (recursive helper) تعيد قيمة منطقية (boolean) تخبر المستدعي ما إذا كان يمكن إزالة الابن الحالي.
جرّب بنفسك
#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;
}