Trie树,又被称为前缀树。

    它查询的基本原理是通过当前字的下一个字定位到其子节点。如果我们限制所有有效的输入仅是普通的英文字母,那么它最多会有52个子节点。我之前见过的一种做法就是一旦插入产生第一个子节点, 所有52个节点会同时生成。这种做法的好处是查询速度非常快, 因为直接通过输入的字符就直接可以定位到子节点。缺陷也非常的明显, 即是上述的应用场景都会造成严重的空间浪费.。如果我们把字符集加大到所有汉字, 那么这个空间浪费将是承受不起的。

    另一种建树的思路可以解决上述结构造成空间浪费的问题, 思路如下。所有的节点按照一定的顺序保存到一维数组中, 每个节点保存其第一个子节点在该一维数组中的位置(也可以是和当前节点的偏移量), 同时保存子节点的个数。知道子节点的位置便可以将其直接定位到, 知道子节点的个数我们就可以通过遍历来确定查询词是否在Trie树中。这样的实现在查询时间上会稍微逊色于前一种，但是其空间利用率是非常高效的。

    通常的一种应用是找到以某个查询串为前缀的所有成词。具体的实现可以是深度优先查找和广度优先查找。广度优先查找是需要一个临时的数组来保存扫描到的节点的所有子结点，这样如果数据量大时会消耗掉一定的内存。深度优先查找也需要一个临时变量保存当前节点已经扫描过的子节点数，其性能应该较优于广度有限查找，只是代码会难写一些。

    建树的过程比较复杂。其基本思路是按层建树。需要的一个重要的临时变量是记录每一个词中的每一个字所成的词（比如词是‘笑猫日记’，扫描到‘猫’时所成的词是‘笑猫’）在一维数组中的位置。之所以需要这个信息，是我们扫描的其子节点时，才会去填写偏移量和子节点个数的信息。扫描时，如果发现当前字的前一个字和前面一个词当前字（层级都是n）的前一个字不同时，可以通过那个临时变量定位到以前一个字成词在一维数组中的位置，填写该节点的子节点数为1，偏移量为当前一维数组的大小减去上面的位置数；否则子节点数加一。如果当前字和扫面的前一个词的当前字不同，我们需要把以当前字所成的词放入一维数组中去，并记录相关临时变量的值。

一种trie树 的实现方式