寫在前
-
什么是字典樹铡溪？
- Trie樹，即字典樹衡蚂，又稱單詞查找樹或鍵樹窿克，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種毛甲。Trie 一詞來自 retrieval年叮，發(fā)音為 /tri:/ "tree"，也有人讀為 /tra?/ "try"玻募。
- 典型應用是用于統(tǒng)計和排序大量的字符串（但不僅限于字符串）只损，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：最大限度地減少無謂的字符串比較七咧。
Trie的核心思想是空間換時間跃惫，利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
-
基本性質(zhì)
根節(jié)點不包含字符艾栋，除根節(jié)點外每一個節(jié)點都只包含一個字符爆存。
從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來裹粤，為該節(jié)點對應的字符串终蒂。
每個節(jié)點的所有子節(jié)點包含的字符都不相同蜂林。
-
復雜度分析
1.插入和查詢的效率很高遥诉，時間復雜度都為O(m)拇泣，其中 m 是待插入/查詢的字符串的長度。
注：關(guān)于查詢矮锈，會有人說 hash 表時間復雜度是O(1)不是更快霉翔？但是，哈希搜索的效率通常取決于 hash 函數(shù)的好壞苞笨，若一個壞的 hash 函數(shù)導致很多的沖突债朵，效率并不一定比Trie樹高。
2.最壞的空間復雜度實現(xiàn)方式可以到S^L瀑凝，其中S為字符集L為最長長度
-
Trie樹的應用
- 字符串檢索：事先將已知的一些字符串（字典）的有關(guān)信息保存到 Trie 里序芦，查找另外一些未知字符串是否出現(xiàn)過或者出現(xiàn)頻率。
- 字符串最長公共前綴：Trie 利用多個字符串的公共前綴來節(jié)省存儲空間粤咪，反之谚中，當我們把大量字符串存儲到一棵 Trie 上時，我們可以快速得到某些字符串的公共前綴寥枝。
- 排序：Trie 樹是一棵多叉樹宪塔，只要先序遍歷整棵樹，輸出相應的字符串囊拜，便是按字典序排序的結(jié)果某筐。
- 作為其他數(shù)據(jù)結(jié)構(gòu)和算法的輔助結(jié)構(gòu)：如后綴樹，AC自動機等冠跷。
基本實現(xiàn)
前綴樹創(chuàng)建
假設(shè)有b南誊，abc，abd蜜托，bcd弟疆，abcd，efg盗冷，hii 這6個單詞,那我們創(chuàng)建trie樹就得到怠苔。
可以看出，Trie樹的關(guān)鍵字一般都是字符串仪糖，而且Trie樹把每個關(guān)鍵字保存在一條路徑上柑司，而不是一個結(jié)點中。另外锅劝，兩個有公共前綴的關(guān)鍵字攒驰，在Trie樹中前綴部分的路徑相同。
前綴樹的主要操作就是插入和查詢故爵，即將一個字符串加入集合中和查詢集合中有沒有這個字符串玻粪。每個字符加兩個變量，path 定義節(jié)點經(jīng)過的次數(shù)，end 定義最后一個插入的節(jié)點
public class TrieNode {
private int path;
private int end;
private TrieNode[] nexts;
public TrieNode() {
path = 0;
end = 0;
nexts = new TrieNode[26];
}
}
前綴樹插入
private TrieNode root; // 根節(jié)點
public TrieNode {
root = new TrieNode();
}
/**
往前綴樹中插入字符串(這里只包含26個小寫字母)
*/
private void insert(String word) {
if (word == null) {
return;
}
int n = word.length();
char[] chs = word.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < n; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode(); // 創(chuàng)建當前字符
}
node = node.nexts[index];
node.path++;
}
node.end++;
}
前綴樹查詢
/**
1劲室、查詢前綴樹某字符串出現(xiàn)的次數(shù)伦仍，返回結(jié)尾字符出現(xiàn)的次數(shù)，即node.end
2很洋、查詢以某字符串為前綴的數(shù)量充蓝，返回每個字符被劃過的次數(shù)，即node.path
如果不存在返回-1喉磁，類似插入操作谓苟！
*/
private int searchCount(String str) {
if (str == null) {
return -1;
}
int n = str.length();
char[] chs = str.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < n; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return -1;
}
node = node.nexts[index];
}
return node.end; // 返回以當前關(guān)鍵字結(jié)尾的字符串的個數(shù)
//return node.path; //插字符串時到達幾次
}
/**
3、查詢集合中是否存在某個字符串协怒，同理
*/
private boolean search(String str) {
if (str == null) {
return false;
}
int n = str.length();
char[] chs = str.toCharArray();
TrieNode node = root;
int index = 0;
for (int i = 0; i < n; i++) {
index = chs[i] - 'a';
if (node.nexts[index] == null) {
return false;
}
node = node.nexts[index];
}
return true;
}
案例分析
T208 前綴樹
代碼實現(xiàn)：
class Trie {
class TrieNode {
boolean isEnd;
TrieNode[] nexts = new TrieNode[26];
}
TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
if (word == null) {
return;
}
TrieNode node = root;
int index = 0;
for (int i = 0; i < word.length(); i++) {
index = word.charAt(i) - 'a';
if (node.nexts[index] == null) {
node.nexts[index] = new TrieNode();
}
node = node.nexts[index];
}
node.isEnd = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
if (word == null) {
return false;
}
TrieNode node = root;
int index = 0;
for (int i = 0; i < word.length(); i++) {
index = word.charAt(i) - 'a';
if (node.nexts[index] == null) {
return false;
}
// 指針移動
node = node.nexts[index];
}
return node.isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
if (prefix == null) {
return false;
}
TrieNode node = root;
int index = 0;
for (int i = 0; i < prefix.length(); i++) {
index = prefix.charAt(i) - 'a';
if (node.nexts[index] == null) {
return false;
}
node = node.nexts[index];
}
return true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
T421 數(shù)組最大異或值
待補充涝焙。。孕暇。
