資料結構與算法專題——第十二題 Trie樹
今天來聊一聊Trie樹，Trie樹的名字有很多，比如字典樹，字首樹等等。
一：概念
下面有and,as,at,cn,com這幾個關鍵詞，建構成 trie 樹如下。
- 根節點不包含字元，除根節點外的每一個子節點都包含一個字元。
- 從根節點到某一節點，路徑上經過的字元連接配接起來，就是該節點對應的字元串。
- 每個單詞的公共字首作為一個字元節點儲存。
二：使用範圍
既然學Trie樹，肯定要知道這玩意是用來幹嘛的？
1. 詞頻統計。
可能有人要說了，詞頻統計簡單啊，一個hash或者一個堆就可以打完收工，但問題來了，如果記憶體有限呢？還能這麼玩嗎？這種限制級條件下就可以用trie樹來壓縮下空間，因為公共字首都是用一個節點儲存的。
2. 字首比對
就拿上面的圖來說吧，如果我想擷取所有以 "a" 開頭的字元串，從圖中可以很明顯的看到是：and,as,at，如果不用trie樹，你該怎麼做呢？很顯然樸素的做法時間複雜度為O(N2) ，用Trie樹就不一樣了，它可以做到h，h為你檢索單詞的長度，可以說這是秒殺的效果。
舉個例子：現有一個編号為1的字元串”and“，怎樣插入到trie樹中呢？采用動态規劃的思想，将編号”1“計入到每個途徑的節點中，那麼以後我們要找”a“，”an“，”and"為字首的字元串的編号将會輕而易舉。
三：實際操作
到現在為止，我想大家已經對trie樹有了大概的掌握，下面看看如何來實作。
1：定義trie樹節點
為了友善，我也采用純英文字母，大家都知道字母有26個，是以建構的trie樹就是一個26叉樹，每個節點包含26個子節點，實作代碼如下：
/// <summary> /// Trie樹節點 /// </summary> public class TrieNode { /// <summary> /// 26個字元，也就是26叉樹 /// </summary> public TrieNode[] childNodes;
/// <summary> /// 詞頻統計 /// </summary> public int freq;
/// <summary> /// 記錄該節點的字元 /// </summary> public char nodeChar;
/// <summary> /// 插入記錄時的編碼id /// </summary> public HashSet<int> hashSet = new HashSet<int>();
/// <summary> /// 初始化 /// </summary> public TrieNode() { childNodes = new TrieNode[26]; freq = 0; } }