介紹

Trie，也稱為前綴樹，是一種專門的基於樹的資料結構，用於高效的資訊檢索。

它對於涉及字串內搜尋和前綴匹配的用例特別有用。

1. 如果我告訴你有關 Trie 演算法的信息，你可能對此演算法感興趣，也可能不感興趣

2. 但如果我告訴你，你可以用它來建立一個來自動完成演算法。你會更興奮地了解這一點。

此演算法的用例

1。自動完成：

一個。搜尋引擎或文字編輯器中經常使用嘗試來實現自動完成功能。
b.當您開始輸入時，應用程式會根據您輸入的前綴建議可能的補全。

2.拼字檢查器：

一個。嘗試可用於實現拼字檢查器。如果某個單字不存在於 trie 中，則它可能是拼字錯誤的。
b.特里樹也可以透過尋找相似的單字來建議更正。

3. IP路由：

一個。嘗試在路由器中用於儲存路由表。
b.路由器使用 trie 來匹配最長前綴，從而確定資料包的下一跳。

4。高效儲存和搜尋字串：

一個。如果您有一個包含大量共享前綴的字串資料集，則 trie 可以使用比單獨儲存它們更少的空間來儲存這些字串。
b. 搜尋操作也很高效，時間複雜度與您要搜尋的字串的長度成正比。

class Node {
    constructor() {
        this.end = false;
        this.children = {}
    }
}

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

    insert(word) {
        let head = this.root;

        for (let i = 0; i ', current.children);

        console.log('Possible Auto Complete Values are --->');
        for (let key in current.children) {
            console.log('---> ', word key);
        }
    }
}

const test = new Trie();
test.insert('ant');
test.insert('any');
console.log(test.search('ant'));
console.log(test.search('any'));
console.log(test.search('anj'));
test.autoComplete('an')
/*
true
true
false
children =--->  {
  t: Node { end: true, children: {} },
  y: Node { end: true, children: {} }
}
Possible Auto Complete Values are --->
--->  ant
--->  any
*/

如果您有任何疑慮/疑問，請隨時與我聯繫。