2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(9)

　　(6)trie樹(shù)

　　Trie樹(shù)，即Double Array字典查找樹(shù)，既可用于一般的字典搜索，也可用于索引查找。

　　每個(gè)節(jié)點(diǎn)相當(dāng)于DFA的一個(gè)狀態(tài)，終止?fàn)顟B(tài)為查找結(jié)束。有序查找的過(guò)程相當(dāng)于狀態(tài)的不斷轉(zhuǎn)換

　　對(duì)于給定的一個(gè)字符串a(chǎn)1,a2,a3,...,an.則

　　采用TRIE樹(shù)搜索經(jīng)過(guò)n次搜索即可完成一次查找。不過(guò)好像還是沒(méi)有B樹(shù)的搜索效率高，B樹(shù)搜索算法復(fù)雜度為logt(n+1/2).當(dāng)t趨向大，搜索效率變得高效。

　　Trie樹(shù)的優(yōu)點(diǎn)舉例

　　已知n個(gè)由小寫字母構(gòu)成的平均長(zhǎng)度為10的單詞,判斷其中是否存在某個(gè)串為另一個(gè)串的前綴子串。下面對(duì)比3種方法：

　　1. 最容易想到的：即從字符串集中從頭往后搜，看每個(gè)字符串是否為字符串集中某個(gè)字符串的前綴，復(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)缱址�串a(chǎn)bc是否為某個(gè)字符串的前綴時(shí)，顯然以b,c,d....等不是以a開(kāi)頭的字符串就不用查找了。所以建立trie的復(fù)雜度為O(n*len)，而建立+查詢?cè)趖rie中是可以同時(shí)執(zhí)行的，建立的過(guò)程也就可以成為查詢的過(guò)程，hash就不能實(shí)現(xiàn)這個(gè)功能。所以總的復(fù)雜度為O(n*len)，實(shí)際查詢的復(fù)雜度只是O(len)。

　　解釋一下hash為什么不能將建立與查詢同時(shí)執(zhí)行，例如有串：911，911456輸入，如果要同時(shí)執(zhí)行建立與查詢，過(guò)程就是查詢911，沒(méi)有，然后存入9、91、911，查詢911456，沒(méi)有然后存入9114、91145、911456，而程序沒(méi)有記憶功能，并不知道911在輸入數(shù)據(jù)中出現(xiàn)過(guò)。所以用hash必須先存入所有子串，然后for循環(huán)查詢。

　　而trie樹(shù)便可以，存入911后，已經(jīng)記錄911為出現(xiàn)的字符串，在存入911456的過(guò)程中就能發(fā)現(xiàn)而輸出答案;倒過(guò)來(lái)亦可以，先存入911456，在存入911時(shí)，當(dāng)指針指向最后一個(gè)1時(shí)，程序會(huì)發(fā)現(xiàn)這個(gè)1已經(jīng)存在，說(shuō)明911必定是某個(gè)字符串的前綴，該思想是我在做pku上的3630中發(fā)現(xiàn)的，詳見(jiàn)本文配套的“入門練習(xí)”。

　　小結(jié)

　　B樹(shù)：二叉樹(shù)，每個(gè)結(jié)點(diǎn)只存儲(chǔ)一個(gè)關(guān)鍵字，等于則命中，小于走左結(jié)點(diǎn)，大于走右結(jié)點(diǎn);

　　B-樹(shù)：多路搜索樹(shù)，每個(gè)結(jié)點(diǎn)存儲(chǔ)M/2到M個(gè)關(guān)鍵字，非葉子結(jié)點(diǎn)存儲(chǔ)指向關(guān)鍵字范圍的子結(jié)點(diǎn);所有關(guān)鍵字在整顆樹(shù)中出現(xiàn)，且只出現(xiàn)一次，非葉子結(jié)點(diǎn)可以命中;

　　B+樹(shù)：在B-樹(shù)基礎(chǔ)上，為葉子結(jié)點(diǎn)增加鏈表指針，所有關(guān)鍵字都在葉子結(jié)點(diǎn)中出現(xiàn)，非葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)的索引;B+樹(shù)總是到葉子結(jié)點(diǎn)才命中;

　　B*樹(shù)：在B+樹(shù)基礎(chǔ)上，為非葉子結(jié)點(diǎn)也增加鏈表指針，將結(jié)點(diǎn)的最低利用率從1/2提高到2/3;

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)