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

　　(3)B+樹

　　B+樹是B-樹的變體，也是一種多路搜索樹：

　　1.其定義基本與B-樹同，除了：

　　2.非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同;

　　3.非葉子結(jié)點的子樹指針P[i]，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹(B-樹是開區(qū)間);

　　5.為所有葉子結(jié)點增加一個鏈指針;

　　6.所有關(guān)鍵字都在葉子結(jié)點出現(xiàn);

　　如：(M=3)

　　B+的搜索與B-樹也基本相同，區(qū)別是B+樹只有達到葉子結(jié)點才命中(B-樹可以在非葉子結(jié)點命中)，其性能也等價于在關(guān)鍵字全集做一次二分查找;

　　B+的特性：

　　1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中(稠密索引)，且鏈表中的關(guān)鍵字恰好是有序的;

　　2.不可能在非葉子結(jié)點命中;

　　3.非葉子結(jié)點相當(dāng)于是葉子結(jié)點的索引(稀疏索引)，葉子結(jié)點相當(dāng)于是存儲(關(guān)鍵字)數(shù)據(jù)的數(shù)據(jù)層;

　　4.更適合文件索引系統(tǒng);

　　(4)B*樹

　　是B+樹的變體，在B+樹的非根和非葉子結(jié)點再增加指向兄弟的指針;

　　B*樹定義了非葉子結(jié)點關(guān)鍵字個數(shù)至少為(2/3)*M，即塊的最低使用率為2/3(代替B+樹的1/2);

　　B+樹的分裂：當(dāng)一個結(jié)點滿時，分配一個新的結(jié)點，并將原結(jié)點中1/2的數(shù)據(jù)復(fù)制到新結(jié)點，最后在父結(jié)點中增加新結(jié)點的指針;B+樹的分裂只影響原結(jié)點和父結(jié)點，而不會影響兄弟結(jié)點，所以它不需要指向兄弟的指針;

　　B*樹的分裂：當(dāng)一個結(jié)點滿時，如果它的下一個兄弟結(jié)點未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點中，再在原結(jié)點插入關(guān)鍵字，最后修改父結(jié)點中兄弟結(jié)點的關(guān)鍵字(因為兄弟結(jié)點的關(guān)鍵字范圍改變了);如果兄弟也滿了，則在原結(jié)點與兄弟結(jié)點之間增加新結(jié)點，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點，最后在父結(jié)點增加新結(jié)點的指針;

　　所以，B*樹分配新結(jié)點的概率比B+樹要低，空間使用率更高;

　　(5)紅黑樹

　　紅黑樹(Red-Black Tree)是二叉搜索樹(BinarySearch Tree)的一種改進。我們知道二叉搜索樹在最壞的情況下可能會變成一個鏈表(當(dāng)所有節(jié)點按從小到大的順序依次插入后)。而紅黑樹在每一次插入或刪除節(jié)點之后都會花O(log N)的時間來對樹的結(jié)構(gòu)作修改，以保持樹的平衡。也就是說，紅黑樹的查找方法與二叉搜索樹完全一樣;插入和刪除節(jié)點的的方法前半部分節(jié)與二叉搜索樹完全一樣，而后半部分添加了一些修改樹的結(jié)構(gòu)的操作。

　　map就是采用紅黑樹存儲的，紅黑樹(RB Tree)是平衡二叉樹，其優(yōu)點就是樹到葉子節(jié)點深度一致，查找的效率也就一樣，為logN。在實行查找，插入，刪除的效率都一致，而當(dāng)是全部靜態(tài)數(shù)據(jù)時，沒有太多優(yōu)勢，可能采用hash表各合適。

　　相對來說，hash_map是一個hashtable占用內(nèi)存更多，查找效率高一些，但是hash的時間比較費時。總體而言，hash_map 查找速度會比map快，而且查找速度基本和數(shù)據(jù)數(shù)據(jù)量大小無關(guān)，屬于常數(shù)級別;而map的查找速度是log(n)級別。并不一定常數(shù)就比log(n)小， hash還有hash函數(shù)的耗時，明白了吧，如果你考慮效率，特別是在元素達到一定數(shù)量級時，考慮考慮hash_map。但若你對內(nèi)存使用特別嚴(yán)格，希望程序盡可能少消耗內(nèi)存，那么一定要小心，hash_map可能會讓你陷入尷尬，特別是當(dāng)你的hash_map對象特別多時，你就更無法控制了，而且 hash_map的構(gòu)造速度較慢。

　　現(xiàn)在知道如何選擇了嗎?權(quán)衡三個因素: 查找速度, 數(shù)據(jù)量, 內(nèi)存使用。

　　紅黑樹的每個節(jié)點上的屬性除了有一個key、3個指針：parent、lchild、rchild以外，還多了一個屬性：color。它只能是兩種顏色：紅或黑。而紅黑樹除了具有二叉搜索樹的所有性質(zhì)之外，還具有以下4點性質(zhì)：

　　1. 根節(jié)點是黑色的。

　　2. 空節(jié)點是黑色的(紅黑樹中，根節(jié)點的parent以及所有葉節(jié)點lchild、rchild都不指向NULL，而是指向一個定義好的空節(jié)點)。

　　3. 紅色節(jié)點的父、左子、右子節(jié)點都是黑色。

　　4. 在任何一棵子樹中，每一條從根節(jié)點向下走到空節(jié)點的路徑上包含的黑色節(jié)點數(shù)量都相同。

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

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

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