Trie树

Trie树又叫前缀树，字典树。

作用高效的存储和查找字符串集合的数据结构

Trie储存字符串

对于树的存储，本题本质上是使用的二维数组来存储树，行代表当前第几个几点，列代表当前节点的几个儿子。

#include <iostream>
using namespace std;
const int N = 10e5+10;

int n;
char str[N]; // 用来存放一整个字符串 可能N个字符作为一个整体输入到str
int son[N][26]; // 用来存放这个Trie树
int cnt[N];     // 用来存放每个字符串出现了多少次
int idx;

void insert(char* str){  // 将一个字符串插入到Trie树中
    int p = 0;  // 父节点 0则意味着初始父节点
    for(int i = 0; str[i] != 0;i++){  // 遍历每个输入的字符串str
        int u = str[i] - 'a';         // 将每个字符映射到数字上  这样才能在son数组中使用u索引
        if(son[p][u] == 0){   // 如果遍历到这个字符串的最后一个字符0  使用一个新的idx创建一个节点
            son[p][u] = ++idx;
        }
        
        p = son[p][u]; // 更新新的p节点
        //cout << p << " ";
    }
    
    cnt[p] ++ ; // 遍历完每个节点的时候，记得标记加一  共查询使用
    
}

int query(char* str){   // 查询这个字符串中有几个当前字符串  每个字符串的个数其实都在一个数组中排好
    int p = 0;
    for(int i = 0; str[i] != 0;i++){
        int u = str[i] - 'a';
        if(son[p][u] == 0){   // 字符串访问快结束的时候
            return 0;     
        }
        p = son[p][u];
        //cout << p << " ";
    }
    
    return cnt[p];
}

int main(){
    
    cin >> n;
    char op[2]; // 这里开两个是因为以后要以%s输入的字符串，末尾会有一个\0
    while(n--){
        scanf("%s%s",&op,&str);
        if(op[0] == 'I'){
            //printf("------------");
            insert(str);
            
        }else if(op[0] == 'Q'){
            //printf("------------");
            printf("%d\n",query(str));
            // puts("");
        }
    }
    
    return 0;
}

Trie树的应用：最大异或对

// 暴力做法  只能过5/9，因此需要使用Trie树 O(n^{2}) n方是十的十次方所以就会超时
int res = 0;
for(int i = 0;i<n;i++){
  for(int j = 0;j<i;j++){
    res = max(res,q[i]^q[j]);
  }
}

#include <iostream>
// 时间复杂度O(31*n)~O(nlogn)
// c++一秒内可以算大概100万-1000万次 10^7-10^8 所以必须使用算法，不能暴力，暴力就会超时
using namespace std;
const int N = 10e5+10;
int a[N];
int son[N*31][2];   // 第一维度是N个数总共的二进制位，第二维是每个二进制的选择0or1
int n;
int idx;



void insert(int x){ // 自己手动构建一个二叉树
    int p = 0;
    for(int i = 30; i>=0; i--){
        int t = (x >> i & 1); // 把x的二进制表示的第i位抠出来 非0即1
        if(!son[p][t]) son[p][t] = ++idx;   // idx没有实际含义 记录的只是一些用过的节点序号12345678
        p = son[p][t];
        
    }
    // cout << p << endl;
}

int find(int x){ // 从上面构建的二叉树中找到自己需要的值 返回与x异或后 最大的数
    int p = 0,res = 0;
    for(int i = 30;i>=0;i--){
        int t = (x >> i & 1);
        if(son[p][!t]){
            p = son[p][!t];
            res = res *2 + 1;
        }else{
            p = son[p][t];
            res = res * 2 + 0;
        }
    }
    return res;
}
int main(){
    
    cin >> n;
    int res;
    for(int i = 0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i = 0;i<n;i++){
        insert(a[i]);
    }
    for(int i = 0;i<n;i++){
        res = max(res,find(a[i]));
    }
    cout << res;
    
    return 0;
}