字典树

原理

字典树的本质是什么？它其实是一棵存储了很多字符串的树，这棵树上的每一条边就是某个或某些字符串中的一个字符，而从根节点到某一个特定节点所经过的一条路径上的所有边组成的就是字典树所保存的某一个字符串。不难看出，字典树就是一颗多叉树，它利用字符串的前缀来建立了这棵树，从而达到了节省存储空间(所有相同前缀都只存储一次)，优化查询速度(查询单个单词是否存在的时间复杂度仅为该单词的长度)的目的。
Tire的每个节点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符c，就沿着当前节点的c这个字符指针，走向该指针指向的节点。

image

字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

应用于快速字符串插入，查找字符串，在大量字符串的查找中，体现其高效性。

代码

  • 封装

查找的时间复杂度只和树的深度有关，跟表中有多少个单词无关。
考虑到每一个节点可能不止延伸出一条边，不难想到用一个指针数组去保存当前节点可以到达的所有下一个节点。

const int MAXN = 26;
struct Trie{
    // 代表当前节点可以延伸出的边，数量可变
    Trie *Next[MAXN];
    // 标记当前节点是否是保存信息的结尾，也可以代表前缀个数
    int Flag;
    Trie(){
     // 初始化以该信息为前缀的信息个数
       Flag = 1;
     memset(Next, NULL, sizeof(Next));
    }
}*root;//挺像C++的类
  • 插入操作

将某一个信息插入字典树，其实就是将该信息的前缀信息保存到数对应节点中，并修改相应的值

void Insert(char *str){
   int len = strlen(str);
   Trie *p = root, *q;
    // 将str的每一个字符插入trie树
    for(int i=0; i<len; ++i){
        int id = str[i] - 'a';
        // 如果没有边，则新建一个trie节点，产生一条边，用以代表该字符
        if(p->Next[id] == NULL){
            q = new Trie();
            p->Next[id] = q;
            p = p->Next[id];
        }
        // 如果存在边，则沿着该边走
        else{
            p = p->Next[id];
            // 累加以该信息为前缀的信息个数
            ++(p->Flag);
        }
    }
}
  • 查询操作

查询某个信息是否存在于字典树中，实质上也是将该信息的前缀信息与字典树上存储的对应位置的信息进行匹配，然后判断标记的值即可。

int Query(char *str)
{
    int len = strlen(str);
    Trie *p = root;
    // 在trie树上顺序搜索str的每一个字符
    for(int i=0; i<len; ++i)
    {
        int id = str[i] - 'a';
        p = p->Next[id];
        // 若为空集，表示不存以此为前缀的信息
        if(p == NULL) return 0;
    }
    // 返回以该信息为前缀的信息个数
    return p->Flag;
}
  • 删除操作

递归释放字典树的每一个节点占用的空间即可。

void Free(Trie* T)
{
    if(T == NULL) return;
    // 释放trie树的每一个节点占用的内存
    for(int i=0; i<MAXN; ++i)
    {
        if(T->Next[i]) Free(T->Next[i]);
    }
    delete(T);
}

非指针做法

上面的一大串指针挺烦的....

//前缀统计实现
void ins(char *str){
    int len=strlen(str);
    int p=0;
    for(int i=0; i<len; i++){
        int ch=str[i]-'a';
        if(!tire[p][ch])
            tire[p][ch]=++ant;
        p=tire[p][ch];
    }
    cnt[p]++;
}
int srh(char *str){
    int ans=0;
    int len=strlen(str);
    int p=0;
    for(int i=0; i<len; i++){
        int ch=str[i]-'a';
        p=tire[p][ch];
        if(!p) return ans;
        ans+=cnt[p];
    }
    return ans;
}

练习

【数据结构】前缀统计

#include <bits/stdc++.h>
using namespace std;
int ant,n,m;
int tire[1000005][30],cnt[1000005];
void ins(char *str){
    int len=strlen(str);
    int p=0;
    for(int i=0; i<len; i++){
        int ch=str[i]-'a';
        if(!tire[p][ch])
            tire[p][ch]=++ant;
        p=tire[p][ch];
    }
    cnt[p]++;
}

int srh(char *str){
    int ans=0;
    int len=strlen(str);
    int p=0;
    for(int i=0; i<len; i++){
        int ch=str[i]-'a';
        p=tire[p][ch];
        if(!p) return ans;
        ans+=cnt[p];
    }
    return ans;
}

int main(){
    char s[1000000];
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%s",s);
        ins(s);
    }
    for(int i=0;i<m;i++)
    {
        scanf("%s",s);
        printf("%d\n",srh(s));
    }
    return 0;
}