Pengenalan kepada Trie (Pokok Awalan)

A Trie ialah struktur data seperti pepohon yang digunakan untuk menyimpan dan mencari rentetan dengan cekap, terutamanya dalam aplikasi seperti autolengkap, semakan ejaan dan penghalaan IP.

---

Sifat Utama Trie:

1. Nod: Setiap nod mewakili aksara.
2. Akar: Nod akar kosong dan berfungsi sebagai titik permulaan.
3. Kanak-kanak: Setiap nod mempunyai sehingga 26 kanak-kanak (untuk huruf Inggeris huruf kecil) atau lebih, bergantung pada set aksara.
4. Penanda Akhir Kata: Beberapa nod ditandakan untuk menunjukkan penghujung perkataan.

---

Operasi Percubaan Asas:

1. Sisipan

Memasukkan perkataan melibatkan merentasi trie dan mencipta nod baharu untuk aksara yang tidak wujud.

2. Cari

Carian menyemak sama ada perkataan wujud dalam trie dengan merentasi nodnya.

3. Carian Awalan

Ini menyemak sama ada sebarang perkataan dalam percubaan bermula dengan awalan yang diberikan.

---

Pelaksanaan Ujian Asas dalam JavaScript:

class TrieNode {
    constructor() {
        this.children = {}; // Stores child nodes
        this.isEndOfWord = false; // Marks the end of a word
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // Insert a word
    insert(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true; // Mark the end of the word
    }

    // Search for a word
    search(word) {
        let node = this.root;
        for (let char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    // Check if any word starts with the given prefix
    startsWith(prefix) {
        let node = this.root;
        for (let char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

// Example usage
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

---

Operasi Percubaan Lanjutan:

1. Padamkan Perkataan:

Memadamkan perkataan melibatkan pendekatan rekursif, di mana kami mengalih keluar nod yang tidak diperlukan lagi.

delete(word, node = this.root, depth = 0) {
    if (depth === word.length) {
        if (!node.isEndOfWord) return false; // Word doesn't exist
        node.isEndOfWord = false;
        return Object.keys(node.children).length === 0; // Check if node has children
    }

    const char = word[depth];
    if (!node.children[char]) return false;

    const shouldDeleteChild = this.delete(word, node.children[char], depth + 1);

    if (shouldDeleteChild) {
        delete node.children[char];
        return Object.keys(node.children).length === 0 && !node.isEndOfWord;
    }

    return false;
}

2. Kira Perkataan dengan Awalan:

Kira bilangan perkataan yang bermula dengan awalan yang diberikan.

countWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return 0;
        node = node.children[char];
    }
    return this._countWords(node);
}

_countWords(node) {
    let count = node.isEndOfWord ? 1 : 0;
    for (let char in node.children) {
        count += this._countWords(node.children[char]);
    }
    return count;
}

3. Cadangan Autolengkap:

Diberi awalan, kembalikan semua perkataan yang bermula dengannya.

getWordsWithPrefix(prefix) {
    let node = this.root;
    for (let char of prefix) {
        if (!node.children[char]) return [];
        node = node.children[char];
    }
    return this._collectWords(node, prefix);
}

_collectWords(node, prefix) {
    let results = [];
    if (node.isEndOfWord) results.push(prefix);

    for (let char in node.children) {
        results = results.concat(this._collectWords(node.children[char], prefix + char));
    }

    return results;
}

---

Kerumitan Masa:

1. Sisipkan: O(L) (L = panjang perkataan)
2. Cari: O(L)
3. Carian Awalan: O(L)
4. Padam: O(L)

---

Aplikasi Trie:

1. Sistem Autolengkap (cth., bar carian, editor teks).
2. Pemeriksa Ejaan.
3. Penghalaan IP (padanan awalan terpanjang).
4. Permainan Kata (cth., Boggle).
5. Padanan Jujukan DNA.

Atas ialah kandungan terperinci Pengenalan kepada Trie (Pokok Awalan). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!