之前說搜索提示的時候留了一個尾巴，就是Trie樹的結構沒有說，這一篇簡單的說一下Trie樹的實現方式。
在計算機科學中，trie，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。Trie這個術語來自於retrieval。根據詞源學，trie的發明者Edward Fredkin把它讀作英語發音：/ˈtriː/ "tree"。但是，其他作者把它讀作英語發音：/ˈtraɪ/ "try"以上文字來自維基百科
搜索提示和分詞是Trie樹的經典應用範圍。
Trie樹又叫字典樹，本質上是一個多叉樹，每一個節點就是一個多叉的結構，如果是英文的匹配，那麼是一個26叉樹，每個節點一個26長度的數組，每個節點的數據結構如下
type TrieNode struct{
flag bool
hasNext bool
nexts [26]*TrieNode
}
其中flag保存的是當前節點是否已經是一個完整字符串了。hasNext表示是否還有下一節點，而Trie樹畫出來就是下面這個樣子。
從畫出來的圖，很直觀的可以看出來這棵樹的構造方法和遍歷方法，因為每個節點都有一個26長度的數組，來了一個字符，通過字符的編號直接就可以遍歷到下一個節點，查找的時候覆雜度就是O(K)，K表示查找的字符串長度，這種數據結構簡單明了，實現起來也很容易。但是這種數據結構有個問題，就是內存使用得太多了，如果是中文查找的話，需要把所有的中國字都編號到這個數組中，於是有一種優化方法，就是把數組變成變長的，如果按照二分進行每個節點的查找的話，每個節點的查找時間變成了O(lg(n))，整體的查找時間變成K*O(log(n))，n是數組平均長度，這樣的話，雖然內存的使用上降低了，但是查找速度變長了，而且插入的時候需要按序插入，插入也變慢了。按照真正的樹形結構，通過各種指針滿天飛的形式來實現Trie樹，基本上屬於新人練手的水平，純粹為了了解這個數據結構或者大學生做做課程設計，工程化的可能性幾乎為0。
正因為有上面的各種問題，於是有人發明了雙數組Trie樹，其實在這個之前還有個三數組的Trie樹，為了不讓大家更迷糊，我們直接來看看雙數組的形式吧。所謂雙數組Trie樹，當然就是通過兩個數組來實現這棵樹了，這兩個數組分別叫base數組和check數組，一個是基礎數組，一個是檢查數組，Suggestion服務對Trie樹的操作基本上需要有Trie樹的構建部分和Trie樹的查詢部分，插入操作基本上很少使用，後面說數據部分的時候會說到為什麼。Trie樹實際上是一種有限狀態機，通過狀態轉移矩陣在各個狀態之間跳轉，我們不去管這兩個概念，會越說越糊塗，如果你實在是有興趣，可以自己去查查資料，我們直接來點實在的，用一個例子來看看雙數組Trie樹是如何工作的。
假設我們的詞庫裡面有這麼一些詞，中國，北京，中華，華北這幾個詞語，需要構建一棵Trie樹，構建好了以後，用戶輸入中字的時候，能把中國，中華都給提示出來。這裡的例子直接使用了中文是為了更直觀，省得都是abc這種例子容易亂，雖然最後的處理上中文有點特殊，但不影響算法描述。
首先，拿到這些個詞以後，第一步就要構建這棵Trie樹了，構建之前，我們先對每一個字進行編號一下，這個只是為了方便描述，中:1,國:2,北:3,京:4,華:5。
初始化空數組，初始化base和check兩個空數組。
base的元素為1表示是開始位偏移為1，為-1表示沒有數據。
check的元素中，-1表示沒有數據，-2表示這是一個詞結束了，-3表示是根節點，如下圖所示
初始化好了以後就可以開始依次讀取數據了，先讀取出中國兩個字，開始插入
從根節點開始，base[0]=1，插入位置為base[0]+中，中的編號為1，所以是base[0]+1=1+1=2，於是得到應該插入到base[2]的位置。
檢查check[2]，看到check[2]為-1，表示base[2]沒有數據，可以插入
更新check[2]為上一個節點的base數組的下標，上一個節點是base[0]，所以更新為0
更新base[2]為上一個節點的base數組的值，上一個節點base[0]的值是1，所以更新為1
按照上面的四個步驟更新完了以後，整個數組變成下面這個樣子，對著圖可以仔細想想整個過程，然後你想想偽代碼是什麼樣子的，再想想如何編程。
由於這個詞語還沒結束，所以從base[2]開始繼續往下走
從base[2]開始，插入位置為base[2]+國，國的編號是2，所以是base[2]+2=1+2=3，應該插入到base[3]中
檢查check[3]，看到check[2]為-1，表示base[2]沒有數據，可以插入
更新check[3]為上一個節點的base數組下標，上一個是base[2]，所以更新為2
更新base[3]為上一個節點的base數組的值，上一個節點base[2]的值是2，所以更新為2
大家可以自己插入一下北京和中華這兩個詞，插入以後結構變成下面的樣子
到現在一切都很順利，接下來插入華北這個詞，這裡就會遇到衝突了，遇到衝突以後，進行如下算法
這個插入正常，最後圖像如下所示
由於這個詞語還沒結束，所以從base[6]開始繼續往下走
從base[6]開始，插入位置為base[2]+北，國的編號是3，所以是base[6]+3=1+3=4，應該插入到base[4]中
檢查check[4]，看到check[2]為0，表示base[4]有數據，產生衝突！！
從base[6]往後找空閒空閒，空閒空間的概念是兩個數組都是-1
找到base[8]和check[8]為空閒空間
更新check[8]為上一節點的值，6
計算base[6]應該的值為8-北=8-3=5，更新base[6]為5，解決衝突！！
要進行查詢，就相對簡單了，拿到一個詞，比如中華，先確定每個字的編號，然後按照兩個數組去遍歷，就知道這個詞在不在這個Trie樹中了，複雜度就是詞的長度。
本篇比較簡單，就是上次搜索提示的一個小尾巴，後面會說到分詞的技術，這個Trie樹也是分詞的主要數據結構。
如果你覺得不錯，歡迎轉發給更多人看到，也歡迎關注我的公眾號，主要聊聊搜索，推薦，廣告技術，還有瞎扯。。文章會在這裡首先發出來：）掃描或者搜索微信號XJJ267或者搜索中文西加加語言就行
相關閱讀：坑系列 --- 時間和空間的平衡