介紹
trie，也稱(chēng)為前綴樹(shù)，是一種專(zhuān)門(mén)的基于樹(shù)的數(shù)據(jù)結(jié)構(gòu)，用于高效的信息檢索。
它對(duì)于涉及字符串內(nèi)搜索和前綴匹配的用例特別有用。
如果我告訴你 trie 算法，你可能會(huì)對(duì)這個(gè)算法感興趣，也可能不感興趣
但是如果我告訴你你可以使用它創(chuàng)建一個(gè)自動(dòng)完成算法。你會(huì)更興奮地學(xué)習(xí)這個(gè)。
該算法的用例
1.自動(dòng)完成：
a。搜索引擎或文本編輯器中經(jīng)常使用嘗試來(lái)實(shí)現(xiàn)自動(dòng)完成功能。
b.當(dāng)您開(kāi)始輸入時(shí)，應(yīng)用程序會(huì)根據(jù)您輸入的前綴建議可能的補(bǔ)全。
2.拼寫(xiě)檢查器：
a。嘗試可用于實(shí)現(xiàn)拼寫(xiě)檢查器。如果某個(gè)單詞不存在于 trie 中，則它可能是拼寫(xiě)錯(cuò)誤的。
b.特里樹(shù)還可以通過(guò)查找相似的單詞來(lái)建議更正。
3. ip路由：
a。嘗試在路由器中用于存儲(chǔ)路由表。
b.路由器使用 trie 來(lái)匹配最長(zhǎng)前綴，這決定了數(shù)據(jù)包的下一跳。
4.高效存儲(chǔ)和搜索字符串：
a。如果您有一個(gè)包含大量共享前綴的字符串?dāng)?shù)據(jù)集，則 trie 可以使用比單獨(dú)存儲(chǔ)它們更少的空間來(lái)存儲(chǔ)這些字符串。
b. 搜索操作也很高效，時(shí)間復(fù)雜度與您要搜索的字符串的長(zhǎng)度成正比。
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
*/
登錄后復(fù)制
如果您有任何疑慮/疑問(wèn)，請(qǐng)隨時(shí)與我聯(lián)系。
