字典樹(trie tree)

     今天AC了兩題trie tree的題目,感覺trie的性質(zhì)真的是相當(dāng)?shù)暮茫覍崿F(xiàn)比較簡單。它使在字符串集合中查找某個字符串的操作的復(fù)雜度降到最大只需O(n),其中n為字符串的長度。trie是典型的將時間置換為空間的算法，好在ACM中一般對空間的要求很寬松。

     trie的原理是利用字符串集合中字符串的公共前綴來降低時間開銷以達(dá)到提高效率的目的。

它具有以下性質(zhì):1,根結(jié)點不包含任何字符信息;2,如果字符的種數(shù)為n,則每個結(jié)點的出度為n(這樣必然會導(dǎo)致浪費很多空間,這也是trie的缺點,我還沒有想到好點的辦法避免);3,查找，插入復(fù)雜度為O(n),n為字符串長度。

    舉一個例子,給50000個由小寫字母構(gòu)成的長度不超過10的單詞,然后問某個公共前綴是否出現(xiàn)過。如果我們直接從字符串集中從頭往后搜，看給定的字符串是否為字符串集中某個字符串的前綴，那樣復(fù)雜度為O(50000^2)，這樣顯然會TLE。又或是我們對于字符串集中的每個字符串，我們用MAP存下它所有的前綴。然后詢問時可以直接給出結(jié)果。這樣復(fù)雜度為O(50000*len),最壞情況下len為字符串最長字符串的長度。而且這沒有算建立MAP存儲的時間，也沒有算用MAP查詢的時間，實際效率會更低。但如果我們用trie的話，當(dāng)查詢?nèi)缱址?/span>abcd是否為某字符串的前綴時，顯然以b,c,d....等不是以a開頭的字符串就不用查找了。實際查詢復(fù)雜度只有O(len)，建立trie的復(fù)雜度為O(50000).這是完全可以接受的。

    如給定字符串集合abcd,abd,cdd,efg,hij,hi六個字符串建立的trie tree如下圖所示:

  

    查找一個字符串時，我們只需從根結(jié)點按字符串中字符出現(xiàn)順序依次往下走。如果到最后字符串結(jié)束時，對應(yīng)的結(jié)點標(biāo)記為紅色，則該字符串存在;否則不存在。

    插入時也只需從根結(jié)點往下遍歷，碰到已存在的字符結(jié)點就往下遍歷，否則，建立新結(jié)點;最后標(biāo)記最后一個字符的結(jié)點為紅色即可。

    同時我們看到,如果字符的種類為n，則需要結(jié)點的個數(shù)為n級數(shù)。(誰有好辦法降低空間開銷,請告訴我)

 

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

題目:http://acm.hdu.edu.cn/showproblem.php?pid=1251

題目和我上面舉的例子差不多，是說給定一個字符串集合，然后每次詢問時給出一個字符串，問以該字符串為前綴的字符串在集合中有多少個。先給個用MAP版本的，限時2000MS的題目，用MAP，1750MS，險過。

 我的代碼：

 1#include<iostream>
 2using namespace  std;
 3const int kind=26;
 4struct trienode{
 5    public:
 6    trienode *next[kind];    
 7    int branch;
 8    trienode()
 9    {
10     branch=0;
11     for(int i=0;i<kind;i++)
12     next[i]=NULL;    
13    }
14};
15class trie{
16
17    trienode *root;
18    public:
19    trie(){root=NULL;}
20    void insert(char s[])
21    {
22        trienode *location=root;
23        if(location==NULL)
24        location=root=new trienode();
25        int i=0,k;
26        while(s[i])
27        {
28            k=s[i]-'a';
29            if(location->next[k])
30                location->next[k]->branch++;
31            else
32            {
33                location->next[k]=new trienode();
34                location->next[k]->branch++;    
35            }
36            i++;
37            location=location->next[k];    
38        }
39    }
40    int search(char s[]){
41        trienode *location=root;
42        if(!location) return 0;
43        int k,i=0,ans;
44        while(s[i])
45        {
46            k=s[i]-'a';
47            if(!location->next[k])    
48             return 0;
49            ans=location->next[k]->branch;
50            location=location->next[k];
51            i++;
52        }    
53        return ans;
54    }    
55    
56};
57int main()
58{
59    char a[100];
60    int i;
61    trie mytrie;
62    while(gets(a))
63    {
64        if(a[0]=='\0')
65        break;
66        mytrie.insert(a);    
67    }
68    while(gets(a)!=NULL)
69    {
70        //if(a=="end")
71        
72        printf("%d\n",mytrie.search(a));    
73    }
74    return 0;
75}
76