• <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
            国产精品成人无码久久久久久| 国产精品18久久久久久vr| 国产91久久综合| 精品久久久久久无码国产| 四虎国产精品成人免费久久| 亚洲AV无码久久精品成人| 人人狠狠综合久久亚洲婷婷| 久久综合给合综合久久| 久久精品人人做人人爽电影蜜月| 国产精品美女久久久免费| 久久久久免费精品国产| 蜜桃麻豆www久久| 久久久久无码精品国产不卡| 大蕉久久伊人中文字幕| 久久久久亚洲精品日久生情| 99久久99久久精品国产| 国产毛片欧美毛片久久久| 伊人热人久久中文字幕| 久久人妻AV中文字幕| 日本加勒比久久精品| 久久99精品国产麻豆宅宅| 人妻无码αv中文字幕久久| 久久免费香蕉视频| 欧美777精品久久久久网| 亚洲AV无码久久精品狠狠爱浪潮| 久久综合伊人77777| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区| 一级A毛片免费观看久久精品| 热re99久久精品国产99热| 久久精品国产亚洲av高清漫画| 久久国内免费视频| 一级做a爰片久久毛片毛片| 久久久久久A亚洲欧洲AV冫| 国产精品九九久久免费视频| 久久精品成人免费网站| 久久91精品久久91综合| 日本久久久久久中文字幕| 天天爽天天爽天天片a久久网| 久久九九全国免费| 久久午夜无码鲁丝片午夜精品| 国产精品内射久久久久欢欢|