Tre樹(字典樹)數(shù)據(jù)結(jié)構(gòu)詳解及模板

1、Tre樹（字典樹）數(shù)據(jù)結(jié)構(gòu)詳解（圖解）及模板了解這個(gè)數(shù)據(jù)結(jié)構(gòu)之前我們需要了解它能被用來(lái)做什么字典樹又稱單詞查找樹，Tire樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)減少查詢時(shí)間，最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希樹高。說(shuō)到底，字典樹就是用來(lái)查詢公共前綴的一個(gè)工具，延伸的話可以用來(lái)進(jìn)行串匹配，詞頻統(tǒng)計(jì)等，也是學(xué)AC自動(dòng)機(jī)的前置技能.所謂的字典樹，其實(shí)就是一個(gè)n叉樹我們對(duì)于每個(gè)字母，如果有公共前綴的，我們找到它的前綴，在后面不同的部分建立不同的子節(jié)點(diǎn)，

2、比如說(shuō)apple,appear,appxy三個(gè)不同的單詞,公共前綴為app，所以建樹如下：那么問(wèn)題來(lái)了，單詞的第一個(gè)字母不止A啊,應(yīng)該怎么辦？其實(shí)不難，學(xué)過(guò)二分圖的應(yīng)該能想出來(lái):設(shè)置一個(gè)超級(jí)源點(diǎn),我們?cè)诘谝粋€(gè)字母上面再設(shè)一個(gè)超級(jí)源點(diǎn)，這樣計(jì)算的時(shí)候不考慮他就行了，這樣第一層就可以和下面的子節(jié)點(diǎn)一樣建立了如圖所示(ps:此圖有誤,apply應(yīng)該為appxy)又是喜(sang)聞(xin)樂(lè)(bing)見(jiàn)(kuang)的代碼環(huán)節(jié)了個(gè)人由于ACM的原因，就只放數(shù)組實(shí)現(xiàn)的板子了，(反正懂原理了指針版的也挺簡(jiǎn)單的)由于數(shù)組不能動(dòng)態(tài)開(kāi)內(nèi)存，所以我們就得采用模擬的形式了，這里其實(shí)用了一點(diǎn)并查集的思想，各位客

3、官看下圖由于不能動(dòng)態(tài)分配內(nèi)存，同時(shí)字典樹又是比較耗費(fèi)空間的，所以我們的內(nèi)存分配盡可能大，開(kāi)一個(gè)二維數(shù)組iremaxn26然后tireij=k代表編號(hào)為i的節(jié)點(diǎn)的第j個(gè)孩子是編號(hào)為k的節(jié)點(diǎn)，這里的j通常指當(dāng)前位的字母A-Z然后關(guān)于編號(hào)，我們這里的存樹方式是:如果要生成新節(jié)點(diǎn),則編號(hào)+,否則編號(hào)不動(dòng)，所以如上圖,APPLY的對(duì)應(yīng)編號(hào)應(yīng)該為1,2,3,4,10,11;同時(shí)有：tire1A-A=2;tire2P-A=3;tire3P-A=10;tire10X-A=11;tire11Y-A=0;這樣,查找的時(shí)候利用并查集的思想不斷向下查找即可代碼如下/*頭文件可以忽略，只是一些常用的宏*/#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;建樹，每輸入一個(gè)單詞到s里面就調(diào)用_insert()就好void_insert()introot=0;fori(s.size()intnext=si-A;if(!Tirerootnext)Tirerootnext=+cnt;root=Tirerootnext;vroot=true;/這里用了一個(gè)標(biāo)記數(shù)組表示該點(diǎn)存在一個(gè)完整的單詞比如說(shuō)app和apple在最后一個(gè)p的位置就會(huì)被標(biāo)記true查找最長(zhǎng)公共前綴int_find(charbufs,intleng)introot=0;intcns=0;intnext;intres=0;