基础数据结构第七期 Trie树

前言

Trie树大家能够掌握即可，其实用到的地方并不多，本文将为大家介绍一下。

一、Trie树的基本内容

1、根节点不包含字符，除根结点之外每一个结点都只包含一个字符；
2、字典树用边表示字母表示
3、从根节点到某一结点， 路径上经过的字符连接起来，为该结点对应的字符串
4、每个节点的所有子结点包含的字符都不同。每个结点最多有26个子节点(假设给定字符集中包含26个英文字母)
5、有相同前缀的单词共用前缀节点
6、整棵树的根节点是空的，便于插入和查找
7、每个单词结束的时候用一个特殊字符表示，那么从根节点到任意一个特殊字符，所经过的边的所有字母表示一个单词
8、Trie树的空间效率较低，实际上是用空间来换时间的一种数据结构

图解：

二、典型例题

例1：

AC代码：

数组：

#include <iostream>
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;//下标是0的点,既是根节点,又是空节点
char str[N];

//插入操作
void insert(char str[]) {
	int p  = 0;//从根节点开始
	for (int i = 0; str[i]; i++) {//字符串末尾是0
		int u = str[i] - 'a';//把小写字母映射成0~25
		if (!son[p][u])//如果p这个节点不存在u这个儿子,
			son[p][u] = ++idx;//就把他创建出来
		p = son[p][u];//走到下一个节点
	}
	cnt[p]++;//以这个节点的单词数量多了一个
}

//查询
int query(char str[]) {
	int p = 0;//从根节点开始
	for (int i = 0; str[i]; i++) {
		int u = str[i] - 'a';//当前字母对应子节点的编号
		if (!son[p][u])
			return 0;
		p = son[p][u];
	}
	return cnt[p];//返回以p结尾的单词数量
}

int main() {
	int n;
	scanf("%d", &n);
	while (n--) {
		char op[2];
 
		scanf("%s%s", op, str);
		if (op[0] == 'I')
			insert(str);
		else
			printf("%d\n", query(str));
	}
	return 0;
}

STL：

#include<iostream>
using namespace std;
#include<map>
int n;
char c;
string x;
map<string,int>m;
int main()
{
	cin>>n;
	while(n--){
		cin>>c>>x;
		if(c=='I')
			m[x]++;
		if(c=='Q')
			cout<<m[x]<<endl;
	}
	return 0;
}

例2：

AC代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 31 * N;
int son[M][2];  

int a[N];
int idx;

void insert(int x)
{
	int p = 0;                                        
	for (int i = 30; i >= 0; i --)                   
	{
		int u = x >> i & 1;                     
		if (!son[p][u]) son[p][u] = ++ idx;           
		p = son[p][u];                                
	}
}

int query(int x)
{
	int p = 0, res = 0;  
	for (int i = 30; i >= 0; i --)                
	{
		int u = x >> i & 1;
		if (son[p][!u])                            
		{
			p = son[p][!u];                          
			res = res * 2 + !u;                      
		}                                            		
		else
		{
			p = son[p][u];
			res = res * 2 + u;
		}
		
	}
	return res;
}
int main()
{
	int n;
	scanf("%d", &n); 
	for (int i = 0; i < n; i ++)  scanf("%d", &a[i]);
	
	int res = 0;
	for (int i = 0; i < n; i ++)
	{
		insert(a[i]);
		int t = query(a[i]);                    
		res = max(res, a[i] ^ t);
	}
	printf("%d\n", res);
	return 0;
	
}

总结

这部分不是很难理解，大家熟练掌握即可，感谢大家的观看谢谢大家！！！