文章目录
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展示在搜索提示框内,搜索引擎最基本原理。