2.1　Trie樹

Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是哈希樹的一種變種。Trie樹的典型應用是排序大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是可最大限度地減少無謂的字符串比較，查詢效率比哈希表高。

Trie樹的核心思想是空間換時間，即利用字符串的公共前綴來降低查詢時間的開銷，以達到提高效率的目的。

2.1.1　Trie樹的原理

假設有abc、abd、bcd、abcd、efg、hii六個單詞，構建的Trie樹如圖2.1所示。

對于每一個節點，從根遍歷到它的過程就是一個單詞，如果這個節點被標記為紅色（圖2.1中有陰影的小圓圈），就表示這個單詞存在，否則不存在。那么，對于一個單詞，只要順著根走到對應的節點，再檢查這個節點是否被標記為紅色，就可以知道它是否出現過了。把這個節點標記為紅色，就相當于插入了這個單詞。

查詢和插入可以一起完成（重點體會這個查詢和插入是如何一起完成的，下文將具體解釋），所用時間僅僅為單詞長度。Trie樹每一層的節點數是26i級別的，為了節省空間，用動態鏈表或者用數組來模擬，空間的花費不會超過單詞數×單詞長度。

Trie樹有3個基本性質：

●　根節點不包含字符，除根節點外的每一個節點都只包含一個字符。

●　從根節點到某一節點，將路徑上經過的字符連接起來，即可得到該節點對應的字符串。

●　每個節點的所有子節點包含的字符都不相同。

Trie樹是一個很重要的數據結構，主要應用為：

（1）詞頻統計：如給定一個由10萬個單詞組成的庫，現要判斷一個單詞是否在庫中出現，若出現，求出共出現多少次。

（2）前綴匹配：以圖2.1為例，如果想獲取所有以“a”開頭的字符串，那么從圖中可以很明顯地看到abc、abd、abcd。利用這個特性，可以巧妙地實現搜索提示功能，如輸入一個網址，可以自動列出可能的選擇。當沒有完全匹配的搜索結果，可以列出前綴最相似的可能。

2.1.2　Trie樹的實現

將根節點編號為0，然后把其余節點編號為從1開始的正整數，用一個數組來保存每個節點的所有子節點，用下標直接存取。具體來說，可以用ch[i][j]保存節點i的那個編號為j的子節點。將字符串中的小寫字母按照字典序編號為0、1、2…，則ch[i][0]表示節點i的子節點a。ch[i][j]=1表示該子節點存在，否則表示不存在。用sigma_size表示字符集的大小，如當字符集為全部小寫字母時，sigma_size=26。

使用Trie樹的時候，往往需要在單詞節點上加附加信息，其中val[i]表示節點i的附近信息。例如，如果每個字符串有個權值，可以把權值存于val[i]中。

2.1.3　例題講解

例2-1　Xor Sum

Time Limit:2000/1000 ms（Java/Others）　Memory Limit:132768/132768 KB（Java/Others）

題目描述：

Zeus和Prometheus做了一個游戲，Prometheus給Zeus一個集合，在集合中包含N個正整數，隨后Prometheus將向Zeus發起M次詢問，在每次詢問中包含一個正整數S，之后Zeus需要在集合中找出一個正整數K，使得K與S的異或結果最大。

輸入：

輸入包含若干組測試數據，每組測試數據包含若干行。

輸入的第一行是一個整數T（T<10），表示共有T組數據。

每組數據的第一行輸入兩個正整數N、M（1≤N、M≤100000），在接下來的一行中包含N個正整數，代表Zeus獲得的集合；在之后的M行中，每行一個正整數S，代表Prometheus詢問的正整數。所有正整數均不超過232。

輸出：

對于每組數據，首先需要輸出單獨一行“Case #?:”，其中問號處應填入當前的數據組數，組數從1開始計算。

對于每個詢問，輸出一個正整數K，使得K與S異或值最大。

樣例輸入：

2

3 2

3 4 5

1

5

4 1

4 6 5 6

3

樣例輸出：

Case #1:

4

3

Case #2:

4

題目來源：HDU4825。

解題思路：

把每一個數都轉換成二進制（位置要對齊，前面不足則補0），轉換的長度和題目給的數據范圍有關，對于該題，33位就夠了。更新Trie樹的順序和過程是從左到右地遍歷插入各位二進制數值，但顯然next指針只有兩個—next[0]與next[1]，更新的最后是把原來的值附到結尾節點的val上，表示這整條路對應的十進制數值是val。

如何求最大異或值呢？首先要知道在一般情況下，正項等比序列前n-1項求和的值肯定要小于第n項的值，也就是說，在最壞情況下走第x個節點，但是x+1到n個節點都是0，也比不走x，但是x+1到n個節點都是1的情況好。

假設已經得到了最大異或值Max，那么Max異或K就可以得到某個數Xi了，此時不知道Xi是什么，可以通過貪心算法找到它。

題目實現：