大一计算机的自学总结：前缀树（字典树、Trie树）

前言

前缀树，又称字典树，Trie树，是一种方便查找前缀信息的数据结构。

一、字典树的实现

1.类描述实现

#include <bits/stdc++.h>
using namespace std;class TrieNode
{
public:int pass=0;int end=0;TrieNode* nexts[26]={NULL};
};TrieNode* root=NULL;void insert(string word)
{TrieNode* node=root;node->pass++;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(node->nexts[path]==NULL){node->nexts[path]=new TrieNode();}node=node->nexts[path];node->pass++;}node->end++;
}int search(string word)
{TrieNode* node=root;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(node->nexts[path]==NULL){return 0;}node=node->nexts[path];}return node->end;
}int prefixNumber(string word)
{TrieNode* node=root;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(node->nexts[path]==NULL){return 0;}node=node->nexts[path];}return node->pass;
}void deleteWord(string word)
{if(search(word)>0){TrieNode* node=root;node->pass--;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(--node->nexts[path]->pass==0){node->nexts[path]=NULL;return ;}node=node->nexts[path];}node->end--;}
}int main()
{int m;cin>>m;root=new TrieNode();int op;string word;for(int i=0;i<m;i++){cin>>op;cin>>word;if(op==1){insert(word);}else if(op==2){deleteWord(word);}else if(op==3){cout<<(search(word)?"YES":"NO")<<endl;}else if(op==4){cout<<prefixNumber(word)<<endl;;}}
}

类描述的方法不推荐，重点是静态数组的实现方法。

2.静态数组实现

#include <bits/stdc++.h>
using namespace std;const int MAXN=150001;int trie[MAXN][26];
int treePass[MAXN]={0};
int treeEnd[MAXN]={0};
int cnt=1;//节点数void insert(string word)
{int cur=1;//节点编号treePass[cur]++;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){trie[cur][path]=++cnt;}cur=trie[cur][path];treePass[cur]++;}treeEnd[cur]++;
}int search(string word)
{int cur=1;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){return 0;}cur=trie[cur][path];}return treeEnd[cur];
}int prefixNumber(string word)
{int cur=1;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){return 0;}cur=trie[cur][path];}return treePass[cur];
}void deleteWord(string word)
{if(search(word)>0){int cur=1;treePass[cur]--;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(--treePass[ trie[cur][path] ]==0){trie[cur][path]=0;return ;}cur=trie[cur][path];}treeEnd[cur]--;}
}int main()
{int m;cin>>m;int op;string word;for(int i=0;i<m;i++){cin>>op;cin>>word;if(op==1){insert(word);}else if(op==2){deleteWord(word);}else if(op==3){cout<<(search(word)?"YES":"NO")<<endl;}else if(op==4){cout<<prefixNumber(word)<<endl;;}}
}

首先说明前缀树的原理，每个节点有pass和end两个信息，同时还有指向下一个节点的指针，节点与节点间的路径表示每个字符。所以，在树往下扎到底的过程中，沿途路径经过的字符就组成了一个字符串，其中pass的数值表示的是有几个字符串经过这个节点，end表示的是有几个字符串在这个节点结束。如“aab”和“abc”，二者首先经过公共节点“a”，然后出现分支“a”和“b”，所以第一个“a”的pass=2，第二个“a”的pass=1，最后一个“b”的end=1，第二个“b”的pass=1，end=0。

首先，设置全局变量，trie数组的一维表示节点的编号，二维表示每条分支去往的下个节点的编号。因为字母只有26个，所以准备26大小即可。之后，设置cnt为节点个数，从1开始。

函数部分，首先是insert函数，用来插入字符串。首先，cur表示当前节点的编号，开始为1，然后先让pass++。之后遍历word字符串，每次取出当前字符作为path，若trie[cur][path]==0，即没有后续节点，那就让其等于++cnt，建出节点。之后让cur跳到下个节点，然后pass++。最后，让end++。

之后是search函数，用来搜索字符串个数。基本思路和insert差不多，只是若trie等于0，即没有后续节点，说明不存在这个字符串，就返回0；否则最后返回end，即字符串数量。

重点是prefixNumber函数，用来搜索以某个字符串为前缀的串。思路和search差不多，主要区别是最后返回的是pass，即前缀数量。

最后是delete函数，用来删除字符串。思路就是反向的insert，每次让pass-1。注意此时的判断，若下一个节点的pass-1后等于0，即后续节点被删没了，直接让trie等于0后结束即可。

二、前缀树相关题目

1.接头密匙

class Solution {
public:#define MAXN 100int trie[MAXN][12];int pass[MAXN]={0};int end[MAXN]={0};int cnt=1;void insert(string word){int cur=1;pass[cur]++;for(int i=0,path;i<word.length();i++){path=word[i]=='-'?10:(word[i]=='#'?11:word[i]-'0');if(trie[cur][path]==0){trie[cur][path]=++cnt;}cur=trie[cur][path];pass[cur]++;}end[cur]++;}int prefixNumber(string word){int cur=1;for(int i=0,path;i<word.length();i++){path=word[i]=='-'?10:(word[i]=='#'?11:word[i]-'0');if(trie[cur][path]==0){return 0;}cur=trie[cur][path];}return pass[cur];}vector<int> countConsistentKeys(vector<vector<int> >& b, vector<vector<int> >& a){for(int i=0;i<a.size();i++){string cur;for(int j=1;j<a[i].size();j++){cur+=a[i][j]-a[i][j-1]+'0';cur+='#';}insert(cur);}vector<int>ans(b.size(),0);for(int i=0;i<b.size();i++){string word;for(int j=1;j<b[i].size();j++){word+=b[i][j]-b[i][j-1]+'0';word+='#';}ans[i]=prefixNumber(word);}        return ans;}
};

 这个题的重点是你得看出来这个情境是求前缀。（捂脸）

之后转化一下，把数组里每个数的差变成字符串，两个数之间用“#”间隔，加上负号，trie一共开12大小即可。之后先把a数组insert进去，再根据b数组一个一个找就行。

2.数组中两个数的最大异或值

class Solution {
public:#define MAXN 3000001int trie[MAXN][2];int cnt=1;int high;void insert(int n){int cur=1;for(int i=high,status;i>=0;i--){status=1&(n>>i);if(trie[cur][status]==0){trie[cur][status]=++cnt;}cur=trie[cur][status];}}int maxXOR(int n){int ans=0;int cur=1;for(int i=high,status,want;i>=0;i--){status=1&(n>>i);want=status^1;if(trie[cur][want]==0){want^=1;}ans|=(status^want)<<i;cur=trie[cur][want];}return ans;}int findMaximumXOR(vector<int>& nums) {int mx=INT_MIN;for(int i=0;i<nums.size();i++){mx=max(mx,nums[i]);}//找最大值的前导1的位置for(int i=31;i>=0;i--){if( (mx&(1<<i) )!=0){high=i;break;}}for(int i=0;i<nums.size();i++){insert(nums[i]);}int ans=0;for(int i=0;i<nums.size();i++){ans=max(ans,maxXOR(nums[i]));}return ans;}
};

 这个题就需要一点思考了。首先思考要达成异或和最大，最好的办法肯定是选二进制中第一个1最靠前的数，即最大的数。之后，要想异或和最大，理想情况就是找每一位都与最大的数不同的数，这样异或起来每一位就都是1了。

所以，首先把最大值抓出来，接着为了加速，可以把最大值的前导1的数位取出来，这样后续从这个位置开始找即可，不需要从31位开始。再把每个数的二进制形式insert进去，由于只有0和1两种状态，所以trie的大小为2即可。

重点就是maxXOR函数，首先每次让status为n第i位上的状态。注意，这里由于trie只有0和1两条分支，所以选择让n>>i的方法。然后，最优选择肯定是找status不同的状态，所以want=status^1，若没有找到，就再^1回到原状态。最后把这一位的异或结果或进ans里即可。

这个题说实话还是有点难度的。

3.单词搜索 II

class Solution {
public:#define MAXN 10001int trie[MAXN][26];int pass[MAXN]={0};string end[MAXN];int cnt=1;void insert(string word){int cur=1;pass[cur]++;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){trie[cur][path]=++cnt;}cur=trie[cur][path];pass[cur]++;}end[cur]=word;}int prefix(string word){int cur=1;for(int i=0,path;i<word.length();i++){path=word[i]-'a';if(trie[cur][path]==0){return 0;}cur=trie[cur][path];}return pass[cur];}//返回值为找到的字符串个数int dfs(vector<vector<char>>&board,int i,int j,int t,vector<string>&ans){if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]==0){return 0;}int tmp=board[i][j];int path=tmp-'a';t=trie[t][path];if(pass[t]==0||t==0)//找过了或没有{return 0;}int num=0;if(end[t]!="")//找到一个{num++;ans.push_back(end[t]);end[t]="";}board[i][j]=0;num+=dfs(board,i+1,j,t,ans);num+=dfs(board,i-1,j,t,ans);num+=dfs(board,i,j+1,t,ans);num+=dfs(board,i,j-1,t,ans);pass[t]-=num;//找完一个就删除board[i][j]=tmp;return num;}vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {vector<string>ans;for(int i=0;i<words.size();i++){insert(words[i]);}for(int i=0;i<board.size();i++){for(int j=0;j<board[i].size();j++){dfs(board,i,j,1,ans);}}return ans;}
};

 这个题就更是群贤毕至，不仅有前缀树，还有带路径的递归和还原现场。

前缀树在这个题的作用就是剪枝，而且有三次剪枝。首先，通过前缀树，可以让每次递归去往的都是有效的格子。其次，这里让end数组直接存放整个字符串，可以方便递归结束时直接收集结果。最后，每次在找完一个字符串后就把节点删除，也可以减少不必要的搜索。

重点就是这个dfs函数，首先若越界了或走到走过的格子就返回0。之后取当前格子上的字符和path，t表示前缀树当前节点的编号，所以让t去下一个节点，若下一个节点找过了或者没有就返回0。然后若end有东西，说明找到了，就记录答案之后删除。接着分别去四个方向递归，注意这里在回来时不仅要把格子还原，还有让pass减去找到的数量，即删去找过的字符串，所以要让dfs函数带上返回值，表示找到的字符串个数。

有一说一这个题确实难。

总结

前缀树还是很强的，用好了能很大程度优化算法。

END