文章目录
一、Tire 树
1. Tire 树介绍
2. 优缺点及性质
3. 具体实现可见例题 Tire 字符串统计
二、Tire 树例题——Tire 字符串统计
具体实现
1. 实现过程
2. 代码注解
3. 实现代码
三、Tire 树例题——最大异或对
具体实现
0. 暴力做法
1. 实现思路
2. 实现代码
一、Tire 树
1. Tire 树介绍
- Tire 树 又称单词查找树，是一种树形结构，是一种哈希树的变种。
- Tire 树是一种能够快速存储和查找一组字符串集合的数据结构，是以空间换时间，利用字符串的前缀来降低查询时间。
与二叉树不同，Tire 树有 26 子节点对应 26 个字母，根节点不包含字符串，从根节点到某个节点，经过的字符连起来的字符串就是对应的字符串。当储存结束一个字符串后，尾节点会产生一个标记，表示当前字符串已经结束了。
典型应用：用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
- 如下图就是一棵由字符串 abcdef，abdef，aced，bcdf，bcfc，bcff，cdaa，组成的 Tire 树：
2. 优缺点及性质
- 优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
- 缺点：空间复杂度比较大。
- 优化：我们可以用链表来动态开辟空间，达到空间上利用率的最大化。
- 性质：
- （1）根结点不包含字符，其他的每一个节点只包含一个字符。
- （2）从根结点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串（假如某个节点为一个字符串的结尾，对其打个标记即可）。
- （3）每个节点的所有子节点包含的字符都不相同。
3. 具体实现可见例题 Tire 字符串统计
二、Tire 树例题——Tire 字符串统计
题目描述
维护一个字符串集合，支持两种操作：
I x 向集合中插入一个字符串 x；
Q x 询问一个字符串在集合中出现了多少次。
共有 N 个操作，所有输入的字符串总长度不超过 1e5，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。
每个结果占一行。
数据范围
1 ≤ N ≤ 2∗1e4
输入样例
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例
1
0
1
具体实现
1. 实现过程
- Tire 树的插入和查询功能的实现。
- （1）
I x向集合中插入一个字符串 x。
void insert(char str[]) { int p=0; for(int i=0;str[i];i++) { int u=str[i]-'a'; if(!son[p][u]) { idx++; son[p][u]=idx; } p=son[p][u]; } cnt[p]++; }
- （2）
Q x询问一个字符串在集合中出现了多少次。
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; } else { p=son[p][u]; } } return cnt[p]; }
2. 代码注解
int son[N][26]; 表示树当中每个点的所有子节点。
int cnt[N]; 表示以当前这个点结尾的单词有多少个。
int idx; 表示当前用到了哪个下标。这里需要注意：下标是 0 的点，既是根节点，又是空节点。
C++ 字符串结尾是 \0 ，因此 str[i] 可以判断字符串是否走到结尾。
int u=str[i]-‘a’; 将小写字母 a~z ，映射成数字 0~25。
3. 实现代码
#include <bits/stdc++.h> using namespace std; const int N=100010; int son[N][26]; int cnt[N]; char str[N]; int idx; void insert(char str[]) { int p=0; for(int i=0;str[i];i++) { int u=str[i]-'a'; if(!son[p][u]) { idx++; 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]; } int main() { int n; cin>>n; while(n--) { char op[2]; scanf("%s%s",op,str); if(op[0]=='I') { insert(str); } else { cout<<query(str)<<endl; } } system("pause"); return 0; }
三、Tire 树例题——最大异或对
题目描述
在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1～AN。
输出格式
输出一个整数表示答案。
数据范围
1 ≤ N ≤ 1e5
0 ≤ Ai < 2的31次方
输入样例
3
1 2 3
输出样例
3
具体实现
0. 暴力做法
- 暴力做法通俗易懂，两个 for 循环，相互枚举每一个值，异或，最后答案为其中的最大值。
- 暴力做法虽然易做，但是会出现 超时 问题。
#include <bits/stdc++.h> using namespace std; const int N=100010; int n; int a[N]; int main() { cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } int res=0; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { res=max(res,a[i]^a[j]); } } cout<<res<<endl; system("pause"); return 0; }
1. 实现思路
- 首先，需要搞清楚 异或操作。
- 如果 A = 1101 ，B = 0111，那么 A ^ B = 1010。详细讲解请见 基础算法-位运算
- 对暴力做法进行优化，使其满足时间限制。
- 由异或操作的计算公式可知，我们只需要先遍历每一个数，然后根据遍历的数的对应二进制形式，选取一个尽可能二进制形式每一位都不同的数字，得到该数字的最大异或值，最后再选举最大的异或值。在得到每一个数字的最大亦或值的选取过程就是一个 Tire 数。
- 举例说明：
2. 实现代码
#include <bits/stdc++.h> using namespace std; const int N = 100010, M = 3100010; int n; int a[N], son[M][2], idx; void insert(int x) { int p = 0; for (int i = 30; i >= 0; i -- ) { int &s = son[p][x >> i & 1]; if (!s) { idx ++; s = idx; } p = s; } } int search(int x) { int p = 0, res = 0; for (int i = 30; i >= 0; i -- ) { int s = x >> i & 1; if (son[p][!s]) { res += 1 << i; p = son[p][!s]; } else { p = son[p][s]; } } return res; } int main() { cin >> n; for (int i = 0; i < n; i ++ ) { cin >> a[i]; insert(a[i]); } int res = 0; for (int i = 0; i < n; i ++ ) { res = max(res, search(a[i])); } cout << res << endl; system("pause"); return 0; }
