定義
（本篇僅代表本人自己的觀點，請路過大佬勿噴）
字典樹，又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種，適用于實作字串快速檢索的多叉樹，典型應用是用于統計，排序和保存大量的字串(但不僅限于字串)，所以經常被搜索引擎系統用于文本詞頻統計，它的優點是:利用字串的公共前綴來減少查詢時間，最大限度地減少無謂的字串比較，查詢效率比哈希樹高
那么她是如何實作的呢？Tire的每個節點都擁有若干個字符指標，若在插入或檢索字串時掃描到一個字符c，就沿著當前節點的c字符指標，走向該指標指向的節點，以此類推......
這樣講感覺太籠統了，有點難理解，個人覺得可以理解成翻字典，找到一個英文字母以后，繼續找下一個，這是同樣的道理，接下來讓我們看看字典樹的基本操作程序
基本操作程序
其實就兩個操作--插入（insert）和查詢（find）也可以稱之為檢索，（差不多啦，這個沒必要糾結，喜歡什么用什么）
插入（insert）
字典樹也是一棵樹，雖然簡單，但人家也是有尊嚴的！想要用她，就得建立她，（咳......這個Ta用女字旁純屬個人喜好，更生動嘛！）那該如何建立呢？就是用這個插入操作，比如有很多的單詞，那就把這些單詞的每個字母都插進去，等你把單詞插完了，她就建好了！舉個例子，比如下面這棵樹-->
這棵樹就包括了（cap,cat,csp,co,code）這么幾個單詞，這樣是不是感覺直觀多了！
那著上面的數字代表什么？其實是編號，每個結點的編號，因為在插入程序中，如果當前要插入的字符在樹上沒有，那么就要將該字符作為一個新的節點，那肯定不能亂了順序，在這個文明社會得知道先來后到吧（扯歪了），所以就需要一個全域變數tot來記錄節點編號，那如果已經有當前要插入的字符，比如說第二個單詞（cat)他的前綴“ca”在上一個單詞（cap)中已經被插入了，那既然都有了，那還插什么？直接就跳到該字符所在的節點就行了！
那這樣看來的話，稱這顆樹為前綴樹似乎更好理解，因為兩個單詞如果有重合的前綴，那么他們就共用，直到前綴不一樣或者是一個單詞就是另一個單詞的前綴，才會出現不同，那很多的單詞也同樣的道理，也可以通過相同的前綴放到一棵樹上，有沒有感徑訓然開朗？
但是，又有一個問題，如果沒有相同的前綴呢，那咋整啊？那要搞一個虛擬節點唄！所以字典數會有一個固定的根節點--root，它可以是不會被用到的任意節點編號，0或1，看個人習慣吧，我習慣用0
知道思路和會實作代碼是兩碼事，這里我直接貼上我習慣寫法的代碼
1 const int N=1000005; 2 int t[N][26],root=0,tot=2;//t陣列用于存盤字典樹 t[4][2]表示，4號節點下面2這個兒子 3 void insert(string s)//傳入一個單詞 4 { 5 int p=root;//p是指當前在樹上的位置，一開始固定在根上 6 for(int i=0;i<s.size();i++)//將單詞掃描一邊 7 { 8 int id=s[i]-'a';//將每個字母單獨拿出來 9 if(t[p][id]==0) t[p][id]=tot++;//當前位置如果沒有id這個兒子，就新建節點 10 p=t[p][id];//跳到下一個節點 11 } 12 }
好了，插入操作講完了，已經可以進行簡單的運用了，如果想先插入的鞏固知識的話，可以做一下簡單的題目實戰一下！！
P1481 魔族密碼 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
這個題目就是插入的一道很裸的題目了，可以自行AC，沒有任何問題！
接下來還有一個重要的操作
查詢（find）
真個操作可以用來查找一個單詞是否在這棵樹上，也能用來查前綴（哎呀，其實你想想查什么都行，但查你女朋友戶口本應該不行），在建好樹的基礎上可以進行這個操作，下面是查有沒有這個單詞的代碼
1 const int N=1e6+5; 2 int root=0,t[N][26],flag[N]; 3 int find(sting s) 4 { 5 int p=root; 6 for(int i=0;i<s.size();i++) 7 { 8 int id=s[i]-'a'; 9 if(t[p][id]==0) return 0;//一旦找不到，直接回傳 10 p=t[p][id]; 11 } 12 if(flag[p]) return 1;//這里必須判斷一下，flag[4]指的是在4這個節點有單詞結尾，不判斷的話可能會因為找到其他單詞的前綴而出錯 13 }
其實說實話，我感覺查詢和插入跟雙胞胎一樣的，都是差不多的，沒變多少，查詢也可以根據題意調整
下面看一道例題：P2580 于是他錯誤的點名開始了 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
這道題是一道很裸很裸的例題，就是 有 手 就 行！！
我貼一下我的AC代碼，僅供參考
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1000005; 4 int t[N][26],root=0,tot=2; 5 bool vis[N],f[N]; 6 void insert(string s) 7 { 8 int p=root; 9 for(int i=0;i<s.size();i++) 10 { 11 int id=s[i]-'a'; 12 if(t[p][id]==0) t[p][id]=tot++; 13 p=t[p][id]; 14 } 15 f[p]=1; 16 } 17 void query(string s) 18 { 19 int p=root; 20 for(int i=0;i<s.size();i++) 21 { 22 int id=s[i]-'a'; 23 if(!t[p][id]) 24 { 25 cout<<"WRONG"<<endl; 26 return ; 27 } 28 p=t[p][id]; 29 } 30 if(f[p]==0) 31 { 32 cout<<"WRONG"<<endl; 33 return ; 34 } 35 if(vis[p]==1) 36 { 37 cout<<"REPEAT"<<endl; 38 return ; 39 } 40 else 41 { 42 cout<<"OK"<<endl; 43 vis[p]=1; 44 } 45 } 46 int main() 47 { 48 int n,m; 49 string s; 50 cin>>n; 51 for(int i=1;i<=n;i++) cin>>s,insert(s); 52 cin>>m; 53 for(int i=1;i<=m;i++) cin>>s,query(s); 54 return 0; 55 }
一開始都說了，字典樹不僅可以處理字串，同樣可以處理其它資料，比如下面的
字串的其他應用
這次直接用一道例題方便大家理解
題意大家應該很清楚吧，就是在一棵樹上找兩個點，使他們的異或路徑最大
分析：
因為題目中并沒有給定根節點，所以我們很容易就能想到，指定節點1為根節點，使其變成有根樹，建立這棵樹，求第i個節點到根節點的異或路徑si（遞回求解），而節點i到節點j的異或路徑就是si異或sj，這是兩個節點分別到根節點的路徑，因為路徑是唯一的，在他們lca之上的部分是重疊的，異或兩遍會歸零，因此，對于每個si，找到一個sj使得路徑最大即可求解，所以就能AC了（AC個屁，那和字典樹有什么關系？）
是的，所以還有個問題，如果兩兩列舉的話，效率很低，所以今天的主角登場！！
先看下面的圖片你就知道了
我們可以用字典樹來維護這些數字，把這些數字看成一個31位的字串，并建立字典樹，每個葉節點的深度都是相同的，建完以后（如上圖），對于每個到根異或路徑值，可以用貪心的策略，從字典樹的根開始，每一位使用貪心策略，如果字典樹當前只有一個節點，直接往下走，如果有兩個的話，選擇和這一位不同的數構成1，當列舉完所有的位數，也就到了字典樹的葉子節點了，正好找到了符合要求的sj
有沒有感覺這個運用很妙？
下面是我的AC代碼：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1e5+10; 4 struct node 5 { 6 int v,w; 7 }; 8 vector<node>G[N]; 9 int n,tot,t[N*31][2],s[N],root=0; 10 void insert(int x) 11 { 12 int u=root; 13 for(int i=30;i>=0;i--) 14 { 15 int op=bool(x&(1<<i));//這一位是0還是1 16 if(!t[u][op]) t[u][op]=++tot; 17 u=t[u][op]; 18 } 19 } 20 void dfs(int u,int fa) 21 { 22 for(int i=0;i<G[u].size();i++) 23 { 24 int v=G[u][i].v,w=G[u][i].w; 25 if(v==fa) continue; 26 s[v]=s[u]^w;//和父節點的異或路徑再異或一次 27 dfs(v,u); 28 } 29 } 30 int find(int x) 31 { 32 int ans=0,u=root; 33 for(int i=30;i>=0;i--) 34 { 35 int op=bool(x&(1<<i)); 36 if(t[u][!op]) //優先走使答案變成1的方向 37 { 38 ans+=(1<<i);//累加答案 39 u=t[u][!op]; 40 } 41 else u=t[u][op]; 42 } 43 return ans; 44 } 45 int main() 46 { 47 cin>>n; 48 for(int i=1;i<n;i++) 49 { 50 int x,y,w; 51 cin>>x>>y>>w; 52 G[x].push_back((node){y,w}); 53 G[y].push_back((node){x,w}); 54 } 55 dfs(1,-1);//根據讀入建立樹，計算每個到根節點的異或路徑 56 for(int i=1;i<=n;i++) insert(s[i]); 57 int ans=0; 58 for(int i=1;i<=n;i++) ans=max(ans,find(s[i]));//對于每個si，都找的到對應的sj 59 cout<<ans;//輸出答案，完美收官，撒花！ 60 return 0; 61 }
這道題的鏈接：P4551 最長異或路徑 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
習題：題目串列 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
剩下的關于字典樹的內容，有興趣的讀者可以自行查閱學習！
謝謝大家閱讀，碼字不易，隨手點贊，謝謝！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502465.html
標籤：其他