Tire树（字典树）数据结构详解（图解）及模板

了解这个数据结构之前我们需要了解它能被用来做什么

字典树又称单词查找树，Tire树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

说到底,字典树就是用来查询公共前缀的一个工具,延伸的话可以用来进行串匹配,词频统计等,也是学AC自动机的前置技能. 所谓的字典树,其实就是一个n叉树

我们对于每个字母,如果有公共前缀的,我们找到它的前缀,在后面不同的部分建立不同的子节点,比如说apple,appear,appxy 三个不同的单词,公共前缀为app,所以建树如下: 如果下面有一个单词为apzl的话,建树如下也就是只注意前缀相同的部分,后面即使有一样的字母也重新建立子节点

那么问题来了,单词的第一个字母不止A啊,应该怎么办? 其实不难,学过二分图的应该能想出来:设置一个超级源点,我们在第一个字母上面再设一个超级源点,这样计算的时候不考虑他就行了,这样第一层就可以和下面的子节点一样建立了如图所示(ps:此图有误,apply应该为appxy)

又是喜(sang)闻(xin)乐(bing)见(kuang)的代码环节了个人由于ACM的原因,就只放数组实现的板子了,(反正懂原理了指针版的也挺简单的) 由于数组不能动态开内存,所以我们就得采用模拟的形式了,这里其实用了一点并查集的思想,各位客官看下图由于不能动态分配内存,同时字典树又是比较耗费空间的,所以我们的内存分配尽可能大,开一个二维数组tire[maxn][26],然后tire[i][j] = k 代表编号为i的节点的第j个孩子是编号为k的节点,这里的j通常指当前位的字母A-Z然后关于编号,我们这里的存树方式是:如果要生成新节点,则编号++,否则编号不动,所以如上图,APPLY的对应编号应该为1,2,3,4,10,11; 同时有:

tire[1]['A'-'A'] = 2;
tire[2]['P'-'A'] = 3;
tire[3]['P'-'A']  = 10;
tire[10]['X'-'A'] = 11;
tire[11]['Y'-'A'] = 0;

这样,查找的时候利用并查集的思想不断向下查找即可代码如下

/*头文件可以忽略,只是一些常用的宏*/
#include <map>
#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <fstream>
#include <iostream>
#include <sstream>
#include <algorithm>
#define _mem(a,b) memset(a,0,(b+3)<<2)
#define fori(a) for(int i=0;i<a;i++)
#define forj(a) for(int j=0;j<a;j++)
#define ifor(a) for(int i=1;i<=a;i++)
#define jfor(a) for(int j=1;j<=a;j++)
#define mem(a,b) memset(a,b,sizeof(a))
#define IN freopen("in.txt","r",stdin)
#define OUT freopen("out.txt","w",stdout)
#define IO do{\
    ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);}while(0)
#define mp(a,b) make_pair(a,b);
using namespace std;
typedef long long ll;
const int maxn =  1e5;
const int INF = 0x3f3f3f3f;
const int inf = 0x3f;
const double EPS = 1e-7;
const double Pi = acos(-1);
const int MOD = 1e9+7;
int Tire[maxn][26];
char str[2000005];
bool v[maxn];
string s;
int cnt = 1;
//建树,每输入一个单词到s里面就调用_insert()就好
void _insert(){
    int root = 0;
    fori(s.size()){
        int next = s[i] - 'A';
        if(!Tire[root][next])
            Tire[root][next] = ++cnt;
        root = Tire[root][next];
    }
    v[root] = true;//这里用了一个标记数组表示该点存在一个完整的单词,比如说`app`和`apple`
                            //在最后一个`p`的位置就会被标记true
}

//查找最长公共前缀
int _find(char bufs[],int leng){
    int root = 0;
    int cns = 0;
    int next;
    int res = 0;
    fori(leng){
        next = bufs[i] - 'A';
        if(Tire[root][next] == 0)
            break;
        root = Tire[root][next];
        cns++;
        if(v[root])
            res = cns;
    }
    return res;
}