heap、2-3-4樹、紅黑樹、hash算法介紹

《heap、2-3-4樹、紅黑樹、hash算法介紹》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、Heap、2-3-4樹、紅黑樹、hash算法介紹中國人壽梁如見liangrujian@gmail.com201305排序和查找排序算法數(shù)組排序：quick、merge、heap樹排序：AVL、B(2-3-4)、red-blackHash排序動態(tài)、靜態(tài)分類靜態(tài)：quick、merge動態(tài)：heap、樹排序、hashOracle是用hash、B-tree堆出來的heap性質(zhì)：完全二叉樹最大堆中每個節(jié)點都比兒節(jié)點大，根節(jié)點最大。最小堆則是每個節(jié)點比兒節(jié)點小。適合優(yōu)先隊列：輸出優(yōu)先級最大或最小的不采用鏈表結(jié)構(gòu)，采用數(shù)組實現(xiàn)，

2、算法簡單堆上下有序，左右無序堆排序本身不保存排序好的結(jié)果，仍需要用數(shù)組來存放結(jié)果數(shù)據(jù)。所以，無法在堆上進行查找，也無法刪除指定關(guān)鍵字用java實現(xiàn)時，可以動態(tài)擴大規(guī)模。如果用c實現(xiàn)，可以采取申請擴大一倍的數(shù)組，然后遷移數(shù)據(jù)。heap插入：放在最后，然后向上比較、交換直到已符合堆性質(zhì)摘?。赫oot，把最后一個數(shù)放入root，然后向下比較、交換直到已符合堆性質(zhì)2-3-4tree性質(zhì)：234指一個節(jié)點可能含有的子節(jié)點的個數(shù)每個節(jié)點存放1-3個值，2-4個指針只能在葉子上插入中間結(jié)點也存放數(shù)據(jù)全樹有序，葉子等高可通過先序

3、遍歷輸出排序結(jié)果可實現(xiàn)優(yōu)先隊列，查找最優(yōu)節(jié)點并刪除2-3-4tree插入，必須在葉子上進行：從根向下找位置，遇到3值即拆為2節(jié)點（騰出空位），增加父親值（父親原先值非3有空缺）刪除：刪非頁節(jié)點，則繼續(xù)找到葉子為止，交換上來；如刪頁節(jié)點，則找到就行。如果找的過程中碰到1值則進行轉(zhuǎn)換擴值，根例外（根會被葉子搞定）1、如果兄弟有多值，通過父親交換到這邊，擴自己2、如果兄弟也1值，從父親拉下一個，變?yōu)?值。父親應(yīng)該非1值。parent如果是根，且為1值，則變短。red-blacktree性質(zhì)：1)、Anodeiseither

4、redorblack.每個結(jié)點要么是紅的，要么是黑的。2)、Therootisblack.根結(jié)點是黑的。3)、Allleaves(NIL)areblack.葉節(jié)點是黑的。4)、Bothchildrenofeveryrednodeareblack.如果一個結(jié)點是紅的，那么它的子節(jié)點必須是黑的。5)、Everysimplepathfromagivennodetoanyofitsdescendantleavescontainsthesamenumberofblacknodes.從任何給定節(jié)點到葉節(jié)點的每條路徑都包含相同數(shù)目

5、的黑結(jié)點。只能在葉子上插入紅節(jié)點中間結(jié)點也存放數(shù)據(jù)全樹有序可通過先序遍歷輸出排序結(jié)果可實現(xiàn)優(yōu)先隊列，查找最優(yōu)節(jié)點并刪除紅黑樹從根到葉子，如果全為黑最短，黑紅相間最長，長度最多相差一倍，基本平衡。red-blacktree插入：只用紅節(jié)點插入到葉子1)、如果是根，改為黑即可，否則去22)、如果父親是黑，OK，否則去33)、如果叔叔也是紅，則如下圖，改變顏色，對G節(jié)點回1；否則表示叔叔為黑色，去4下面4和5僅顯示P為G左兒子的情況，如果P為G右兒子則4為右旋5為左旋。4)、如果N為P的右兒子，左旋，去5，否則直接去55)

6、、右旋，OKred-blacktree刪除，首先是把左鄰（最接近被刪數(shù)）或右鄰交換上來（交換不影響紅黑樹性質(zhì)），然后把被交換的節(jié)點刪除。被交換的節(jié)點要么是葉子，要么只有一個兒子。刪除問題演變成刪除一個最多只有一個兒節(jié)點C的節(jié)點M的問題。幾種形態(tài)：（2*3，M紅或黑，C無、紅或黑，紅紅不符樹性質(zhì)）1、M紅，無C，直接刪除M即可2、M紅，C黑，實際上2和1是一樣的，該C只能是nil，否則長度不等3、M黑，無C4、M黑，C紅，C下不能再有兒子，該情況簡單，刪除黑節(jié)點，把子節(jié)點改為黑色即可5、M黑，C黑，實際上5和3是一樣的

7、，該C只能是nil，否則長度不等問題繼續(xù)演變?yōu)閯h除黑色葉子節(jié)點的問題如果是根，直接刪除，后面不討論red-blacktree刪除續(xù)1一棵這樣的樹：N為刪后高度減1的子樹（初始時即為nil節(jié)點），P為父親，S為兄弟（肯定有，因N原先為黑，S及其兒子必須有一黑）如何保持S這邊高度不變，但N這邊高度補回1初始狀態(tài)下，刪除N后則只剩P、S及S的兒、孫節(jié)點。初始狀態(tài)（2*2*?*?，P紅或黑，S紅或黑，S的兒子？S的孫子？）case1、P紅S黑，該情況比較簡單，因為N原高度為1，決定了S的兒子空或紅，S沒有孫節(jié)點刪除N后只有2

8、-4個節(jié)點，比較容易安排，2則父為黑，3-4則父為紅case2、P黑S紅，S有兩黑兒子，S可能有紅孫子可以轉(zhuǎn)換為case1case3、P黑S黑，S可能有紅兒子刪除N后的節(jié)點數(shù)量有2-4個節(jié)點，3或4個節(jié)點兩層黑好安排，2個節(jié)點時必須用到爺爺節(jié)點了，直接把S置為紅色，然后把P（黑）作為N節(jié)點針對剛才三種情況進行轉(zhuǎn)化（剛才是N變短，現(xiàn)在是P變短了）