Tre树(字典树)数据结构详解及模板

1、Tre树（字典树）数据结构详解（图解）及模板了解这个数据结构之前我们需要了解它能被用来做什么字典树又称单词查找树，Tire树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。说到底，字典树就是用来查询公共前缀的一个工具，延伸的话可以用来进行串匹配，词频统计等，也是学AC自动机的前置技能.所谓的字典树，其实就是一个n叉树我们对于每个字母，如果有公共前缀的，我们找到它的前缀，在后面不同的部分建立不同的子节点，

2、比如说apple,appear,appxy三个不同的单词,公共前缀为app，所以建树如下：那么问题来了，单词的第一个字母不止A啊,应该怎么办？其实不难，学过二分图的应该能想出来:设置一个超级源点,我们在第一个字母上面再设一个超级源点，这样计算的时候不考虑他就行了，这样第一层就可以和下面的子节点一样建立了如图所示(ps:此图有误,apply应该为appxy)又是喜(sang)闻(xin)乐(bing)见(kuang)的代码环节了个人由于ACM的原因，就只放数组实现的板子了，(反正懂原理了指针版的也挺简单的)由于数组不能动态开内存，所以我们就得采用模拟的形式了，这里其实用了一点并查集的思想，各位客

3、官看下图由于不能动态分配内存，同时字典树又是比较耗费空间的，所以我们的内存分配尽可能大，开一个二维数组iremaxn26然后tireij=k代表编号为i的节点的第j个孩子是编号为k的节点，这里的j通常指当前位的字母A-Z然后关于编号，我们这里的存树方式是:如果要生成新节点,则编号+,否则编号不动，所以如上图,APPLY的对应编号应该为1,2,3,4,10,11;同时有：tire1A-A=2;tire2P-A=3;tire3P-A=10;tire10X-A=11;tire11Y-A=0;这样,查找的时候利用并查集的思想不断向下查找即可代码如下/*头文件可以忽略，只是一些常用的宏*/#includ

4、e#include#include#include#include#include#include#include#include#include#include#define_mem(a,b)memset(a,0,(b+3)2)#definefori(a)for(inti=0;ia;i+)#defineforj(a)for(intj=0;ja;j+)#defineifor(a)for(inti=1;i=a;i+)#defineifor(a)for(inti=1;i=a;i+)#definejfor(a)for(intj=1;j=a;j+)#definemem(a,b)memset(a,b,s

5、izeof(a)#defineINfreopen(in.txt,r,stdin)#defineOUTfreopen(out.txt,w,stdout)#defineIOdoios:sync_with_stdio(false);cin.tie(0);cout.tie(0);while(0)#definemp(a,b)make_pair(a,b);usingnamespacestd;typedeflonglongll;constintmaxn=1e5;constintINF=0 x3f3f3f3f;constintinf=0 x3f;constdoubleEPS=1e-7;constdoubleP

6、i=acos(-1);constintMOD=1e9+7;intTiremaxn26;charstr2000005;boolvmaxn;strings;intcnt=1;建树，每输入一个单词到s里面就调用_insert()就好void_insert()introot=0;fori(s.size()intnext=si-A;if(!Tirerootnext)Tirerootnext=+cnt;root=Tirerootnext;vroot=true;/这里用了一个标记数组表示该点存在一个完整的单词比如说app和apple在最后一个p的位置就会被标记true查找最长公共前缀int_find(charbufs,intleng)introot=0;intcns=0;intnext;intres=0;