Hapus

Pelajaran 8 dari 14 dalam kursus Trie: Struktur Data Seri #8 di Coddy.

Menghapus kata dari trie terdiri dari dua bagian. Bagian yang sederhana: temukan node terminal untuk kata tersebut, lalu ubah isEndOfWord kembali menjadi false. Setelah itu, search tidak lagi melaporkan kata tersebut, dan itulah yang penting bagi pengguna.

Bagian yang lebih rumit: pangkas node yang kini tidak berguna. Node anak tidak berguna jika tidak memiliki anak sendiri dan bukan akhir dari kata lain, node tersebut tidak dapat dijangkau oleh pencarian atau penelusuran prefix di masa mendatang. Kita menemukan node-node itu dengan melakukan rekursi ke bawah, lalu memangkasnya saat kembali ke atas.

Perhatikan dua kasus. Jika kamu mencoba menghapus kata yang belum pernah disisipkan, jangan lakukan apa pun. Jika kata yang kamu hapus merupakan prefix dari kata lain yang tersimpan, misalnya menghapus "car" saat "card" juga ada di trie, kamu harus menghapus tandanya, tetapi tetap mempertahankan semua node, karena node-node itu masih dapat dijangkau melalui "card".

Tantangan

Sedang

Tambahkan method delete ke class Trie.

Method ini menerima string word:

Jika word tersimpan di trie, hapus penanda pada node terminalnya (isEndOfWord = false) dan hapus node yang kini tidak memiliki induk dalam perjalanan tersebut, yaitu node tanpa anak yang bukan akhir dari kata lain.
Jika word tidak ada di trie, jangan lakukan apa pun.

Cara yang rapi untuk menerapkan pemangkasan adalah dengan helper rekursif yang mengembalikan boolean untuk memberi tahu pemanggil apakah child saat ini dapat dihapus.

Coba sendiri

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

Semua pelajaran di Trie: Struktur Data Seri #8

1Pengenalan

Pengenalan Apa Itu Trie?

2Proyek Trie

class TrieNode class Trie Sisipkan Cari Diawali DenganHapusJumlah Kata

3Tantangan Latihan

Prefiks Bersama Terpanjang Hitung Kata dengan Prefiks Pelengkapan Otomatis Kata Terpanjang dalam Dictionary Pemisahan Kata

Latihan sendiri: Compiler C online