[数据结构与算法]Trie树

前言

Trie树，一种高效的存储和查找字符串集合的数据结构。

提示：以下是本篇文章正文内容，根据acwing上y总的讲解进行整理，方便自己复习。刚开始尝试写博客，能力有限，敬请雅正。

一、建树存储

拿如下字符串举例：

建树如图所示

每一个字符串的结尾处应有标记，表示该字符串已经建好。

二、查询

假设查询如下字符串

1.绿色路径对应字符串aced，可以发现刚好可以走到结尾处，说明该字符串存在。
2.红色路径对应字符串abcf，可以发现c的子节点没有f，即该字符串不存在。
3.橙色路径对应字符串cda，可以发现每一个节点都存在，但是没有到结尾处，该字符串也不存在。

上述图示是为了便于理解Trie树，当然还需结合题目和代码进行进一步理解。
题目链接：Trie字符串统计
代码如下：

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
using namespace std;
typedef long long  ll;
typedef pair<int, int> P;
const int N = 1e5 + 6, M = 1e6 + 6;
const int inf = 0x3f3f3f3f;
//因为是小写字母，故每个节点的子节点最多26个
//cnt记录字符串的个数
//idx则为当前节点
int son[N][26], cnt[N], idx;
char op, str[N];
//建图存储
void insert(char str[])
{
    int p = 0;//建立根节点
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a'; //将26个英文字母映射成数字1-26
        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 -- )
    {
        scanf(" %c", &op);
        if (op == 'I')
        {
            scanf("%s", str);
            insert(str);
        }
        else
        {
            scanf("%s", str);
            printf("%d\n",query(str));
        }
    }
    return 0;

}

上述题目为简单的模板题，接下来为变形题，可进一步巩固对Trie树的了解。
题目链接：最大异或对

题目大意：
从给定的数中选取任意两个数进行异或运算，找到异或结果最大的。

思路：
1.首先明白异或运算就是对二进制位进行非进位加法运算，即相同为0，不同为1。要让异或结果最大，则尽可能让对应的二进制位相反，这样得到的结果才最大。
2.将每一个整数对应成31位二进制数，存入Trie树中，然后对每一个整数进行查询，找到其对应的异或值最大的数。
3.我们进行先插入再查询的操作，这样就避免了重复查询。

举一个简单的例子
输入数据

插入数据后进行查询时，尽可能找相反的。假设当前为0，那么接下来就尽可能找1；当前为0，那么接下来就找1。若不存在，则只能找相同的数。
接下来上题解代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 6;
//每一位数对应31位二进制数，数据范围为1e5
int son[31 * N][2], idx;
void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i -- )
    {
        //位运算，判断第i位二进制数是0还是1
        int u = x >> i & 1;
        if (!son[p][u]) 
            son[p][u] = ++ idx;
        p = son[p][u];
    }
}
int query(int x)
{
	//res计算最大的那个结果值
    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 << 1) + !u;
        }
        else
        {
            //若相反位不存在
            p = son[p][u];
            res = (res << 1) + u;
        }
    }
    return res;
}
int main()
{
    int n, res = 0;
    scanf("%d", &n);
    for (int i = 0; i < n ; i ++ )
    {
        int x;
        scanf("%d", &x);
        //先插入再询问
        insert(x);
        int y = query(x);
        res = max(res, x ^ y);
    }
    printf("%d", res);
    return 0;
}

总结

Trie树的概念理解起来还是比较简单的，但是根据题目要能分析出Trie类型还是比较不容易的，还是要尽可能的多见识一些题目类型。