搜索引擎最基本的原理-Trie树

什么是“Trie 树”？

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。

如何实现一棵 Trie 树？

Trie 树主要有两个操作

• 一个是将字符串集合构造成 Trie 树
• 一个是在 Trie 树中查询一个字符串

如何存储一个 Trie 树？

经典的存储方式

通过一个下标与字符一一映射的数组，来存储子节点的指针。

时间复杂度 O(k)， k表示目标查询字符串长度

Trie树的内存消耗

Trie树非常内存消耗内存，采用的是空间换取时间的策略。

Trie 树与散列表、红黑树的比较

• 字符串中包含的字符集不能太大。我们前面讲到，如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。
• 要求字符串的前缀重合比较多，不然空间消耗会变大很多。
• 如果要用 Trie 树解决问题，那我们就要自己从零开始实现一个 Trie 树，还要保证没有 bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。
• 我们知道，通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

思考

如果现在给你一个很大的字符串集合，比如包含 1 万条记录，如何通过编程量化分析这组字符串集合是否比较适合用 Trie 树解决呢？也就是如何统计字符串的字符集大小，以及前缀重合的程度呢？