Trie(字典树)
Trie树
Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较。
功能
Trie树主要使用来构建树形结构去存储字符串的每一位
方便我们后期对字符串进行查询
构建Trie树
如何对字符串的每一位进行存储呢?
我们可以使用二维数组son[N][26]
来存储
N代表的是第N个结点
26代表的是N结点下有26个分支(因为都是单词,所以我们可以将结果映射到(0 - 25)
son[N][26]
代表的就是N结点的儿子结点
同时我们需要创建一个新的数组tail[N]
对字符串的尾部结点进行收集,方便我们对出现的单词个数进行统计
根结点的值默认设置为0
插入
我们如何将一个字符串插入到Trie树中呢?
我们可以对每一位进行遍历,判断这一位是否出现过
如果出现过了那么就接着判断下一个字符
如果没有出现过就进行插入,创建出一条新的分支
void insert() { |
查找字符串
其实和上面是一样的我们也是先去遍历字符串
最终只需要将字符串末尾元素对应的值进行打印
void query() { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Freedom Coding!
评论
ValineDisqus