Trie（前綴樹）簡介

Trie 是一種樹狀資料結構，用於高效儲存和搜尋字串，特別是在自動完成、拼字檢查和IP 路由等應用程式中。

---

Trie 的關鍵屬性：

1. 節點：每個節點代表一個字元。
2. Root：根節點為空，作為起點。
3. 子節點：每個節點最多有 26 個子節點（小寫英文字母）或更多，取決於字元集。
4. 詞尾標記：標記一些節點以指示詞的結尾。

---

基本特里樹操作：

1. 插入

插入單字需要遍歷特里樹並為不存在的字元建立新節點。

2. 搜尋

搜尋透過遍歷單字的節點來檢查單字是否存在於 trie 中。

3. 前綴搜尋

這會檢查 trie 中是否有任何單字以給定的前綴開頭。

---

JavaScript 中基本 Trie 的實作：

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

---

進階 Trie 操作：

1. 刪除單字：

刪除單字涉及遞歸方法，即刪除不再需要的節點。

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. 計算有前綴的單字：

計算有多少個單字以給定前綴開頭。

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. 自動完成建議：

給定前綴，傳回以其開頭的所有單字。

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

---

時間複雜度：

1. 插入：O(L)（L = 單字長度）
2. 搜尋：O(L)
3. 前綴搜尋：O(L)
4. 刪除：O(L)

---

特里樹的應用：

1. 自動完成系統（例如搜尋列、文字編輯器）。
2. 拼字檢查器。
3. IP 路由（最長前綴匹配）。
4. 文字遊戲（例如，Boggle）。
5. DNA 序列匹配.

以上是Trie（前綴樹）簡介的詳細內容。更多資訊請關注PHP中文網其他相關文章！