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