2.1 Trie树
Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是哈希树的一种变种。Trie树的典型应用是排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是可最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie树的核心思想是空间换时间，即利用字符串的公共前缀来降低查询时间的开销，以达到提高效率的目的。
2.1.1 Trie树的原理
假设有abc、abd、bcd、abcd、efg、hii六个单词，构建的Trie树如图2.1所示。
图2.1 Trie树
对于每一个节点，从根遍历到它的过程就是一个单词，如果这个节点被标记为红色（图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是什么，可以通过贪心算法找到它。
题目实现：
