Trie字典树

Trie字典树是一种数据结构主要用来高效的存储和查询字符串

Trie思路

Trie树处理的问题一般都会说存储的字符串都是小写字母或者大写字母或者数字等等，反正肯定会限制一个范围，假设问题是有一堆只有小写字母组成的字符串，我们需要将他们存储并且查询指定字符串出现次数之类的

Trie树的思路是说，因为一共就26个小写字母，那么如果字符串很多那么肯定会有很多字符重复，比如”ababa”和”ababc”，如果要存储这俩字符串，就得一共存储10个字符也就是10字节，但是他们都有一个公共前缀”abab”这个是重复的那就不需要多存储一次，如果不理解就看图

image.png

Trie形式大概就是这样，如果字符串数量特别多，那么小写字母就26个一定会有大量重复，所以就会节省很多空间

Trie存储

首先树肯定有一个根节点，对于一个字符串s长度是n，如果根节点的儿子节点没有s[0]那就开辟一个新的分支存储s[0]，然后看s[0]节点的儿子节点有没有s[1] (不过因为s[0]都是新开辟的所以肯定不存在儿子节点)，那假如根节点的儿子节点有s[0]那就走进去那个儿子节点，去看那个儿子节点的儿子节点有没有s[1]以此类推，直到没有没有就新开辟，或者直到字符串存储完，当你存储完这个字符串s在最后存储的节点记录一下，表示以这个节点结尾的字符串数量方便后面查询

Trie查询

查询一个字符串s长度为n出现的次数，那其实跟存储的逻辑是一样的，就是这样去看根节点的儿子节点是否存在s[0]不存在直接返回0，存在就继续看这个儿子节点的儿子节点是否存在s[1]依次类推 ，如果这个过程有一个字符不存在那就返回0否则就一直往下找直到找完这个字符串s，如果成功找到字符串s那就返回他的数量(存储的时候存储了以某个字符为结尾的字符串数量)

代码

Trie树的逻辑和代码都很简单，所以你要是觉得上面没看懂那直接看代码就好了其实

Trie模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N =1e6+5;
int tr[N][26],cou[N],idx;//其实应该用指针去连接每个节点，但是做题其实一般不考虑空间所以用数组模拟即可，tr数组就是字典树
						//cou[i]表示以i节点字符结尾的字符串个数，idx表示根节点，但是也表示接下来要存储的节点下标其实
char str[N];
void insert(char *s){//存储操作
	int p=0;//当前节点下标或者说编号，从根节点开始
	for(int i=0;s[i];i++){//遍历整个要插入的字符串
		int u = (s[i]-'a');//讲字符串转换成数字
		if(!tr[p][u])tr[p][u]=++idx;//如果p节点的儿子节点没有要插入的这个字符那就开辟一个分支用来存储这个字符
		p=tr[p][u];//将当前节点更新成当前结点的那个儿子节点然后继续往下存储
	}
	cou[p]++;//最终存储完p就是这个字符串最后一个字符存储的节点编号，cou[p]++就表示以这个节点编号结尾的字符串数量+1
}

int query(char *s){//查询操作
	int p = 0;//当前节点下标或者说编号，从根节点开始
	for(int i=0;s[i];i++){//遍历整个要插入的字符串
		int u = (s[i]-'a');//讲字符串转换成数字
		if(!tr[p][u])return 0;//如果p节点的儿子节点没有要插入的这个字符那就表示当前Trie树不存在这个字符串那就返回0
		p=tr[p][u];////将当前节点更新成当前结点的那个儿子节点然后继续往下查找
	} 
	return cou[p];//如果找到了就返回字符个数
}

int main(){

	int t;
	char op;
	scanf("%d",&t);
	while(t--){
		scanf(" %c %s",&op,str);
		if(op=='I'){
			insert(str);
		}
		else{
			printf("%d\n",query(str));
		}
	}

	return 0;
}