Trie树

说到Trie树的数据结构，必须要列出其应用场景。在搜索引擎中关键词提示，引擎会自动弹出匹配关键词的下拉框，这种应用场景大家应该都很熟悉。如下图所示：

那么哪种数据结构能够高效实现这种算法，就是Trie树。

Trie树定义：字典树，它是一种树形结构。一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。本质就是利用字符串之间的公共前缀，将重复的前缀合并在一起。如how,hi,her,hello,so,see这6个字符串构造出来的就是下面图这个样子。

如何实现一颗Trie树

Trie树主要有两个操作：一是将字符串集合构造成Trie树，另一个是在Trie树种查询一个字符串。

show me code:

构建Trie树的过程需要扫描所有的字符串，时间复杂度是O(n) n-表示所有字符串的长度和。

每次查询时，如果要查询的字符串长度是k, 那么查找字符串的时间复杂度是O(k). 

Trie树很消耗内存

Trie树其实就是使用空间换时间的概念，来提高查询的效率。前面的列举的例子是查询小写字母，每个节点存储了26个下一个节点指针（a-z)，相当于多存储了8*26=208字节。如果每个字符串重复前缀较少，这样其实就浪费了大量的内存空间。

Trie树应用场景总结

1，字符串中包含的字符集不能太大。

2，要求字符串的前缀重复比较多，不然消耗空间会比较大。

3，如果要用Trie树解决问题，那我们就要自己从零开始实现一个Trie树，还要保证没有bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这么做。

4，Trie树通过指针串起来的数据块是不连续的，对缓存不友好。

如果在一组字符串中查找字符串的问题，工程中，更倾向于用散列表或者红黑树。因为这两种数据结构，不需要我们自己实现，直接利用编程语言提供的现成类库就行了。

实际上Trie树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。Trie树比较合适的是查找前缀匹配的字符串，也就是类似开篇这样的场景。