数据结构:字典树Trie-创新互联

Trie树
      • 作用
      • 存储图解
      • 查找图解
      • 代码实现
      • 习题

创新互联是一家专业提供衡阳县企业网站建设,专注与成都网站设计、成都网站建设、HTML5、小程序制作等业务。10年已为衡阳县众多企业、政府机构等服务。创新互联专业网站建设公司优惠进行中。作用

用来高效快速存储和查找字符串集合的一种数据结构

存储图解

假设有若干个字符串在这里插入图片描述

先创建了一个根结点root,代指字符串集合的开头,对第一个字符串abcdef存储就如上图所示

在这里插入图片描述

当存储abdef时,一直走到b都和abcdef相同,于是在b点另开一个分支存储之后的def

当存储aced时,一直走到a都和abcdef相同,于是在a点另开一个分支存储之后的ced

以此类推

我们就得到能够以树的形式存储一个字符串集合

在这里插入图片描述

并且在每个字符串的结尾的字母都标记一下,表示以该字母结尾的节点是存在一个字符串的

如果有类似abc这样的字符串,也要在c点标记一下

查找图解

如果要查找一个不存在的字符串,比如abcf

在这里插入图片描述

沿着树枝一直走,走到c之后发现没有f对应的路径,那么就说明该字符串不存在

或者查找一个字符串,该字符串在存储里的字符串不存在,但属于某个存储的字符串的前缀

比如abcdef中的abc作为要查找的字符串

沿着树枝走,发现c点没有标记,即使有对应对应路径也不能说明该字符串存在

代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#includeusing namespace std;

const int N = 100010;

int son[N][26];//代表每个节点可以有26个子节点
int cnt[N];//以当前这个点结尾的字符串有多少个
int idx;//操作次数,当前用到了哪个下标
//下标是0的点,既是根节点,也是空节点
char str[N];

void insert(char str[])//插入新字符串
{int p = 0;//根节点
	for (int i = 0;str[i];i++)
	{int u = str[i] - 'a';//存储编号,字母a-'a'就变成了0,b就变成了1
		//如果说该节点之后没有这个字母,即son[p][u] == 0
		if (!son[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;//如果不存在直接返回0
		p = son[p][u] ;
	}

	return cnt[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;
}
习题

在这里插入图片描述

暴力做法

利用两重for循环来寻找大异或

//暴力法
	for (int i = 0;i< n;++i)
	{for (int j = 0; j< i;++j)
			res = max(res, (arr[i] ^ arr[j]));
	}

能被看作是trie树的原因

因为运算方式是异或,而异或看的是二进制,如果两个数的二进制某一位相同则为0,不同则为1

因此可以用31个长度的数组存储两个数的每一位

且对二进制从左往右看时,假设一个数为0,可以用trie树查询最高位为1的数,再找下一位为1的数,以此类推,便可以快速找出异或后的大数

在这里插入图片描述

因此,对某个数查询能够在存储里的数寻找大异或时,可以从最高位依次查找每一位相异的数

实现代码

#define _CRT_SECURE_NO_WARNINGS 1
#include#include 

using namespace std;

const int N = 100010;
const int M = N * 31;

int arr[N];
int son[M][2];
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;
	int 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;//相当于把所有的位数进一再加上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", &arr[i]);

	int res = 0; 

	for (int i = 0;i< n;++i)
	{insert(arr[i]);
		//先插入在查询,防止第一次查询不到的情况
		int t = query(arr[i]);

		res = max(res, (arr[i] ^ t));
	}
	printf("%d", res);
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文名称:数据结构:字典树Trie-创新互联
分享路径:http://ybzwz.com/article/doisce.html