淡薄名利,修身養(yǎng)性
文章作者：yx_th000 文章來源：Cherish_yimi (http://www.cnblogs.com/cherish_yimi/) 轉(zhuǎn)載請注明，謝謝合作。關(guān)鍵詞：trie trie樹 數(shù)據(jù)結(jié)構(gòu)
前幾天學(xué)習(xí)了并查集和trie樹，這里總結(jié)一下trie。 本文討論一棵最簡單的trie樹，基于英文26個字母組成的字符串，討論插入字符串、判斷前綴是否存在、查找字符串等基本操作；至于trie樹的刪除單個節(jié)點(diǎn)實(shí)在是少見，故在此不做詳解。
l Trie原理
Trie的核心思想是空間換時(shí)間。利用字符串的公共前綴來降低查詢時(shí)間的開銷以達(dá)到提高效率的目的。
l Trie性質(zhì)
好多人說trie的根節(jié)點(diǎn)不包含任何字符信息，我所習(xí)慣的trie根節(jié)點(diǎn)卻是包含信息的，而且認(rèn)為這樣也方便，下面說一下它的性質(zhì) (基于本文所討論的簡單trie樹)
1. 字符的種數(shù)決定每個節(jié)點(diǎn)的出度，即branch數(shù)組(空間換時(shí)間思想)
2. branch數(shù)組的下標(biāo)代表字符相對于a的相對位置
3. 采用標(biāo)記的方法確定是否為字符串。
4. 插入、查找的復(fù)雜度均為O(len),len為字符串長度
l Trie的示意圖
如圖所示，該trie樹存有abc、d、da、dda四個字符串，如果是字符串會在節(jié)點(diǎn)的尾部進(jìn)行標(biāo)記。沒有后續(xù)字符的branch分支指向NULLl TrieTrie的優(yōu)點(diǎn)舉例
已知n個由小寫字母構(gòu)成的平均長度為10的單詞,判斷其中是否存在某個串為另一個串的前綴子串。下面對比3種方法：
1. 最容易想到的：即從字符串集中從頭往后搜，看每個字符串是否為字符串集中某個字符串的前綴，復(fù)雜度為O(n^2)。
2. 使用hash：我們用hash存下所有字符串的所有的前綴子串。建立存有子串hash的復(fù)雜度為O(n*len)。查詢的復(fù)雜度為O(n)* O(1)= O(n)。
3. 使 用trie：因?yàn)楫?dāng)查詢?nèi)缱址產(chǎn)bc是否為某個字符串的前綴時(shí)，顯然以b,c,d....等不是以a開頭的字符串就不用查找了。所以建立trie的復(fù)雜 度為O(n*len)，而建立+查詢在trie中是可以同時(shí)執(zhí)行的，建立的過程也就可以成為查詢的過程，hash就不能實(shí)現(xiàn)這個功能。所以總的復(fù)雜度為 O(n*len)，實(shí)際查詢的復(fù)雜度只是O(len)。
解釋一下 hash為什么不能將建立與查詢同時(shí)執(zhí)行，例如有串：911，911456輸入，如果要同時(shí)執(zhí)行建立與查詢，過程就是查詢911，沒有，然后存入9、 91、911，查詢911456，沒有然后存入9114、91145、911456，而程序沒有記憶功能，并不知道911在輸入數(shù)據(jù)中出現(xiàn)過。所以用 hash必須先存入所有子串，然后for循環(huán)查詢。
而trie樹便可 以，存入911后，已經(jīng)記錄911為出現(xiàn)的字符串，在存入911456的過程中就能發(fā)現(xiàn)而輸出答案；倒過來亦可以，先存入911456，在存入911時(shí)， 當(dāng)指針指向最后一個1時(shí)，程序會發(fā)現(xiàn)這個1已經(jīng)存在，說明911必定是某個字符串的前綴，該思想是我在做pku上的3630中發(fā)現(xiàn)的，詳見本文配套的“入 門練習(xí)”。
l Trie的簡單實(shí)現(xiàn)(插入、查詢)
Copyright @ eircQ Powered by: .Text and ASP.NET Theme by: .NET Monster