Trie树
数据结构初见：Trie树
今天，我们来了解一下Trie树这种数据结构，来看看专属于它的数据结构之美，(●ˇ∀ˇ●)
Trie树的基本功能
在之前我们可能会遇到一种题，比如说，现在我们有m个小写字母字符串，然后，我们有n个询问，对于每一个询问会告诉我们一个字符串，让我们在那m个字符串里面找到一样的，找到的话就输出yes，不然就输出no
一般情况下，我们会用一个二维数组，把所有的字符串保存在二维数组里面，对于每一次询问，我们对数组进行依次遍历，直到找到符合的字符串，但是呢，这么做的话，就会很麻烦，因此，伟大的前辈们研究出来了一种可以很好解决这一类题目的方法，那就是Trie树这么一种数据结构
那么，Trie树是怎么对于这些字符串数组进行存储的呢？欸，其实也是一个二维数组，只不过存储方式不太一样，假如说，我们现在有一下这些字符串
abcde
abd
abdc
abc
bcd 在存储一个字符串之前，我们先设置一个根节点，这个节点的目的就是作为存储的根，可以让我们更加方便地查询。好的，现在我们开始存储第一个字符串吧
我们从根节点开始找起，看看有没有一个叫做a字符的子节点，如果没有的话，我们就创建一个a字符子节点，像这样
根
a 我们添加了字符a这个子节点，然后，我们再从a这个子节点开始找，看看能不能找到字符b，如果不能找到的话，那么就创建一个字符b这么个子节点，像这样
根
a
b然后，像这样依次进行下去，直到把整个字符串全部存储到Trie树里面，像这样
根
a
b
c
d
e通过5次存储，最后，我们存储了所有的字符串进入Trie树里面
根
a b
b c
c d d
d c
e在这棵树里面，就存储了5个字符串，但是，我们在查询的时候如果仅仅这么做的话，我们就不知道我们一开始存了哪些字符串，那么如果我们查询abcd这个字符串，在Trie树里面是可以找到的，但是我们一开始的字符串里面是没有abcd这个字符串的，所以我们对于每一次存储，都要做一个记号，说明这个地方有字符串，这样的话就可以灵活的查询了
原题如下：
——————题目来自acwing
维护一个字符串集合，支持两种操作：
I x向集合中插入一个字符串x；Q x询问一个字符串在集合中出现了多少次。
共有 N 个操作，所有输入的字符串总长度不超过 105，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N，表示操作数。
接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2^104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab输出样例：
1
0
1基本功能实现
上述解释可以转变成代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int son[N][26], idx, cnt[N];
//往Trie树里面添加字符串
void add(char ch[])
{
int p = 0;
for(int i = 0;ch[i];i++) {
int u = ch[i] - 'a';
//如果这个节点没有创建出来，就新开一个节点
if(!son[p][u]) son[p][u] = ++idx;
//找到子节点
p = son[p][u];
}
//对应的字符串印记增加
cnt[p]++;
}
//向Trie树里面询问字符串
int query(char ch[])
{
int p = 0;
for(int i = 0;ch[i];i++) {
int u = ch[i] - 'a';
//如果有一个节点是没有的，说明字符串不存在
if(!son[p][u]) return 0;
p = son[p][u];
}
//找到了这么一个字符串，但是字符串可能不存在
return cnt[p];
}
int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i++) {
char ch[2], s[N];
scanf("%s%s",ch, s);
if(ch[0] == 'I') add(s);
else cout << query(s) << endl;
}
return 0;
}如此一来，我们就可以自由地查询字符串了
现在，我们来一道小题来练练手吧（
练习题目
在给定的 N 个整数 A1，A2……AN 中选出两个进行 xor（异或）运算，得到的结果最大是多少？
输入格式
第一行输入一个整数 N。
第二行输入 N 个整数 A1～AN。
输出格式
输出一个整数表示答案。
数据范围
1≤N≤10^5,
0≤Ai<2^31
输入样例：
3
1 2 3输出样例：
3——————————————————————分割线——————————————————————
好的，初看此题，大家的想法应该是先创建一个二维数字数组，对于每一个数都存储进去，然后再进行for循环嵌套for循环依次计算每一个数的异或值，最后再得出最大答案
没错，这确实可以计算出来，但是对于复杂度来说较高，因为计算量会大于10^8，而c++一秒内只能计算10^7 —- 10^8的数值，所以我们会超时，因此，我们得考虑其它的算法，那么有没有其它的方法呢？
肯定是有的，不然怎么会出现在这里，对于每一个数，我们可以依次存储到Trie树里面，但是怎么存呢，这就需要很巧妙的方法了
算法讲解
首先，我们要知道怎么计算两个数的异或值，对于5和3两个数，
5的二进制 0000 0101
3的二进制 0000 0011
异或值为7 0000 0111没错，我们计算二进制的时候是通过二进制计算的，所以说，我们可以把每一个数都转化成二进制数，依次保存到Trie树里面，这样一来，我们就可以有选择的找每一个数对应的最大异或数，再求出每一个数的最大异或值，这样的话就会避免很多难题，
那么，问题又来了，我们该怎么查找与该数字相匹配的指定数字的最大异或数呢？
我们来看看5，在2^8里面，5可以和谁组成最大异或数？
5的二进制 0000 0101
n的二进制 1111 1010
很明显，5和n可以组成最大异或数，也就是从高位往低位进行寻找，5的最高位是0，那么我们就要找最高位是1的，这样依次查询下去，如果没有对应的相反的值，那就只能找一样的，但是依然可以保证每一个数都找到最大异或数，最后依次比较
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010, M = 31*N;
int a[N], idx, son[M][2];
//把每一个数都添加到Trie数里面
void add(int x)
{
int p = 0;
//从最高位开始存储
for(int i = 30;i >= 0;i--) {
//通过位运算求出这个数的第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 ans = 0;
for(int i = 30;i >= 0;i--) {
int u = x>>i&1;
//找得到相反的
if(son[p][!u]) {
p = son[p][!u];
//二进制求和
ans = ans * 2 + !u;
}
//找不到相反的，就找个次的
else {
p = son[p][u];
//二进制求和
ans = ans * 2 + u;
}
}
//返回
return ans;
}输入输出代码：
int main()
{
int n;
cin >> n;
int sum = 0;
for(int i = 0;i < n;i++) {
cin >> a[i];
add(a[i]);
int ans = query(a[i]);
sum = max(sum, ans^a[i]);
}
cout << sum << endl;
return 0;
}总结
以上就是关于Trie树的基础内容了，相信通过这个知识点的学习，可以更好的了解数据结构的奥妙之美，ヽ(✿ﾟ▽ﾟ)ノ
