1脾还、 概述
Trie樹忙厌，又稱字典樹纲酗，單詞查找樹或者前綴樹浴麻，是一種用于快速檢索的多叉樹結構椅野，如英文字母的字典樹是一個26叉樹盛垦，數(shù)字的字典樹是一個10叉樹绘面。
Trie一詞來自retrieve涣楷，發(fā)音為/tri:/ “tree”袁稽，也有人讀為/tra?/ “try”勿璃。
Trie樹可以利用字符串的公共前綴來節(jié)約存儲空間。如下圖所示，該trie樹用10個節(jié)點保存了6個字符串tea补疑，ten歧沪，to，in莲组，inn诊胞，int：
在該trie樹中，字符串in胁编，inn和int的公共前綴是“in”厢钧，因此可以只存儲一份“in”以節(jié)省空間。當然嬉橙，如果系統(tǒng)中存在大量字符串且這些字符串基本沒有公共前綴早直，則相應的trie樹將非常消耗內(nèi)存，這也是trie樹的一個缺點市框。
Trie樹的基本性質(zhì)可以歸納為：
（1）根節(jié)點不包含字符霞扬，除根節(jié)點意外每個節(jié)點只包含一個字符。
（2）從根節(jié)點到某一個節(jié)點枫振，路徑上經(jīng)過的字符連接起來喻圃，為該節(jié)點對應的字符串。
（3）每個節(jié)點的所有子節(jié)點包含的字符串不相同粪滤。
2斧拍、 Trie樹的基本實現(xiàn)
字母樹的插入（Insert）、刪除（ Delete）和查找（Find）都非常簡單杖小，用一個一重循環(huán)即可肆汹，即第i 次循環(huán)找到前i 個字母所對應的子樹，然后進行相應的操作予权。實現(xiàn)這棵字母樹昂勉，我們用最常見的數(shù)組保存（靜態(tài)開辟內(nèi)存）即可，當然也可以開動態(tài)的指針類型（動態(tài)開辟內(nèi)存）扫腺。至于結點對兒子的指向岗照，一般有三種方法：
1、對每個結點開一個字母集大小的數(shù)組笆环，對應的下標是兒子所表示的字母攒至，內(nèi)容則是這個兒子對應在大數(shù)組上的位置，即標號躁劣；
2嗓袱、對每個結點掛一個鏈表，按一定順序記錄每個兒子是誰习绢；
3、使用左兒子右兄弟表示法記錄這棵樹。
三種方法闪萄，各有特點梧却。第一種易實現(xiàn)，但實際的空間要求較大败去；第二種放航，較易實現(xiàn)，空間要求相對較小圆裕，但比較費時广鳍；第三種，空間要求最小吓妆，但相對費時且不易寫赊时。
下面給出動態(tài)開辟內(nèi)存的實現(xiàn)：
#define MAX_NUM 26
enumNODE_TYPE{//"COMPLETED" means a string is generated so far.
COMPLETED,
UNCOMPLETED
};
structNode {
enumNODE_TYPE type;
charch;
structNode* child[MAX_NUM];//26-tree->a, b ,c, .....z
};
structNode* ROOT;//tree root
structNode* createNewNode(charch){
// create a new node
structNode *new_node = (structNode*)malloc(sizeof(structNode));
new_node->ch = ch;
new_node->type == UNCOMPLETED;
inti;
for(i = 0; i < MAX_NUM; i++)
new_node->child[i] = NULL;
returnnew_node;
}
voidinitialization() {
//intiazation: creat an empty tree, with only a ROOT
ROOT = createNewNode(' ');
}
intcharToindex(charch) {//a "char" maps to an index
returnch -'a';
}
intfind(constcharchars[],intlen) {
structNode* ptr = ROOT;
inti = 0;
while(i < len) {
if(ptr->child[charToindex(chars[i])] == NULL) {
break;
}
ptr = ptr->child[charToindex(chars[i])];
i++;
}
return(i == len) && (ptr->type == COMPLETED);
}
voidinsert(constcharchars[],intlen) {
structNode* ptr = ROOT;
inti;
for(i = 0; i < len; i++) {
if(ptr->child[charToindex(chars[i])] == NULL) {
ptr->child[charToindex(chars[i])] = createNewNode(chars[i]);
}
ptr = ptr->child[charToindex(chars[i])];
}
ptr->type = COMPLETED;
}
3、 Trie樹的高級實現(xiàn)
可以采用雙數(shù)組（Double-Array）實現(xiàn)行拢。利用雙數(shù)組可以大大減小內(nèi)存使用量祖秒，具體實現(xiàn)細節(jié)見參考資料（5）（6）。
4舟奠、 Trie樹的應用
Trie是一種非常簡單高效的數(shù)據(jù)結構竭缝，但有大量的應用實例。
（1） 字符串檢索
事先將已知的一些字符串（字典）的有關信息保存到trie樹里沼瘫，查找另外一些未知字符串是否出現(xiàn)過或者出現(xiàn)頻率抬纸。
舉例：
@? 給出N 個單詞組成的熟詞表，以及一篇全用小寫英文書寫的文章耿戚，請你按最早出現(xiàn)的順序?qū)懗鏊胁辉谑煸~表中的生詞湿故。
@? 給出一個詞典，其中的單詞為不良單詞溅话。單詞均為小寫字母晓锻。再給出一段文本，文本的每一行也由小寫字母構成飞几。判斷文本中是否含有任何不良單詞砚哆。例如，若rob是不良單詞屑墨，那么文本problem含有不良單詞躁锁。
（2）字符串最長公共前綴
Trie樹利用多個字符串的公共前綴來節(jié)省存儲空間，反之卵史，當我們把大量字符串存儲到一棵trie樹上時战转，我們可以快速得到某些字符串的公共前綴。
舉例：
@ 給出N 個小寫英文字母串以躯，以及Q 個詢問槐秧，即詢問某兩個串的最長公共前綴的長度是多少啄踊？
解決方案：首先對所有的串建立其對應的字母樹。此時發(fā)現(xiàn)刁标，對于兩個串的最長公共前綴的長度即它們所在結點的公共祖先個數(shù)颠通，于是，問題就轉(zhuǎn)化為了離線（Offline）的最近公共祖先（Least Common Ancestor膀懈，簡稱LCA）問題顿锰。
而最近公共祖先問題同樣是一個經(jīng)典問題，可以用下面幾種方法：
1. 利用并查集（Disjoint Set）启搂，可以采用采用經(jīng)典的Tarjan 算法硼控；
2. 求出字母樹的歐拉序列（Euler Sequence ）后，就可以轉(zhuǎn)為經(jīng)典的最小值查詢（Range Minimum Query胳赌，簡稱RMQ）問題了牢撼；
（關于并查集，Tarjan算法匈织，RMQ問題浪默，網(wǎng)上有很多資料。）
（3）排序
Trie樹是一棵多叉樹缀匕，只要先序遍歷整棵樹纳决，輸出相應的字符串便是按字典序排序的結果。
舉例：
@ 給你N 個互不相同的僅由一個單詞構成的英文名乡小，讓你將它們按字典序從小到大排序輸出阔加。
（4） 作為其他數(shù)據(jù)結構和算法的輔助結構
如后綴樹，AC自動機等
5满钟、 Trie樹復雜度分析
（1） 插入胜榔、查找的時間復雜度均為O(N)，其中N為字符串長度湃番。
（2） 空間復雜度是26^n級別的夭织，非常龐大（可采用雙數(shù)組實現(xiàn)改善）。
6吠撮、 總結
Trie樹是一種非常重要的數(shù)據(jù)結構尊惰，它在信息檢索，字符串匹配等領域有廣泛的應用泥兰，同時弄屡，它也是很多算法和復雜數(shù)據(jù)結構的基礎，如后綴樹鞋诗，AC自動機等膀捷，因此，掌握Trie樹這種數(shù)據(jù)結構削彬，對于一名IT人員全庸，顯得非承阒伲基礎且必要！
