Trie樹就是字典樹，其核心思想就是空間換時(shí)間。

舉個(gè)簡單的例子。

給你100000個(gè)長度不超過10的單詞。對(duì)于每一個(gè)單詞，我們要判斷他出沒出現(xiàn)過，如果出現(xiàn)了，第一次出現(xiàn)第幾個(gè)位置。
這題當(dāng)然可以用hash來，但是我要介紹的是trie樹。在某些方面它的用途更大。比如說對(duì)于某一個(gè)單詞，我要詢問它的前綴是否出現(xiàn)過。這樣hash就不好搞了，而用trie還是很簡單。
現(xiàn)在回到例子中，如果我們用最傻的方法，對(duì)于每一個(gè)單詞，我們都要去查找它前面的單詞中是否有它。那么這個(gè)算法的復(fù)雜度就是O(n^2)。顯然對(duì)于100000的范圍難以接受。現(xiàn)在我們換個(gè)思路想。假設(shè)我要查詢的單詞是abcd，那么在他前面的單詞中，以b，c，d，f之類開頭的我顯然不必考慮。而只要找以a開頭的中是否存在abcd就可以了。同樣的，在以a開頭中的單詞中，我們只要考慮以b作為第二個(gè)字母的……這樣一個(gè)樹的模型就漸漸清晰了……
假設(shè)有b，abc，abd，bcd，abcd，efg，hii這6個(gè)單詞，我們構(gòu)建的樹就是這樣的。

對(duì)于每一個(gè)節(jié)點(diǎn)，從根遍歷到他的過程就是一個(gè)單詞，如果這個(gè)節(jié)點(diǎn)被標(biāo)記為紅色，就表示這個(gè)單詞存在，否則不存在。
那么，對(duì)于一個(gè)單詞，我只要順著他從跟走到對(duì)應(yīng)的節(jié)點(diǎn)，再看這個(gè)節(jié)點(diǎn)是否被標(biāo)記為紅色就可以知道它是否出現(xiàn)過了。把這個(gè)節(jié)點(diǎn)標(biāo)記為紅色，就相當(dāng)于插入了這個(gè)單詞。
這樣一來我們?cè)儐柡筒迦肟梢砸黄鹜瓿桑脮r(shí)間僅僅為單詞長度，在這一個(gè)樣例，便是10。
我們可以看到，trie樹每一層的節(jié)點(diǎn)數(shù)是26^i級(jí)別的。所以為了節(jié)省空間。我們用動(dòng)態(tài)鏈表，或者用數(shù)組來模擬動(dòng)態(tài)。空間的花費(fèi)，不會(huì)超過單詞數(shù)×單詞長度。

給出一個(gè)用類封裝的字典樹代碼，厄。。。做ACM的模板用另一個(gè)。。應(yīng)該放在了“ACM模板”文件夾下了。。。

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;


const int num_chars = 26;


class Trie {
public:
      Trie():root(NULL){};
      Trie(Trie& tr);

     int search(const char* word, char* entry ) const;
     int insert(const char* word, const char* entry);
     int remove(const char* word, char* entry);
private:
     struct Trie_node
     {
         char* data;
          Trie_node* branch[num_chars];
          Trie_node();
     }* root;
};
Trie::Trie_node::Trie_node() 
{
      data = NULL;
    for (int i=0; i<num_chars; ++i) 
          branch[i] = NULL;
}

int Trie::search(const char* word, char* entry ) const 
{
    int position = 0;
    char char_code;
     Trie_node *location = root;
    while( location!=NULL && *word!=0 ) 
    {
        if (*word>='A' && *word<='Z') 
              char_code = *word-'A';
        else if (*word>='a' && *word<='z') 
              char_code = *word-'a';
        else return 0;


         location = location->branch[char_code];
         position++;
         word++;
    }
    if ( location != NULL && location->data != NULL ) 
    {
        strcpy(entry,location->data);
        return 1;
    }
    else return 0;
}
int Trie::insert(const char* word, const char* entry) 
{
    int result = 1, position = 0;
    if ( root == NULL ) root = new Trie_node;
    char char_code;
      Trie_node *location = root;
    while( location!=NULL && *word!=0 )
    {
        if (*word>='A' && *word<='Z') 
              char_code = *word-'A';
        else if (*word>='a' && *word<='z') 
              char_code = *word-'a';
        else return 0;


        if( location->branch[char_code] == NULL ) 
              location->branch[char_code] = new Trie_node;


          location = location->branch[char_code];
          position++;
          word++;
    }
    if (location->data != NULL)
          result = 0;
    else {
          location->data = new char[strlen(entry)+1];
        strcpy(location->data, entry);
    }
    return result;
}
int main()
{
      Trie t;
      char entry[100];
      t.insert("aa", "DET"); 
      t.insert("abacus","NOUN");
      t.insert("abalone","NOUN"); 
      t.insert("abandon","VERB");
      t.insert("abandoned","ADJ"); 
      t.insert("abashed","ADJ");
      t.insert("abate","VERB"); 
      t.insert("this", "PRON");
    if (t.search("this", entry))
        cout<<"'this' was found. pos: "<<entry<<endl;
    if (t.search("abate", entry))
        cout<<"'abate' is found. pos: "<<entry<<endl;
    if (t.search("baby", entry))
        cout<<"'baby' is found. pos: "<<entry<<endl;
    else
        cout<<"'baby' does not exist at all!"<<endl;
    
    if (t.search("aa", entry))
        cout<<"'aa was found. pos: "<<entry<<endl;
}