Trie字典樹
Trie字典樹又稱前綴樹，顧名思義，是查詢前綴匹配的一種樹形數據結構
可以分為插入(創建) 和 查詢兩部分。參考地址極客時間
下圖為插入字符串的過程：
創建完成后，每個字符串最後一個字母標記為終結點（圖中显示為紅色）
下圖為查詢字符串：“her”的過程：綠色箭頭表示查詢路徑
我們將要查找的字符串分割成單個的字符 h，e，r，一個一個查詢
下圖為查詢字符串：“he”的過程：綠色箭頭表示查詢路徑
因為‘e’不是終結點，所以不能完全匹配上。
Trie字典樹的實現
1.首先是字典樹 數據結構定義的代碼實現
樹形結構，類比於二叉樹的存儲嘛，每個結點兩條分支(二叉樹)；
而字典樹，每個節點可以最多有 26個分支(存儲英文字母)。
1-1二維數組存儲字母
int trie[MAX_NODE][26];//MAX_NODE表示結點數量，每個結點有26個字母結點
int k;
MAX_NODE表示結點數量，每個結點有26個字母結點
Trie[i][j]的值是0，表示trie樹中i號節點，並沒有一條連出去的邊滿足邊上的字符標識是字符集中第j個字符（從0開始）；
trie[i][j]的值是正整數x表示trie樹中i號節點，有一條連出去的邊滿足邊上的字符標識是字符集中第j個字符，並且
這條邊的終點是x號節點。
1-2鏈表
我這裏用C++中的vector實現，
vector< pair<char, int> > trie[MAX_NODE];
int k;
也可以寫一個真正的鏈表，包含二元組字段<char,int>型的對應關係
1-3hash，
map<char, int> trie[MAX_NODE];
每次我們想找i號節點有沒有標識
是某個字符ch的邊時，只要看trie[i][ch]的值即可
但是實際上map時空複雜度的常數都比較大
2.插入 和 查詢 兩個函數的代碼實現
插入 查詢 實際上是類似的，就是從樹的根開始往下遍歷，
2-1插入：從樹的根開始往下遍歷，到達一個結點，沒有這個字母就插入到這個結點下，作為這個結點的子節點
基於二維數組結構的插入功能實現
代碼的第6~8行，一開始trie[][]被初始化為0，保證每個節點被創建出來時，都沒有子節點。K初
始化為1表示一開始只有1個節點，也就是0號節點根節點。Color是用來標記一個節點是不是終結
點。Color[i]=1標識i號節點是終結點。
第9~21行是插入函數insert(w)，w是字符指針，實際上可以看作是一個字符串。
第11行是p從0號節點開始。
第12~19行是依次插入w的每一個字符。
第13行是計算w[i]是字符集第幾個字符，這裏我們假設字符集只包含26個小寫字母。
第14~17行是如果p沒有連出標識是w[i]的邊，那麼就創建一個。這裏新創建的節點一定就是k號節
點。所謂創建新節點實際上也沒什麼可創建的，新節點就是個編號。所以我們直接令trie[i][c]=k
即可，然後將k累加1，整個創建過程就完成了。
第18行是沿着標記着w[i]的邊移動到下一個節點。
最後第20行，是將最後到達的節點p標記為終結點。
2-2查詢：從樹的根開始往下遍歷，查看是否匹配上當前正在查的單詞
基於二維數組結構的查詢功能實現
第24行是從p=0也就是根節點開始。
第25~29行是枚舉s的每一個字符。
第26行是計算當前字符s[i]在字符集的序號。
第27行是判斷p節點有沒有連出標識s[i]字符的邊，如果沒有，說明現在無路可走，直接返回0；如
果有的話，
第28行就是移動到下一個節點。如果整個循環結束還沒有return 0，那就說明成功沿着s的每一個
字符到達了p節點。這時只要判斷p節點是不是終結點即可，也就是第30行的代
3.完整代碼C++版
public class Trie {
private TrieNode root = new TrieNode('/'); // 存儲無意義字符
// 往 Trie 樹中插入一個字符串
public void insert(char[] text) {
TrieNode p = root;
for (int i = 0; i < text.length; ++i) {
int index = text[i] - 'a';
if (p.children[index] == null) {
TrieNode newNode = new TrieNode(text[i]);
p.children[index] = newNode;
}
p = p.children[index];
}
p.isEndingChar = true;
}
// 在 Trie 樹中查找一個字符串
public boolean find(char[] pattern) {
TrieNode p = root;
for (int i = 0; i < pattern.length; ++i) {
int index = pattern[i] - 'a';
if (p.children[index] == null) {
return false; // 不存在 pattern
}
p = p.children[index];
}
if (p.isEndingChar == false) return false; // 不能完全匹配，只是前綴
else return true; // 找到 pattern
}
public class TrieNode {
public char data;
public TrieNode[] children = new TrieNode[26];
public boolean isEndingChar = false;
public TrieNode(char data) {
this.data = data;
}
}
}
Trie字典樹的時間複雜度 與 缺點
插入的時間複雜度：O(N)，N為所有待插入字符串的長度之和
查詢的時間複雜度：O(K)，K為待查詢字符串的長度
占內存：如果用二維數組實現，每個節點就會額外需要 26*8=208 個字節
優化思路：將每個節點中的數組換成其他數據結構，比如有序數組(可以二分查找)、跳錶、散列表、紅黑樹等。
Trie變體，縮點優化：對只有一個子節點的節點，而且此節點不是一個串的結束節點，可以將此節點與子節點合併
Trie字典樹的實際應用
1.搜索引擎輸入框關鍵詞提示
因為字典樹是查找 “與前綴匹配的字符串”，又稱為前綴樹。
關鍵詞提示就是 查尋找前綴匹配的前綴合適關鍵詞，當然還有更複雜的關鍵詞排名問題，這裏不再展開。
2.自動補全功能，如：IDE編譯器自動補全，輸入法自動補全等
原理與搜索引擎類似。
3.敏感詞過濾系統
4.其它
Trie在面試與算法競賽中的例題
1.hihoCoder1014
hihoCoder1014
解題思路：Trie字典樹
首先我們把集合中的N個字符串都插入到trie中。
對於每一個查詢s我們在trie中查找s，如果查找過程中無路可走，那麼一定沒有以s為前綴的字符串。
如果最後停在一個節點p，那我們就要看看以p為根的子樹里一共有多少終結點。
終結點的數目就是答案。
但是如果我們每次都遍歷以P為根的子樹，那時間複雜度就太高了。解決的辦法是用空間換時間，我們增加一個數組intcnt[MAX_NODE]
cnt[i]記錄的是以i號節點為根的子樹中，有幾個終結點。
然後我們每次insert一個字符串的時候，順便就把沿途的節點的cnt值都+1。
這樣就不用每次遍歷以P為根的子樹，而是直接輸出cnt[P]即可。
代碼：
2.hihoCoder1107微軟面試題
hihoCoder1014
其實就是找一個節點p，滿足以p為根的子樹中的終結點不多於5個，同時以p的父節點為根的子樹中的終結點大於5個。
和上題一樣用cnt數組標記，之後dfs查找終結點的數目
3.Trie應用在整數xor異或值最大的題目
給定一個包含N個整數的集合S={A1, A2, A3, … AN}。然
後有M個詢問，每次詢問給定一個整數X，讓你找一個Ai使得Ai xor X的值最大。
首先我們知道一個整數可以用二進製表示成一個01串。比如3=(011)2, 5=(101)2, 4=(100)2……。
我們假設輸入的整數都在0~2^32-1之間，於是我們可以用一個長度是32位的01串表示一個整數。
然後對於給定的N個整數A1, A2, A3, … AN，我們把它們對應的01串都插入到一個trie中。注意這裏字符集只有0和1，所以整個trie是一棵二叉樹。
下面我們舉一個例子，為了描述方便，我們假設整數都在0~7之間，也就是可以用3位01串表示。
現在假設S={1, 2, 7}，也就是說我們要在Trie中插入{001, 010, 111}：
這時假設我們要查詢x=4，也就是哪個數和4異或結果最大？4=(100)2，
我們的做法是在trie樹中，盡量與4的二進制位反着走。
比如4的第一位（最高位）是1，我們從0出發第一步就盡量沿着0走。因為我們要異或和最大，01相反才能異或值是1。
並且這一步是可以貪心的，也就是說如果有相反的邊，那麼我們一定沿着這條邊走。因為最高位異或得1的話，即便後面都是0, 10000…000也要比最高位是0，後面都是1的011111…111大。
所以我們第一步沿着標識是0的邊，移動到了1號節點；4第二位是0，所以我們沿着標識是1的邊移動到4號節點；
4的第三位是0，但是4號節點沒有標識是1的邊，所以我們也只好沿着標識是0的邊移動到5號節點。
已經到了終結點，所以5號節點對應的A2=(010)2=2就是我們要求的答案，A2 xor 4 = 6是最大的。
【精選推薦文章】
自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象
網頁設計一頭霧水??該從何著手呢? 找到專業技術的網頁設計公司，幫您輕鬆架站!
評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享
台北網頁設計公司這麼多，該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"
