Trie

是一種類似樹的數據結構，用於有效存儲和搜索字符串，尤其是在諸如AutoComplete，Spell Checking和IP路由之類的應用程序中。

Trie的關鍵特性：

---

nodes

：每個節點代表一個字符。
1. ：root節點是空的，並用作起點。
2. ：每個節點最多有26個孩子（用於小寫英文字母）或更多，具體取決於字符集。 字標記
：有些節點被標記為指示單詞的結尾。
基本的Trie操作：
4. 1。 insertion

---

插入一個單詞涉及穿越Trie並為不存在的字符創建新節點。

2。

搜尋

搜索通過遍歷其節點是否存在一個單詞是否存在。

3。

前綴搜索

這檢查了三位一體中的任何單詞是否從給定的前綴開頭。

JavaScript中基本Trie的實現：

類Trienode { constructor（）{ this.Children = {}; //存儲兒童節點 this.isendofword = false; //標記一個單詞的結尾 } } 類Trie { constructor（）{ this.root = new Trienode（）; } //插入一個單詞 插入（word）{ 令node = this.root; for（讓詞字符）{ 如果（！node.children [char]）{ Node.Children [char] = new Trienode（）; } node = node.Children [char]; } node.isendofword = true; //標記單詞的結尾 } //搜索一個單詞 搜索（Word）{ 令node = this.root; for（讓詞字符）{ 如果（！node.children [char]）{ 返回false; } node = node.Children [char]; } 返回node.isendofword; } //檢查是否有任何單詞從給定的前綴開始 startswith（前綴）{ 令node = this.root; 對於（讓前綴的字符）{ 如果（！node.children [char]）{ 返回false; } node = node.Children [char]; } 返回true; } } //示例用法 const trie = new trie（）; trie.insert（“蘋果”）; console.log（trie.search（“蘋果”））; // 真的 console.log（trie.search（“ app”））; // 錯誤的 console.log（trie.startswith（“ app”））; // 真的 trie.insert（“ app”）; console.log（trie.search（“ app”））; // 真的

高級Trie操作：

1。

刪除一個詞

---

：

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

---

2。

用前綴

計數單詞：

計數幾個單詞以給定前綴開頭。

[2 令node = this.root; 對於（讓前綴的字符）{ 如果（！node.children [char]）返回0; node = node.Children [char]; } 返回this._countwords（node）; } _countwords（node）{ 讓count = node.isendofword？ 1：0; （讓char in Node.Children）{ count = this._countwords（node.children [char]）; } 返回計數； }

3。

autocomplete建議

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

給定前綴，返回所有以其開頭的單詞。

）返回[]; node = node.Children [char]; } 返回this._collectwords（node，prefix）; } _collectwords（node，prefix）{ 讓結果= []; if（node.isendofword）results.push（prefix）; （讓char in Node.Children）{ 結果= results.concat（this._collectwords（node.children [char]，prefix char））; } 返回結果； }

時間複雜性：

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

[2 搜索

：o（l）

prefix search

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

---

delete

：o（l）

1. Trie的申請：
2. autocomplete systems
（例如，搜索欄，文本編輯器）。
3. 拼寫檢查器。
4. [2 Word Games
（例如，boggle）。

[2

---