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() {
		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];
}