• <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>

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            Trie樹

            Trie樹就是字符樹,其核心思想就是空間換時間

            舉個簡單的例子。

            給你100000個長度不超過10的單詞。對于每一個單詞,我們要判斷他出沒出現過,如果出現了,第一次出現第幾個位置。

            這題當然可以用hash來,但是我要介紹的是trie樹。在某些方面它的用途更大。比如說對于某一個單詞,我要詢問它的前綴是否出現過。這樣hash就不好搞了,而用trie還是很簡單。

            現在回到例子中,如果我們用最傻的方法,對于每一個單詞,我們都要去查找它前面的單詞中是否有 它。那么這個算法的復雜度就是O(n^2)。顯然對于100000的范圍難以接受。現在我們換個思路想。假設我要查詢的單詞是abcd,那么在他前面的單 詞中,以b,c,d,f之類開頭的我顯然不必考慮。而只要找以a開頭的中是否存在abcd就可以了。同樣的,在以a開頭中的單詞中,我們只要考慮以b作為 第二個字母的……這樣一個樹的模型就漸漸清晰了……

            假設有b,abc,abd,bcd,abcd,efg,hii這6個單詞,我們構建的樹就是這樣的。

            對于每一個節點,從根遍歷到他的過程就是一個單詞,如果這個節點被標記為紅色,就表示這個單詞存在,否則不存在。

            那么,對于一個單詞,我只要順著他從跟走到對應的節點,再看這個節點是否被標記為紅色就可以知道它是否出現過了。把這個節點標記為紅色,就相當于插入了這個單詞。

            這樣一來我們詢問和插入可以一起完成,所用時間僅僅為單詞長度,在這一個樣例,便是10。

            我們可以看到,trie樹每一層的節點數是26^i級別的。所以為了節省空間。我們用動態鏈表,或者用數組來模擬動態。空間的花費,不會超過單詞數×單詞長度。




            posted on 2012-08-22 09:26 wangs 閱讀(2353) 評論(0)  編輯 收藏 引用 所屬分類: ACM-數據結構

            久久激情亚洲精品无码?V| 久久免费大片| 国内精品久久久久伊人av| 精品久久久久久国产| 色欲久久久天天天综合网| 欧美午夜精品久久久久久浪潮| 国产亚洲色婷婷久久99精品91| 久久婷婷五月综合97色直播| 新狼窝色AV性久久久久久| 日本道色综合久久影院| 色综合久久中文字幕综合网| 久久午夜无码鲁丝片| 久久综合狠狠综合久久97色| 国内精品久久久久影院日本| 久久99热这里只有精品66| 国产精品久久久久久| 久久婷婷午色综合夜啪| 91超碰碰碰碰久久久久久综合| 久久久久久精品成人免费图片| 99久久无码一区人妻| 久久99精品久久久久久动态图| 亚洲伊人久久成综合人影院 | 99精品伊人久久久大香线蕉| 久久精品极品盛宴观看| 国产精品丝袜久久久久久不卡| 久久久久无码精品国产不卡| 久久99热这里只有精品66| 久久久噜噜噜久久| 久久精品国产亚洲5555| 国产福利电影一区二区三区久久久久成人精品综合 | 久久精品这里热有精品| 色诱久久久久综合网ywww| 99久久综合国产精品免费| 一本久久a久久精品综合香蕉| 久久久久亚洲av毛片大| 久久久久无码精品国产app| 国产午夜福利精品久久| 久久久久久久久久久免费精品| 99久久精品国产一区二区| .精品久久久麻豆国产精品| 国内精品久久久久影院免费|