- 定義
??又稱單詞查找樹，Trie樹帅矗，是一種樹形結(jié)構(gòu)偎肃，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)浑此，排序和保存大量的字符串（但不僅限于字符串）累颂，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)減少查詢時(shí)間凛俱，最大限度地減少無(wú)謂的字符串比較喘落，查詢效率比哈希樹高。
字典樹
??Trie樹查找每個(gè)條目的復(fù)雜度和字典中條目的個(gè)數(shù)無(wú)關(guān)最冰，而是和查找的條目的長(zhǎng)度有關(guān)瘦棋。常用的場(chǎng)景有通訊錄、最長(zhǎng)公共前綴等等暖哨。
??由上圖可知對(duì)于 Trie的定義可以使用一個(gè)數(shù)據(jù)域和一個(gè)字符數(shù)組完成赌朋，一般情況下數(shù)組的長(zhǎng)度設(shè)置為26即可，但是不同的語(yǔ)言和不同的場(chǎng)景篇裁，可能為導(dǎo)致數(shù)組的程度難以確定沛慢，比如是否考慮大小寫、是否包含其他字符等达布，而且使用數(shù)組的方式可能會(huì)包含多個(gè)空閑位置团甲，導(dǎo)致內(nèi)存資源的浪費(fèi)，所以我們使用以下方式定義動(dòng)態(tài)的 Trie黍聂。
class Node{
//某些條目比如對(duì)于abc躺苦， abcd身腻，在字典樹中如果是通過葉子節(jié)點(diǎn)來(lái)來(lái)判定是否到達(dá)條目的結(jié)尾，那就不存在abc了匹厘。
//可以給每個(gè)節(jié)點(diǎn)多增加一個(gè)標(biāo)識(shí)嘀趟，用來(lái)標(biāo)識(shí)當(dāng)前節(jié)點(diǎn)是否是一個(gè)條目的結(jié)尾。
boolean isWord;
//數(shù)據(jù) e 和對(duì)應(yīng)的子節(jié)點(diǎn)
Map<E, Node> next;
}
- 基本使用
??（1）構(gòu)建字典樹
//向字典樹中添加一個(gè)元素
public void add(String word){
Node cur = root;
// 遍歷 word愈诚，將每個(gè)字符添加到對(duì)應(yīng)的節(jié)點(diǎn)中
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
// 如果字符對(duì)應(yīng)的節(jié)點(diǎn)不存在她按，則添加節(jié)點(diǎn)
cur.next.putIfAbsent(c, new Node());
// 獲取 該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，重復(fù)操作
cur = cur.next.get(c);
}
// 如果word存在炕柔，則不更新酌泰，如果不存在，則標(biāo)識(shí)當(dāng)前的節(jié)點(diǎn)為字符串的尾部匕累。
if(!cur.isWord && size ++ >= 0) cur.isWord = true;
}
??（2）查詢字符
//從 trie 中查找元素
public boolean search(String word){
Node cur = root;
// 遍歷字符串宫莱，去字典樹中尋找是否有對(duì)應(yīng)的路徑可以表示
for (int i = 0; i < word.length(); i++) {
Node node = cur.next.get(word.charAt(i));
if(node == null) return false;
cur = node;
}
return cur.isWord;
}
- 擴(kuò)展
??Tire的刪除操作、壓縮字典樹哩罪、 Tnernay Search Trie授霸、后綴樹。
