Menu
Coddy logo textTech
flag Ar iconالعربيةdown icon

حذف

الدرس 8 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.

يتكون الحذف من شجرة trie من جزأين. الجزء البسيط: ابحث عن العقدة الطرفية للكلمة واضبط isEndOfWord الخاصة بها مرة أخرى على false. بعد ذلك، لن يتم الإبلاغ عن الكلمة بواسطة search، وهو ما يهتم به المستخدمون.

الجزء الأكثر تعقيداً: تقليم العقد التي أصبحت الآن عديمة الفائدة. تكون العقدة الفرعية عديمة الفائدة إذا لم يكن لديها أطفال خاصون بها ولم تكن هي نفسها نهاية لكلمة أخرى - حيث لا يمكن الوصول إليها من خلال أي بحث مستقبلي أو تصفح للبادئات (prefix walk). نكتشف تلك العقد من خلال النزول بشكل متكرر، ثم التقليم أثناء العودة للأعلى.

كن حذراً في حالتين. إذا حاولت حذف كلمة لم يتم إدراجها مطلقاً، فلا تفعل شيئاً. إذا كانت الكلمة التي تحذفها هي بادئة لكلمة أخرى مخزنة (حذف "car" عندما تكون "card" موجودة أيضاً في الـ trie)، فيجب عليك مسح العلامة ولكن الاحتفاظ بجميع العقد - لا يزال من الممكن الوصول إلى تلك العقد بواسطة "card".

challenge icon

التحدي

متوسط

أضف طريقة 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;
}

جميع دروس Tries - سلسلة هياكل البيانات #8