מחיקה
שיעור 8 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8 של Coddy.
מחיקה מטריי מורכבת משני חלקים. החלק הפשוט: מוצאים את צומת הסיום של המילה ומחזירים את isEndOfWord ל־false. לאחר מכן, search כבר לא מדווחת על המילה, וזה מה שחשוב למשתמשים.
החלק המורכב יותר: מסירים צמתים שכבר אין בהם צורך. צומת בן מיותר אם אין לו ילדים משלו והוא אינו בעצמו סוף של מילה אחרת — אי אפשר להגיע אליו בחיפוש או במעבר קידומת עתידיים. אנחנו מאתרים את הצמתים האלה באמצעות רקורסיה כלפי מטה, ואז מסירים אותם בדרך חזרה למעלה.
חשוב להקפיד על שני מקרים. אם מנסים למחוק מילה שמעולם לא הוכנסה, לא עושים דבר. אם המילה שמוחקים היא קידומת של מילה אחרת שנשמרה (מחיקת "car" כאשר "card" נמצאת גם היא בטריי), צריך לאפס את הדגל, אבל להשאיר את כל הצמתים — עדיין אפשר להגיע אליהם באמצעות "card".
אתגר
בינוניהוסיפו מתודה delete למחלקה Trie.
היא מקבלת מחרוזת word:
- אם
wordמאוחסנת בטריי, בטלו את הסימון של צומת הסיום שלה (isEndOfWord = false) והסירו צמתים שהתייתמו בעקבות זאת לאורך הדרך (צמתים ללא ילדים שאינם סופו של מילה אחרת). - אם
wordאינה נמצאת בטריי, אל תעשו דבר.
דרך נקייה למימוש הגיזום היא להשתמש בפונקציית עזר רקורסיבית שמחזירה ערך בוליאני, המורה לקורא אם ניתן להסיר את הילד הנוכחי.
נסו בעצמכם
#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;
}
כל השיעורים ביחידה טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8
תרגלו בעצמכם: קומפיילר C אונליין