前面的文章介紹過各種高效的的數據結構，比如二叉搜索樹，AVL樹，紅黑樹，B樹，跳躍表等，今天我們再來學習一種多路樹，叫做Trie樹。
什麼是Trie樹在計算機科學中，Trie，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組。其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。Trie樹的名稱來源於搜尋引擎中的專有名詞的retrieval，發音和單詞try一樣。
比如下面的這個Trie樹包含「Cat」，「Cut」，「Cute」，「To」，「B」五個單詞，其存儲圖示如下：
從上面我們可以發現，前綴一樣的單詞，在實際存儲中只存儲了一份，並且如果單詞後面有.符號表從root到這個位置是一個單詞，前綴相同的單詞會復用一樣的公共節點。
Trie樹的應用場景Trie最典型的應用場景是用於搜尋引擎的suggest功能，比如我們在google中，每輸入一個英文字母，搜尋引擎都會給過我們返回以這個字母為前綴的相關的結果，如下：
除以之外，還有常見的IDE裡面自動補全功能和各種通訊錄的自動補全功能等。
Trie樹的工作原理這裡以英文單詞為例，我們知道英語單詞由26個字母組成，每一個字母都是這26個字母中的其中一個，假如現在我們想為英語單詞的suggest功能，那麼使用Trie樹就非常適合。因為總共的可能性只有26，所以我們可以定義一個長度為26的數組來存儲所有的可能性，然後附帶一個boolean類型的變量，來標記當前層是否是一個單詞。
如下定義：
static class TrieNode{
TrieNode[] children;
boolean isWord;
public TrieNode(){
children=new TrieNode[26];
}
}
如何插入Trie樹的結構，通常需要一個虛擬的head節點來輔助，head節點並不存儲數據，僅僅用於操作方便，在插入的時候，會分解單詞為一個字符數組，然後依次插入其中的每一個字母到Trie樹裡面，如果插入的位置不存在該字母，那麼代表第一次插入，就需要新建一個TrieNode節點， 如果插入的地方已經存在，那麼就直接繼續插入下一個字母，直到整個單詞的每一個字母都插入完畢後，在最後一個TrieNode節點處標記到目前這個節點處，代表一個完整的單詞。
如何查詢查詢主要有兩種形式，第一種是判斷是否存在某個單詞在Trie樹裡面，第二種是判斷指定的前綴是否在Trie樹裡面存在。
這兩種case的檢索方式大致一樣，就是從head節點入手，判斷這個單詞的第一個字母是否存在，如果就跳到第二級繼續搜索，知道遍歷完整個字母，返回最後一個節點，然後判斷如果該節點有數據，並且有完整單詞標記，那麼就證明該單詞存在，如果沒有單詞標記，那麼證明該前綴存在。如果判斷返回的節點沒有數據，那麼就證明當前的Trie樹裡面不包含某個單詞或者輸入的指定的前綴。
如何刪除Trie樹的相對來說稍微複雜點，舉個例子，比如包含6個單詞的Trie樹：
("abc")
("xy")
("xyz")
("abb")
("xyzb"),
("word")
圖示如下：
我們看刪除的幾種情況：
（1）如果要刪除的單詞不存在，則不做任何操作
（2）如果要刪除的單詞是沒有任何字母被作為公共前綴，那麼就要刪除每個字母，如上圖的單詞word
（3）如果要刪除的單詞全部字母都是公共前綴，那麼僅僅在這個單詞的尾部標記不是完整單詞即可，如上圖的單詞xyz
（4）如果要刪除的單詞是超出了公共前綴，那麼僅僅刪除多出的部分即可，如上圖的xyzb，在刪除的時候僅僅刪除字母b即可。
（5）如果要刪除的單詞是兩條路徑的公共前綴，那麼僅僅刪除非公共前綴的部分即可，這種情況與（4）類似，但不同的是（4）是在一條路徑上，而（5）是在兩條路徑上，如上圖要刪除abc，因為前綴ab是共用的，所以僅僅刪除abc的c字母即可。
上面就是刪除的全部情況，不過在Trie樹裡面，重要的部分是插入和檢索部分，刪除部分可能比較少的使用。
Trie樹的實現方式Trie樹有兩種實現策略，第一種使用數組存儲所有的可能性，第二種是使用的Map存儲所有的可能性，使用數組的方式需要對存儲的字符和數組的index之間要有明確的映射規則，這樣便於查詢，比如如果想做中文的suggest，一種的可行的辦法就是將整個中文字符集映射到具體的數值上，然後與上面字母的操作類似，如果選擇使用Map作為可能性存儲，相對來說會更加靈活一點，畢竟Map在大多數程式語言裡面都有封裝好的動態實現。
下面給出的是基於數組實現Trie樹的方式，基於Map的實現方式可以參考我的github的代碼：
https://github.com/qindongliang/Java-Note
public class TrieByArray {
static class TrieNode{
TrieNode[] children;//存儲所有的可能性
boolean isWord;//是否是一個完整單詞
public TrieNode(){
children=new TrieNode[26];
}
}
TrieNode root;
public TrieByArray(){
root=new TrieNode();
}
public void insert(String word){
TrieNode prev=root;
for (int i = 0; i < word.length(); i++) {
if(prev.children[word.charAt(i)-'a']==null){
prev.children[word.charAt(i)-'a']=new TrieNode();
}
prev=prev.children[word.charAt(i)-'a'];
}
prev.isWord =true;
}
public boolean search(String word){
TrieNode result=checkExists(word);
if(result!=null&&result.isWord){
return true;
}
return false;
}
public TrieNode checkExists(String query){
TrieNode cur=root;
for (int i = 0; i < query.length(); i++) {
//待查詢的字符不存在
if(cur.children[query.charAt(i)-'a']==null){
return cur.children[query.charAt(i)-'a'];
}else{
cur=cur.children[query.charAt(i)-'a'];;
}
}
return cur;
}
public void delete(String key){
if(root==null||key==null){
return;
}
deleteWord(root,key,key.length(),0);
}
private boolean hasChildren(TrieNode currentNode){
for (int i = 0; i < currentNode.children.length; i++) {
if(currentNode.children[i]!=null){
return true;
}
}
return false;
}
public boolean deleteWord(TrieNode currentNode,String word,int length,int level){
boolean deletedSelf=false;
if(level==length){
//如果當前節點是最後，並且沒有孩子節點
if(!hasChildren(currentNode)){
currentNode=null;
deletedSelf=true;
}else{//有孩子節點
currentNode.isWord =false;//則將其置為非單詞屬性即可
deletedSelf=false;
}
}else {
//由下而上遞歸刪除
TrieNode childNode=currentNode.children[word.charAt(level)-'a'];
boolean childDeleted=deleteWord(childNode,word,length,level+1);
if(childDeleted){//如果單詞的最後的字符沒有孩子節點，就可以被刪除，然後需要繼續向上遞歸判斷其前一個字符是否是需要刪除
currentNode.children[word.charAt(level)-'a']=null;//設置子節點為null
if(currentNode.isWord){//判斷父節點是否是一個word的結束，如果是說明是公共前綴就不能再刪除了
deletedSelf=false;
}else if(hasChildren(currentNode)){//如果這個父節點還有孩子節點，說明也是公共前綴，也不能再刪除了
deletedSelf=false;
}else{//到這一步，說明父節點也是要刪除單詞唯一的的字符，可以繼續向上刪除
currentNode=null;
deletedSelf=true;
}
}else {//如果不需要被刪除，則向上傳遞false即可
deletedSelf=false;
}
}
return deletedSelf;
}
public boolean startsWith(String prefix){
TrieNode result=checkExists(prefix);
if(result!=null){
return true;
}
return false;
}
public static void main(String[] args) {
TrieByArray trie=new TrieByArray();
trie.example1();
// trie.example2();
// trie.example3();
}
private void example1(){
TrieByArray trie = new TrieByArray();
trie.insert("apple");
System.out.println(trie.search("apple")); // returns true
System.out.println(trie.search("app")); // returns false
System.out.println(trie.startsWith("app")); // returns true
trie.insert("app");
System.out.println(trie.search("app")); // returns true
}
private void example2(){
TrieByArray trie = new TrieByArray();
trie.insert("gat");
trie.insert("gag");
System.out.println(trie.search("gat"));//true
System.out.println(trie.startsWith("ga"));//true
trie.delete("gat");
System.out.println(trie.search("gat"));//false
System.out.println(trie.startsWith("ga"));//true
System.out.println(trie.search("gag"));//true
}
private void example3(){
TrieByArray trie = new TrieByArray();
trie.insert("abcd");
trie.insert("abc");
System.out.println(trie.search("abc"));
System.out.println(trie.startsWith("abc"));
trie.delete("abc");
System.out.println(trie.search("abc"));
System.out.println(trie.search("abcd"));
System.out.println(trie.startsWith("abc"));
}
}
Trie樹的時間和空間複雜度分析Trie樹的時間複雜度為O（k），k=該字符串（單詞或者前綴）的長度，在最好最壞的case均為O（k）。
Trie樹的空間複雜度，如果重複的前綴比較多，那麼一定程度上使用Trie是可以節省存儲空間的，但如果重複的前綴不多，這樣就會導致Trie消耗大量內存，為什麼這麼說？
還記得上面數組的實現方式嗎？在TrieNode裡面需要把每一種可能性都要提前存儲到一個數組，方便查找，拿英文單詞為例，一個單詞cat，看起來只需要3個char字符的空間就可以了，但實際上每個字符都需要存儲一個26大小的指針數組，這樣就需要O（n*k）的空間來存儲，k=字符串的長度，n=共有多少個這樣不重複的字符，這麼算下來，其實Trie樹的原理，可以看做是拿空間換時間的實現策略。
那麼有的同學會說使用數組的方式為了查找快速，沒辦法只能那麼存，那麼使用Map的方式是不是就節省內存了？其實並不是，不要忘記，Map的底層也是通過數組+鍊表+紅黑樹的方式實現的，初始化容量和每次擴容也都是需要開闢大量的前置空間來存儲的。所以相比數組的方式可能還要更浪費內存。
總結本文詳細的介紹了Trie樹相關的內容，Trie樹作為一種特殊的數據結構，雖然在實際開發中並不常用，但其在特定的場景下比如suggest自動補全功能，可以發揮的出色的表現。Trie樹本質上是一種通過空間換時間的策略，來提高檢索性能，所以在使用的時候要注意內存限制。當然，Trie樹在空間上也是有優化策略的，比如對部分前綴或者後綴進行壓縮，這樣以來能夠節省不必要的指針存儲，這種實現需要更複雜的編碼來支持，感興趣的朋友可以自己研究下。