叫前綴樹更容易理解
字典樹的樣子

image.png

Trie又被稱為前綴樹、字典樹，所以當(dāng)然是一棵樹。上面這棵Trie樹包含的字符串集合是{in, inn, int, tea, ten, to}。每個(gè)節(jié)點(diǎn)的編號(hào)是我們?yōu)榱嗣枋龇奖慵由先サ?。樹中的每一條邊上都標(biāo)識(shí)有一個(gè)字符。這些字符可以是任意一個(gè)字符集中的字符。比如對(duì)于都是小寫字母的字符串，字符集就是’a’-‘z’；對(duì)于都是數(shù)字的字符串，字符集就是’0’-‘9’；對(duì)于二進(jìn)制字符串，字符集就是0和1。

比如上圖中3號(hào)節(jié)點(diǎn)對(duì)應(yīng)的路徑0123上的字符串是inn，8號(hào)節(jié)點(diǎn)對(duì)應(yīng)的路徑0568上的字符串是ten。終結(jié)點(diǎn)與集合中的字符串是一一對(duì)應(yīng)的。

原理
下面我們來講一下對(duì)于給定的字符串集合{W1, W2, W3, … WN}如何創(chuàng)建對(duì)應(yīng)的Trie樹。其實(shí)上Trie樹的創(chuàng)建是從只有根節(jié)點(diǎn)開始，通過依次將W1, W2, W3, … WN插入Trie中實(shí)現(xiàn)的。所以關(guān)鍵就是之前提到的Trie的插入操作。
具體來說，Trie一般支持兩個(gè)操作：

1. Trie.insert(W)：第一個(gè)操作是插入操作，就是將一個(gè)字符串W加入到集合中。
2. Trie.search(S)：第二個(gè)操作是查詢操作，就是查詢一個(gè)字符串S是不是在集合中。

假設(shè)我們要插入字符串”in”。我們一開始位于根，也就是0號(hào)節(jié)點(diǎn)，我們用P=0表示。我們先看P是不是有一條標(biāo)識(shí)著i的連向子節(jié)點(diǎn)的邊。沒有這條邊，于是我們就新建一個(gè)節(jié)點(diǎn)，也就是1號(hào)節(jié)點(diǎn)，然后把1號(hào)節(jié)點(diǎn)設(shè)置為P也就是0號(hào)節(jié)點(diǎn)的子節(jié)點(diǎn)，并且將邊標(biāo)識(shí)為i。最后我們移動(dòng)到1號(hào)節(jié)點(diǎn)，也就是令P=1。

這樣我們就把”in”的i字符插入到Trie中了。然后我們?cè)俨迦胱址鹡，也是先找P也就是1號(hào)節(jié)點(diǎn)有沒有標(biāo)記為n的邊。還是沒有，于是再新建一個(gè)節(jié)點(diǎn)2，設(shè)置為P也就是1號(hào)節(jié)點(diǎn)的子節(jié)點(diǎn)，并且把邊標(biāo)識(shí)為n。最后再移動(dòng)到P=2。這樣我們就把n也插入了。由于n是”in”的最后一個(gè)字符，所以我們還需要將P=2這個(gè)節(jié)點(diǎn)標(biāo)記為終結(jié)點(diǎn)。

image.png

現(xiàn)在我們?cè)俨迦胱址眎nn”。過程也是一樣的，從P=0開始找標(biāo)識(shí)為i的邊，這次找到1號(hào)節(jié)點(diǎn)。于是我們就不用創(chuàng)建新節(jié)點(diǎn)了，直接移動(dòng)到1號(hào)節(jié)點(diǎn)，也就是令P=1。再插入字符n，也是有2號(hào)節(jié)點(diǎn)存在，所以移動(dòng)到2號(hào)節(jié)點(diǎn)，P=2。最后再插入字符n這時(shí)P沒有標(biāo)識(shí)為n的邊了，所以新建3號(hào)節(jié)點(diǎn)作為2號(hào)節(jié)點(diǎn)的子節(jié)點(diǎn)，邊標(biāo)識(shí)為n，同時(shí)將3號(hào)節(jié)點(diǎn)標(biāo)記為終結(jié)點(diǎn)：

image.png

將后面的字符串int tea ten to都插入之后，就得到了我們一開始給出的Trie：

下面我們?cè)僦v一下如何查詢Trie樹中是不是包含字符串S，也就是之前提到的查找操作。查找其實(shí)比較簡(jiǎn)單。我們只要從根節(jié)點(diǎn)開始，沿著標(biāo)識(shí)著S[1] -> S[2] -> S[3] … -> S[S.len]的邊移動(dòng)，如果最后成功到達(dá)一個(gè)終結(jié)點(diǎn)，就說明S在Trie樹中；如果最后無路可走，或者到達(dá)一個(gè)不是終結(jié)點(diǎn)的節(jié)點(diǎn)，就說明S不在Trie樹中。

image.png

如果是查找”te”，就會(huì)從0開始經(jīng)過5最后到達(dá)6。但是6不是終結(jié)點(diǎn)，所以te沒在Trie樹中。如果查找的是”too”，就會(huì)從0開始經(jīng)過5和9，然后發(fā)現(xiàn)之后無路可走：9號(hào)節(jié)點(diǎn)沒有標(biāo)記為o的邊連出去。所以too也不在Trie中。

代碼實(shí)現(xiàn)
數(shù)組方式實(shí)現(xiàn)
要寫代碼實(shí)現(xiàn)一個(gè)Trie首先就要確定如何存儲(chǔ)一個(gè)Trie結(jié)構(gòu)。這里用一個(gè)二維數(shù)組來存儲(chǔ)：

int trie[MAX_NODE][CHARSET];
int k;
其中MAX_NODE是trie中最大能存儲(chǔ)的節(jié)點(diǎn)數(shù)目，CHARSET是字符集的大小，k是當(dāng)前trie中包含有多少個(gè)節(jié)點(diǎn)。Trie[i][j]的值是0表示trie樹中i號(hào)節(jié)點(diǎn)，并沒有一條連出去的邊，滿足邊上的字符標(biāo)識(shí)是字符集中第j個(gè)字符（從0開始）；trie[i][j]的值是正整數(shù)x表示trie樹中i號(hào)節(jié)點(diǎn)，有一條連出去的邊，滿足邊上的字符標(biāo)識(shí)是字符集中第j個(gè)字符，并且這條邊的終點(diǎn)是x號(hào)節(jié)點(diǎn)。

簡(jiǎn)單實(shí)現(xiàn)

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAX_NODE = 1000000 + 10;
const int CHARSET = 26;
int trie[MAX_NODE][CHARSET] = {0};
int color[MAX_NODE] = {0};
int k = 1;

void insert(char *w){
    int len = strlen(w);
    int p = 0;
    for(int i=0; i<len; i++){
        int c = w[i] - 'a';
        if(!trie[p][c]){
            trie[p][c] = k;
            k++;
        }
        p = trie[p][c];
    }
    color[p] = 1;
}

int search(char *s){
    int len = strlen(s);
    int p = 0;
    for(int i=0; i<len; i++){
        int c = s[i] - 'a';
        if(!trie[p][c]) return 0;
        p = trie[p][c];
    }
    return color[p] == 1;
}

int main(){
    int t,q;
    char s[20];
    scanf("%d%d", &t,&q);
    while(t--){
        scanf("%s", s);
        insert(s);
    }
    while(q--){
        scanf("%s", s);
        if(search(s)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

轉(zhuǎn)自：https://blog.csdn.net/weixin_39778570/article/details/81990417