介紹
trie，也稱為前綴樹，是一種專門的基于樹的數據結構，用于高效的信息檢索。
它對于涉及字符串內搜索和前綴匹配的用例特別有用。
如果我告訴你 trie 算法，你可能會對這個算法感興趣，也可能不感興趣
但是如果我告訴你你可以使用它創建一個自動完成算法。你會更興奮地學習這個。
該算法的用例
1.自動完成：
a。搜索引擎或文本編輯器中經常使用嘗試來實現自動完成功能。
b.當您開始輸入時，應用程序會根據您輸入的前綴建議可能的補全。
2.拼寫檢查器：
a。嘗試可用于實現拼寫檢查器。如果某個單詞不存在于 trie 中，則它可能是拼寫錯誤的。
b.特里樹還可以通過查找相似的單詞來建議更正。
3. ip路由：
a。嘗試在路由器中用于存儲路由表。
b.路由器使用 trie 來匹配最長前綴，這決定了數據包的下一跳。
4.高效存儲和搜索字符串：
a。如果您有一個包含大量共享前綴的字符串數據集，則 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
*/
登錄后復制
如果您有任何疑慮/疑問，請隨時與我聯系。
