大一计算机的自学总结：前缀树（字典树、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 100 int 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 3000001 int 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 10001 int 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