文章作者：yx_th000 文章來源：Cherish_yimi (http://www.cnblogs.com/cherish_yimi/) 轉(zhuǎn)載請(qǐng)注明，謝謝合作。
關(guān)鍵詞：trie trie樹 數(shù)據(jù)結(jié)構(gòu)

    前幾天學(xué)習(xí)了并查集和trie樹，這里總結(jié)一下trie。
    本文討論一棵最簡單的trie樹，基于英文26個(gè)字母組成的字符串，討論插入字符串、判斷前綴是否存在、查找字符串等基本操作；至于trie樹的刪除單個(gè)節(jié)點(diǎn)實(shí)在是少見，故在此不做詳解。

l        Trie原理

Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。

l        Trie性質(zhì)

好多人說trie的根節(jié)點(diǎn)不包含任何字符信息，我所習(xí)慣的trie根節(jié)點(diǎn)卻是包含信息的，而且認(rèn)為這樣也方便，下面說一下它的性質(zhì) (基于本文所討論的簡單trie樹)

1.    字符的種數(shù)決定每個(gè)節(jié)點(diǎn)的出度，即branch數(shù)組(空間換時(shí)間思想)

2.    branch數(shù)組的下標(biāo)代表字符相對(duì)于a的相對(duì)位置

3.    采用標(biāo)記的方法確定是否為字符串。

4.    插入、查找的復(fù)雜度均為O(len),len為字符串長度

l        Trie的示意圖

如圖所示，該trie樹存有abc、d、da、dda四個(gè)字符串，如果是字符串會(huì)在節(jié)點(diǎn)的尾部進(jìn)行標(biāo)記。沒有后續(xù)字符的branch分支指向NULL





l        TrieTrie的優(yōu)點(diǎn)舉例

已知n個(gè)由小寫字母構(gòu)成的平均長度為10的單詞,判斷其中是否存在某個(gè)串為另一個(gè)串的前綴子串。下面對(duì)比3種方法：

1.    最容易想到的：即從字符串集中從頭往后搜，看每個(gè)字符串是否為字符串集中某個(gè)字符串的前綴，復(fù)雜度為O(n^2)。

2.    使用hash：我們用hash存下所有字符串的所有的前綴子串。建立存有子串hash的復(fù)雜度為O(n*len)。查詢的復(fù)雜度為O(n)* O(1)= O(n)。

3.    使用trie：因?yàn)楫?dāng)查詢?nèi)缱址產(chǎn)bc是否為某個(gè)字符串的前綴時(shí)，顯然以b,c,d....等不是以a開頭的字符串就不用查找了。所以建立trie的復(fù)雜度為O(n*len)，而建立+查詢?cè)趖rie中是可以同時(shí)執(zhí)行的，建立的過程也就可以成為查詢的過程，hash就不能實(shí)現(xiàn)這個(gè)功能。所以總的復(fù)雜度為O(n*len)，實(shí)際查詢的復(fù)雜度只是O(len)。

解釋一下hash為什么不能將建立與查詢同時(shí)執(zhí)行，例如有串：911，911456輸入，如果要同時(shí)執(zhí)行建立與查詢，過程就是查詢911，沒有，然后存入9、91、911，查詢911456，沒有然后存入9114、91145、911456，而程序沒有記憶功能，并不知道911在輸入數(shù)據(jù)中出現(xiàn)過。所以用hash必須先存入所有子串，然后for循環(huán)查詢。

而trie樹便可以，存入911后，已經(jīng)記錄911為出現(xiàn)的字符串，在存入911456的過程中就能發(fā)現(xiàn)而輸出答案；倒過來亦可以，先存入911456，在存入911時(shí)，當(dāng)指針指向最后一個(gè)1時(shí)，程序會(huì)發(fā)現(xiàn)這個(gè)1已經(jīng)存在，說明911必定是某個(gè)字符串的前綴，該思想是我在做pku上的3630中發(fā)現(xiàn)的，詳見本文配套的“入門練習(xí)”。

l        Trie的簡單實(shí)現(xiàn)(插入、查詢)

 1
 2#include <iostream>
 3using namespace std;
 4
 5const int branchNum = 26; //聲明常量 
 6int i;
 7
 8struct Trie_node
 9{
10    bool isStr; //記錄此處是否構(gòu)成一個(gè)串。
11    Trie_node *next[branchNum];//指向各個(gè)子樹的指針,下標(biāo)0-25代表26字符
12    Trie_node():isStr(false)
13    {
14        memset(next,NULL,sizeof(next));
15    }
16};
17
18class Trie
19{
20public:
21    Trie();
22    void insert(const char* word);
23    bool search(char* word); 
24    void deleteTrie(Trie_node *root);
25private:
26    Trie_node* root;
27};
28
29Trie::Trie()
30{
31    root = new Trie_node();
32}
33
34void Trie::insert(const char* word)
35{
36    Trie_node *location = root;
37    while(*word)
38    {
39        if(location->next[*word-'a'] == NULL)//不存在則建立
40        {
41            Trie_node *tmp = new Trie_node();
42            location->next[*word-'a'] = tmp;
43        }    
44        location = location->next[*word-'a']; //每插入一步，相當(dāng)于有一個(gè)新串經(jīng)過，指針要向下移動(dòng)
45        word++;
46    }
47    location->isStr = true; //到達(dá)尾部,標(biāo)記一個(gè)串
48}
49
50bool Trie::search(char *word)
51{
52    Trie_node *location = root;
53    while(*word && location)
54    {
55        location = location->next[*word-'a'];
56        word++;
57    }
58    return(location!=NULL && location->isStr);
59}
60
61void Trie::deleteTrie(Trie_node *root)
62{
63    for(i = 0; i < branchNum; i++)
64    {
65        if(root->next[i] != NULL)
66        {
67            deleteTrie(root->next[i]);
68        }
69    }
70    delete root;
71}
72
73void main() //簡單測(cè)試
74{
75    Trie t;
76    t.insert("a");         
77    t.insert("abandon");
78    char * c = "abandoned";
79    t.insert(c);
80    t.insert("abashed");
81    if(t.search("abashed"))
82        printf("true\n");
83}