Trie树

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较。

功能

Trie树主要使用来构建树形结构去存储字符串的每一位

方便我们后期对字符串进行查询

构建Trie树

如何对字符串的每一位进行存储呢?

我们可以使用二维数组son[N][26]来存储

N代表的是第N个结点

26代表的是N结点下有26个分支(因为都是单词,所以我们可以将结果映射到(0 - 25)

son[N][26]代表的就是N结点的儿子结点

同时我们需要创建一个新的数组tail[N]

对字符串的尾部结点进行收集,方便我们对出现的单词个数进行统计

根结点的值默认设置为0

插入

我们如何将一个字符串插入到Trie树中呢?

我们可以对每一位进行遍历,判断这一位是否出现过

如果出现过了那么就接着判断下一个字符

如果没有出现过就进行插入,创建出一条新的分支

void insert() {
int p = 0; //代表根结点
for(int i = 0;str[i];i++) { //当str[i] == '\0'的时候停止
int u = str[i] - 'a'; //确认分支
if(!son[p][u]) son[p][u] = ++idx; //如果发现这个分支上没有,创建一个新的分支
p = son[p][u]; //跳到这个分支接着循环下去
}

tail[p]++; //存入尾部分支的值
}

查找字符串

其实和上面是一样的我们也是先去遍历字符串

最终只需要将字符串末尾元素对应的值进行打印

void query() {
int p = 0;
for(int i = 0;str[i];i++) {
int u = str[i] - '0';
if(!son[p][u]) return 0;
p = son[p][u];
}

return tail[p];
}