• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            陋居

            淡薄名利,修身養性

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              31 Posts :: 1 Stories :: 4 Comments :: 0 Trackbacks

            常用鏈接

            留言簿

            我參與的團隊

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            文章作者:yx_th000 文章來源:Cherish_yimi (http://www.cnblogs.com/cherish_yimi/) 轉載請注明,謝謝合作。
            關鍵詞:trie trie樹 數據結構

                前幾天學習了并查集和trie樹,這里總結一下trie。
                本文討論一棵最簡單的trie樹,基于英文26個字母組成的字符串,討論插入字符串、判斷前綴是否存在、查找字符串等基本操作;至于trie樹的刪除單個節點實在是少見,故在此不做詳解。

            l        Trie原理

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

            l        Trie性質

            好多人說trie的根節點不包含任何字符信息,我所習慣的trie根節點卻是包含信息的,而且認為這樣也方便,下面說一下它的性質 (基于本文所討論的簡單trie樹)

            1.    字符的種數決定每個節點的出度,即branch數組(空間換時間思想)

            2.    branch數組的下標代表字符相對于a的相對位置

            3.    采用標記的方法確定是否為字符串。

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

            l        Trie的示意圖

            如圖所示,該trie樹存有abc、d、da、dda四個字符串,如果是字符串會在節點的尾部進行標記。沒有后續字符的branch分支指向NULL





            l       
            Trie
            Trie的優點舉例

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

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

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

            3.    使 用trie:因為當查詢如字符串abc是否為某個字符串的前綴時,顯然以b,c,d....等不是以a開頭的字符串就不用查找了。所以建立trie的復雜 度為O(n*len),而建立+查詢在trie中是可以同時執行的,建立的過程也就可以成為查詢的過程,hash就不能實現這個功能。所以總的復雜度為 O(n*len),實際查詢的復雜度只是O(len)。


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

            而trie樹便可 以,存入911后,已經記錄911為出現的字符串,在存入911456的過程中就能發現而輸出答案;倒過來亦可以,先存入911456,在存入911時, 當指針指向最后一個1時,程序會發現這個1已經存在,說明911必定是某個字符串的前綴,該思想是我在做pku上的3630中發現的,詳見本文配套的“入 門練習”。

            l        Trie的簡單實現(插入、查詢)


             1
             2#include <iostream>
             3using namespace std;
             4
             5const int branchNum = 26//聲明常量 
             6int i;
             7
             8struct Trie_node
             9{
            10    bool isStr; //記錄此處是否構成一個串。
            11    Trie_node *next[branchNum];//指向各個子樹的指針,下標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']; //每插入一步,相當于有一個新串經過,指針要向下移動
            45        word++;
            46    }

            47    location->isStr = true//到達尾部,標記一個串
            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() //簡單測試
            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}

            posted on 2010-11-26 09:48 eircQ 閱讀(311) 評論(0)  編輯 收藏 引用 所屬分類: Arithmetic
            99久久国语露脸精品国产| 久久综合色之久久综合| 精品熟女少妇av免费久久| 久久久久99精品成人片欧美| 国产精品久久永久免费| 国产一区二区精品久久凹凸| 亚洲国产精品成人久久蜜臀 | 99久久精品国产一区二区| 久久精品国产亚洲Aⅴ蜜臀色欲| 久久综合给合综合久久| 国产精品一区二区久久国产| 国产精品亚洲综合专区片高清久久久 | 亚洲熟妇无码另类久久久| 99久久伊人精品综合观看| 人人狠狠综合久久亚洲高清| 国产精品久久久久久吹潮| 精品国产青草久久久久福利| 久久国产色AV免费观看| 久久夜色精品国产| 91性高湖久久久久| 国产午夜久久影院| 亚洲精品无码久久千人斩| 久久高清一级毛片| 久久综合欧美成人| 亚洲国产另类久久久精品 | 久久亚洲AV无码西西人体| 国产麻豆精品久久一二三| 亚洲精品乱码久久久久久久久久久久 | www.久久热.com| 亚洲AV无码久久精品狠狠爱浪潮| 久久精品一区二区三区中文字幕 | 久久伊人色| 久久精品国产一区二区三区不卡| 久久婷婷国产麻豆91天堂| 99久久无色码中文字幕| 精品久久久久久国产潘金莲| 亚洲中文久久精品无码ww16| 亚洲欧美日韩久久精品第一区| 亚洲综合伊人久久综合| 无码人妻精品一区二区三区久久久| 女人高潮久久久叫人喷水|