Xóa

Bài học 8 trên 14 trong khóa học Cây tiền tố, chuỗi cấu trúc dữ liệu số 8 của Coddy.

Xóa một từ khỏi trie gồm hai phần. Phần đơn giản: tìm nút kết thúc của từ đó rồi đặt isEndOfWord về false. Sau đó, search sẽ không còn báo tìm thấy từ này, đúng như điều người dùng mong muốn.

Phần khó hơn: cắt bỏ những nút hiện không còn hữu ích. Một nút con không còn hữu ích nếu nó không có nút con nào và bản thân nó cũng không phải điểm kết thúc của một từ khác. Không có lượt tìm kiếm hay lần duyệt tiền tố nào sau này có thể đi đến nút đó. Ta tìm các nút này bằng cách gọi đệ quy đi xuống, rồi cắt bỏ chúng khi quay ngược lên.

Hãy chú ý hai trường hợp. Nếu bạn thử xóa một từ chưa từng được thêm vào, đừng làm gì cả. Nếu từ bạn xóa là tiền tố của một từ khác đã lưu (xóa "car" khi "card" cũng có trong trie), bạn phải xóa cờ nhưng giữ lại tất cả các nút. Các nút đó vẫn cần thiết để đi đến "card".

Thử thách

Trung bình

Thêm phương thức delete vào lớp Trie.

Phương thức nhận một chuỗi word:

Nếu word được lưu trong trie, bỏ đánh dấu nút cuối của từ (isEndOfWord = false) và xóa các nút không còn thuộc từ nào trên đường đi (các nút không có nút con và không phải là điểm kết thúc của từ khác).
Nếu word không có trong trie, không làm gì cả.

Một cách gọn gàng để tỉa các nút là dùng hàm trợ giúp đệ quy trả về giá trị boolean, cho biết nút con hiện tại có thể bị xóa hay không.

Tự làm thử

#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;
}

Tất cả bài học trong Cây tiền tố, chuỗi cấu trúc dữ liệu số 8

1Giới thiệu

Giới thiệu Trie là gì?

2Dự án Trie

Lớp TrieNode Lớp Trie Chèn Tìm kiếm Bắt đầu bằngXóaSố lượng từ

3Thử thách luyện tập

Tiền tố chung dài nhất Đếm từ có tiền tố Tự động hoàn thành Từ dài nhất trong từ điển Tách từ

Tự luyện tập: Trình biên dịch C online