文章目录
- 1. 什么是“Trie树”？
- 2. 如何实现一棵Trie树？
- 3.Trie树真的很耗内存吗？
- 4.Trie树与散列表、红黑树的比较
- 5. 解答开篇
问题：搜索引擎的关键词的联想词是如何实现的？
1. 什么是“Trie树”？
Trie树，也叫“字典树”。Trie树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。
有6个字符串，它们分别是：how，hi，her，hello，so，see。构造成如下图形：
2. 如何实现一棵Trie树？
Trie树是多叉树。代码表示：
class TrieNode {char data;TrieNode[] children;
}
时间复杂度：构建时间复杂度是O(n)（n表示所有字符串的长度和），查收是O(k), k是字符串长度。
3.Trie树真的很耗内存吗？
比较耗内存。
4.Trie树与散列表、红黑树的比较
Trie树有极其严苛的要求：
- 字符串中包含的字符集不能太大。如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，但也要付出牺牲查询、插入效率的代价。
- 要求字符串的前缀重合比较多，不然空间消耗会变大很多。
- 如果要用Trie树解决问题，那我们就要自己从零开始实现一个Trie树，还要保证没有bug，这个在工程上是将简单问题复杂化，除非必须，一般不建议这样做。
- 我们知道，通过指针串起来的数据块是不连续的，而Trie树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。
一般从字符串中查询字符串，用哈希表或红黑树。Trie树不适合精确匹配
5. 解答开篇
以he为前缀的hello、her展示在搜索提示框内，搜索引擎最基本原理。
