Trie树（字典树）

4.Trie树（字典树）

Trie树，又称字典树，是用来高效存储和查找字符串集合的一种数据结构查找时，可以高效的查找某个字符串是否在Trie树中出现过，并且可以查找出现了多少次

利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

主要性质：

根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符互不相同。
从第一字符开始有连续重复的字符只占用一个节点，比如上面的catch和cat中重复的单词cat只占用了一个节点。

Acwing 835.Trie字符串统计

实现思路：

设置一个二维数组s[p][u]初始为0，p代表当前结点，u代表当前结点的某个子结点（u的取值为0~25对应26个字母），即s[p][u]不为0代表p结点下连接着下标为u的字母
插入操作：设置一个idx指向要操作的数组下标位置（作用同单链表中的idx），每次插入一个字符串，循环处理每一个字符。利用u=str[i]-'a'将每个字符转化为整数操作，判断s[p][u]的值是否为0。若为0，不存在该字符，就插入该字符，即令s[p][u]=++idx，然后下移到子结点继续插入字符串的下一个字符；若不为0，就表示之前已经插入过该字符，直接下移。最后该字符串插入结束，设置一个数组cnt[]标记以该字符串出现次数，cnt[p]表示以p结尾的字符串出现次数。
查询操作：类似插入操作进行判断，若出现某一次s[p][u]为0就此结束，意味着不存在该字符串，直到循环结束，存在该字符串，返回计数数组cnt[p]

#include <iostream>
using namespace std;
const int N=1e6+10;
 
char str[N];
int s[N][26],cnt[N],idx;
int n;
 
//插入一个字符串
void insert(char[] str){
    int p=0;//树的指针，用于下移，初始指向根节点 根节点不存储字符
    int u;//存储当前判断字符的整数值（即数组下标）
    for(int i=0;str[i];i++){//字符数组以'\0'结尾，即每次判断str[i]是否为空字符'\0';或#include <cstring> 使用函数strlen(str)得到字符数组长度
        u=str[i]-'a';//映射到0~25
        if(!s[p][u]) s[p][u]=++idx;//如果不存在，插入该字符
        p=s[p][u];//指针下移
    }
    cnt[p]++;//字符串计数
}
 
//查询字符串出现次数
int query(char[] str){
    int p=0,u;
    for(int i=0;str[i];i++){
        u=str[i]-'a';
        if(!s[p][u]) return 0;//某个字符不存在直接退出
        p=s[p][u];
    }
    return cnt[p];
}
 
int main() {
    cin>>n;
    while(n--)
    {
        char o;
        cin>>o>>str;
        if(o=='I') insert(str);
        else cout<<query(str)<<endl;
    }
    return 0;
}

Acwing 143. 最大异或对

**实现思路：**异或运算：x

暴力算法，两重for循环
Trie树：将每个整数转化为二进制数，每一位作为结点建立Trie树。从根节点开始记录每个数的二进制最高位。

求整数x的二进制数：x>>k &1
对于某个数，在集合中找到与之异或值最大的数：由异或的计算可知，从高位开始，每一位都与当前数不同，即异或值为1时，这个数越可能是与其异或最大的数。由此对于某个数，只要尽量选择Trie树自上而下每一步路径上结点与当前数二进制位不同的路径，最终走到叶子结点时就为与当前数异或值最大的数。
选择先插入再查询的方法（不先完全建立起Trie树，而是逐步插入查找然后建立，这就避免了循环中先异或了a[i]与a[j]，后面又异或了a[j]与a[i]；相比先查找再插入也避免了一开始的判空操作）
- 从第一个数据开始，Trie树为空，直接插入数据到Trie树；第二个数据，插入Trie树，再查找Trie树，找到与第二个数据异或值最大的数；第三个数，插入Trie树，再查找Trie树，找到与第三个数据异或值最大的数…以此类推，每次存下异或值，比较得到最大异或值，最后输出
本题数据最大为2^31，因此每个数的二进制位可以设置最高位从30开始，到0结束。
- 设置一个二维数组s[p][u]，表示下标为p的数的子结点u的值，若值为0表示当前要插入节点不存在，则插入该结点；若不为0则表示当前要插入的结点已存在，下移继续插入。p范围为所有数据总共的二进制位数，u范围为2，即两条路径（子结点）取值为1或0。设置整型变量idx，用来当做s[p][u]的值，每次插入后自增。设置p指针向下遍历Trie树，每次下移p=s[p][u]。
- 插入结点：循环得到每个数的二进制位，从最高位第30位开始插入Trie树
- 查找与当前数异或值最大的数：从最高位开始判断选择路径，看与当前二进制位不同的是否有路径，即s[p][!u]是否为0，若不为0则有不同的二进制位路径，选择这个路径继续向下遍历；若为0，则表示只有相同的二进制位的路径可走，不得不选择这个路径继续遍历。
- 每次选择路径后，都要记录当前路径，用一个整型变量res，每次选择路径后(res*2)+u（或+!u），*2即左移1位因为自上而下是高位开始，再加上当前路径值。最终res即为与当前异或值最大的数。
- 最后比较每次异或值res，选出最大的值输出

#include <iostream>
#include <algorithm>
const int N=1e5+10,M=31*N;//每个数31位二进制位，共N个数
int n;
int a[N];
int s[M][2],idx;//s数组第二维就存两个
 
void insert(int x){
    int p=0;//结点指针
    for(int i=30;i>=0;i--){
     int u=x>>i & 1; //计算二进制位，从最高位开始
     if(!s[p][u]) s[p][u]=++idx;//当前位置子结点为空 可插入
     p=s[p][u];//指针后移 继续插入
    }
}
 
//寻找与x异或值最大的数
int query(int x){
    int p=0,res=0;
    for(int i=30;i>=30;i--){
        int u=x>>i & 1;
        if(s[p][!u]){//如果存在当前二进制位不同的路径
            p=s[p][!u];//指针下移
            res=res*2+!u;
        }else{//只有相同二进制位的路径 那不得不走
            p=s[p][u];
            res=res*2+u;
        }
    }
    return res;
}
 
 
int main()
{
    int res=0;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) 
    {
        //先插入
        insert(a[i]);
        //后查找
        int t=query(a[i]);
        res=max(res,a[i]^t);
    }
    cout<<res;
    return 0;
}

编程笔记

探索

Trie树（字典树）

4.Trie树（字典树）

Acwing 835.Trie字符串统计

Acwing 143. 最大异或对