一、什么是字典樹？
Trie 樹，也叫“字典樹”。顧名思義，它是一個(gè)樹形結(jié)構(gòu)。它是一種專門處理字符串匹配的數(shù)據(jù)結(jié)構(gòu)，用來解決在一組字符串集合中快速查找某個(gè)字符串的問題。
Trie 樹的本質(zhì)，就是利用字符串之間的公共前綴，將重復(fù)的前綴合并在一起。
舉個(gè)例子，現(xiàn)在我們要存儲一些字符串。
1?? 只要前綴相同的我們就不需要兩個(gè)節(jié)點(diǎn)來存儲，但是要注意ABCD和ATCD這兩個(gè)字符串從B和T就分開了，所以后面的CD就不會存到一起。
2?? 有可能一個(gè)字符串是另一個(gè)字符串的前綴。所以我們需要一個(gè)變量來標(biāo)志一個(gè)字符串的結(jié)尾，也能標(biāo)識有多少個(gè)這個(gè)字符串。
二、字典樹的相關(guān)操作
2.1 插入
const int N = 1e6 + 10;
int son[N][26];// 記錄下一個(gè)節(jié)點(diǎn)在第幾層
int cnt[N];// 標(biāo)識字符串結(jié)尾
int idx;// 記錄下一個(gè)要存節(jié)點(diǎn)的層數(shù)
son數(shù)組的作用是記錄儲存子節(jié)點(diǎn)的位置，而26則代表了26個(gè)字符，類似于26叉樹。
而cnt的作用就是標(biāo)志一個(gè)字符串的結(jié)尾，順便記錄有多少個(gè)該字符串。idx表示當(dāng)前要插入的節(jié)點(diǎn)（新建節(jié)點(diǎn)）。
void insert(const string& s)
{
int p = 0;// 從根開始找，如果沒有說明需要新的根
for(int i = 0; i < s.size(); i++)
{
int u = s[i] - 'a';
if(!son[p][u])// 沒有就創(chuàng)建
{
son[p][u] = ++idx;
}
p = son[p][u];
}
cnt[p]++;
}
用一張圖理解一下，假設(shè)現(xiàn)在要插入"ac"和"bc"：
這也說明了不管是插入還是查找，第一個(gè)字符都是在第0層，所以初始化p = 0。
2.2 查找
查找的操作就類似于插入，如果不存在直接返回0即可。
int search(const string& s)
{
int p = 0;
for(int i = 0; i < s.size(); i++)
{
int u = s[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
2.3 例題：Trie字符串統(tǒng)計(jì)
題目鏈接
題目描述
維護(hù)一個(gè)字符串集合，支持兩種操作：
I x向集合中插入一個(gè)字符串 x；Q x詢問一個(gè)字符串在集合中出現(xiàn)了多少次。
共有 N個(gè)操作，所有輸入的字符串總長度不超過 1e5，字符串僅包含小寫英文字母。
輸入格式
第一行包含整數(shù) N，表示操作數(shù)。接下來 N行，每行包含一個(gè)操作指令，指令為 I x 或 Q x 中的一種。
輸出格式
對于每個(gè)詢問指令 Q x，都要輸出一個(gè)整數(shù)作為結(jié)果，表示 x在集合中出現(xiàn)的次數(shù)。
每個(gè)結(jié)果占一行。
數(shù)據(jù)范圍
1≤N≤2?1e4
輸入樣例：
5
I abc
Q abc
Q ab
I ab
Q ab
輸出樣例：
1
0
1
#include <iostream>
#include <string>
using namespace std;
const int N = 1e6 + 10;
int son[N][26];// 記錄下一個(gè)節(jié)點(diǎn)在第幾層
int cnt[N];// 標(biāo)識字符串結(jié)尾
int idx;// 記錄下一個(gè)要存節(jié)點(diǎn)的層數(shù)
void insert(const string& s)
{
int p = 0;// 從根開始找，如果沒有說明需要新的根
for(int i = 0; i < s.size(); i++)
{
int u = s[i] - 'a';
if(!son[p][u])// 沒有就創(chuàng)建
{
son[p][u] = ++idx;
}
p = son[p][u];
}
cnt[p]++;
}
int search(const string& s)
{
int p = 0;
for(int i = 0; i < s.size(); i++)
{
int u = s[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
cin >> n;
string s1, s2;
while(n--)
{
cin >> s1 >> s2;
if(s1 == "I")
{
insert(s2);
}
else
{
cout << search(s2) << endl;
}
}
return 0;
}
三、應(yīng)用：最大異或?qū)?/h2>
題目鏈接
題目描述
在給定的 N個(gè)整數(shù) A1，A2……AN中選出兩個(gè)進(jìn)行 xor（異或）運(yùn)算，得到的結(jié)果最大是多少？
輸入格式
第一行輸入一個(gè)整數(shù) N。第二行輸入 N個(gè)整數(shù) A1～AN。
輸出格式
輸出一個(gè)整數(shù)表示答案。
數(shù)據(jù)范圍
1≤N≤105, 0≤Ai<231
輸入樣例：
3
1 2 3
輸出樣例：
3
思路分析：
首先我們要知道什么時(shí)候兩個(gè)數(shù)字異或值最大？
答案是當(dāng)兩個(gè)數(shù)的二進(jìn)制位每一位都不相同的時(shí)候最大。
我們知道一個(gè)數(shù)有32個(gè)比特位，最高位不用管（符號位），所以我們就要看第0 ~ 30位。
因?yàn)楸忍匚挥性有裕ㄖ挥袃蓱B(tài)），我們可以分兩種情況：一種是比特位相同，一種是不同，而為了保證最大，從最高位開始，如果兩種情況的話每次盡量往不同的方向走，只有一種情況就沒有辦法。我們邊查找邊統(tǒng)計(jì)總和，走到最后即可得到異或的值，所以我們邊查找就能邊統(tǒng)計(jì)最大的異或?qū)?/strong>。
#include <iostream>
using namespace std;
const int N = (1e5 + 10) * 31;
int son[N][2], idx;
void insert(int x)
{
int p = 0;
for(int i = 30; i >= 0; i--)
{
int u = (x >> i) & 1;
if(!son[p][u]) son[p][u] = ++idx;
p = son[p][u];
}
}
int search(int x)
{
int p = 0, res = 0;
for(int i = 30; i >= 0; i--)
{
int u = (x >> i) & 1;
// 盡量往不在的那一邊走
// 另一邊存在就異或
if(son[p][!u])
{
res = res * 2 + 1;
p = son[p][!u];
}
else
{
res = res * 2;
p = son[p][u];
}
}
return res;
}
int main()
{
int n;
cin >> n;
int res = 0;
while(n--)
{
int x;
cin >> x;
insert(x);
int tmp = search(x);
res = max(res, tmp);
}
cout << res << endl;
return 0;
}
四、總結(jié)
我們上面的題目也可以使用哈希來解決，但是trie樹在某些方面它的用途更大，比如說對于某一個(gè)單詞，我們要詢問它的前綴是否出現(xiàn)過。這樣hash就不好搞了，而用trie還是很簡單。
上面我們使用數(shù)組模擬出來的，當(dāng)然也可以用鏈?zhǔn)浇Y(jié)構(gòu)：文章來源：http://www.zghlxwxcb.cn/news/detail-412377.html
#define MAX 26
typedef struct trie {
struct trie* node[MAX];
int v;
} Trie;
用一道leetcode的例題舉例：
題目鏈接
代碼：文章來源地址http://www.zghlxwxcb.cn/news/detail-412377.html
class Trie {
public:
vector<Trie*> son;
bool flag;
Trie* searchend(string s)
{
Trie* node = this;
for(int i = 0; i < s.size(); i++)
{
int u = s[i] - 'a';
if(!node->son[u])
{
return nullptr;
}
node = node->son[u];
}
return node;
}
Trie()
: son(26)
, flag(false)
{}
void insert(string word) {
Trie* node = this;
for(int i = 0; i < word.size(); i++)
{
int u = word[i] - 'a';
if(!node->son[u])
{
node->son[u] = new Trie;
}
node = node->son[u];
}
node->flag = true;
}
bool search(string word) {
Trie* node = searchend(word);
if(node && node->flag)
{
return true;
}
return false;
}
bool startsWith(string prefix) {
Trie* node = searchend(prefix);
if(node)
{
return true;
}
return false;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】深刨Trie樹（字典樹）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
