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

　　(6)trie樹

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

　　每個節(jié)點相當于DFA的一個狀態(tài)，終止狀態(tài)為查找結(jié)束。有序查找的過程相當于狀態(tài)的不斷轉(zhuǎn)換

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

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

　　Trie樹的優(yōu)點舉例

　　已知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：因為當查詢?nèi)缱址�串a(chǎn)bc是否為某個字符串的前綴時，顯然以b,c,d....等不是以a開頭的字符串就不用查找了。所以建立trie的復(fù)雜度為O(n*len)，而建立+查詢在trie中是可以同時執(zhí)行的，建立的過程也就可以成為查詢的過程，hash就不能實現(xiàn)這個功能。所以總的復(fù)雜度為O(n*len)，實際查詢的復(fù)雜度只是O(len)。

　　解釋一下hash為什么不能將建立與查詢同時執(zhí)行，例如有串：911，911456輸入，如果要同時執(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時，當指針指向最后一個1時，程序會發(fā)現(xiàn)這個1已經(jīng)存在，說明911必定是某個字符串的前綴，該思想是我在做pku上的3630中發(fā)現(xiàn)的，詳見本文配套的“入門練習(xí)”。

　　小結(jié)

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

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

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

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

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

　　2011年上半年軟考報名時間及方式匯總

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