a trie は、特にオートコンプリート、スペルチェック、IPルーティングなどのアプリケーションで、文字列を効率的に保存および検索するために使用されるツリーのようなデータ構造です。

---

Trieの重要なプロパティ：

1. nodes ：各ノードは文字を表します。
2. root ：ルートノードは空で、出発点として機能します。
3. 子供：各ノードには、文字セットに応じて、最大26人の子供（小文字の英語文字の場合）以上です。
4. 単語の終わりのマーカー：いくつかのノードは、単語の終わりを示すようにマークされています。

---

基本的なトリー操作：

1。挿入

単語を挿入するには、存在しない文字のトライを横断し、新しいノードを作成することが含まれます。

2。検索

検索は、ノードを横断することにより、トライに単語が存在するかどうかをチェックします。

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

---

高度なトリー操作：

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]; } this._countwords（node）; } _countwords（node）{ count = node.isendofwordとしますか？ 1：0; for count = this._countwords（node.children [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;
}

プレフィックスが与えられた場合、それから始まるすべての単語を返します。

getWordSwithPrefix（プレフィックス）{ let node = this.root; for（let char of prefix）{ if（！node.children [char]）return []; node = node.children [char]; } this._collectwords（node、prefix）を返します。 } _collectwords（node、prefix）{ 結果= []; if（node.isendofword）results.push（prefix）; for 結果= results.concat（this._collectwords（node.children [char]、prefix char））; } 結果を返します。 }

時間の複雑さ：

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

---

挿入

：o（l）（l = wordの長さ）

1. 検索：o（l）
2. プレフィックス検索：o（l）
3. delete ：o（l）
4. Trieのアプリケーション：

---

autocomplete Systems

（たとえば、検索バー、テキストエディター）。

。
1. スペルチェッカー。
2. IPルーティング（最長のプレフィックスマッチング）。
。
3. Word Games （例えば、boggle）。
4. DNAシーケンスマッチング。