數(shù)據(jù)結(jié)構(gòu)第九章ppt課件-資料下載頁
2025-04-30 18:12本頁面
【正文】 m) 其中其中 Ki Ki+1, 1 ? i m 這時必須把結(jié)點這時必須把結(jié)點 p分裂成兩個結(jié)點分裂成兩個結(jié)點 p和和 q,它們包含的它們包含的信息分別為：信息分別為： 結(jié)點結(jié)點 p：： ( ?m/2? 1, P0, K1, P1, ……, K?m/2? 1, P?m/2? 1) 結(jié)點結(jié)點 q：： (m ?m/2?, P?m/2?, K?m/2?+1, P?m/2?+1, ……, Km, Pm) 位于中間的關(guān)鍵碼位于中間的關(guān)鍵碼 K?m/2? 與指向新結(jié)點與指向新結(jié)點 q 的指針形的指針形成一個二元組成一個二元組 ( K?m/2?, q ),插入到這兩個結(jié)點的插入到這兩個結(jié)點的 雙親雙親結(jié)點結(jié)點 中去中去 .40結(jié)點 “分裂 ”的示例 41. B樹上的 插入示例 :從空樹開始逐個加入關(guān)鍵碼53,75,139,49,145,36,101建立 3階 B樹 .42.若設(shè) B樹的高度為 自頂向下 搜索到 葉結(jié)點 的過程中需要進(jìn)行 h次讀盤 ..在插入新關(guān)鍵碼時 ,需要自底向上分裂結(jié)點 ,最壞情況下從被插關(guān)鍵碼所在葉結(jié)點到根的路徑上的所有結(jié)點都要分裂 .43.B樹上的 刪除.在 B樹上刪除一個關(guān)鍵碼時 ,首先需要找到這個關(guān)鍵碼所在的結(jié)點 ,從中刪去這個關(guān)鍵碼 ..若該結(jié)點不是葉結(jié)點 ,且被刪關(guān)鍵碼為 Ki,1 ? i ? n,則在刪去該關(guān)鍵碼之后 ,應(yīng)以該結(jié)點 Pi 所指示子樹中的最小關(guān)鍵碼 x來代替被刪關(guān)鍵碼 Ki 所在的位置 ,然后在 x所在的葉結(jié)點中刪除 x..在葉結(jié)點上刪除有 4種情況 :1)被刪關(guān)鍵碼所在葉結(jié)點同時又是根結(jié)點且刪除前該結(jié)點中關(guān)鍵碼個數(shù) n ? 2,則直接刪去該關(guān)鍵碼并將修改后的結(jié)點寫回磁盤 .442)被刪關(guān)鍵碼所在葉結(jié)點不是根結(jié)點且刪除前該結(jié)點中關(guān)鍵碼個數(shù) n ? ?m/2?,則直接刪去該關(guān)鍵碼并將修改后的結(jié)點寫回磁盤 ,刪除結(jié)束 .453)被刪關(guān)鍵碼所在葉結(jié)點刪除前關(guān)鍵碼個數(shù) n = ?m/2? 1,若這時與該結(jié)點相鄰的右兄弟 (或左兄弟 ) 結(jié)點的關(guān)鍵碼個數(shù) n ? ?m/2?，則可按以下步驟調(diào)整該結(jié)點 ,右兄弟 (或左兄弟 ) 結(jié)點以及其雙親結(jié)點 ,以達(dá)到新的平衡。.將雙親結(jié)點中剛剛大于 (或小于 ) 該被刪關(guān)鍵碼的關(guān)鍵碼 Ki (1 ? i ? n) 下移；.將右兄弟 (或左兄弟 ) 結(jié)點中的最小 (或最大 )關(guān)鍵碼上移到雙親結(jié)點的 Ki 位置；.將右兄弟 (或左兄弟 ) 結(jié)點中的最左 (或最右 ) 子樹指針平移到被刪關(guān)鍵碼所在結(jié)點中最后 (或最前 ) 子樹指針位置；.在右兄弟 (或左兄弟 ) 結(jié)點中 ,將被移走的關(guān)鍵碼和指針位置用剩余的關(guān)鍵碼和指針填補 ,調(diào)整 .再將結(jié)點中的關(guān)鍵碼個數(shù)減 1.4647484)被刪關(guān)鍵碼所在葉結(jié)點刪除前關(guān)鍵碼個數(shù) n = ?m/2? 1,若這時與該結(jié)點相鄰的右兄弟 (或左兄弟 ) 結(jié)點的關(guān)鍵碼個數(shù) n = ?m/2? 1,則必須按以下步驟合并這兩個結(jié)點 ..將 雙親結(jié)點 p 中相應(yīng)關(guān)鍵碼下移到選定保留的結(jié)點中 ..若要合并 p 中的子樹指針 Pi 與 Pi+1 所指的結(jié)點 ,且保留 Pi 所指結(jié)點 ,則把 p 中的關(guān)鍵碼 Ki+1下移到 Pi 所指的結(jié)點中 .. 把 p 中子樹指針 Pi+1 所指結(jié)點中的全部指針和關(guān)鍵碼都照搬到 Pi 所指結(jié)點的后面 .刪去 Pi+1 所指的結(jié)點 ..在結(jié)點 p中用后面剩余的關(guān)鍵碼和指針填補關(guān)鍵碼 Ki+1 和指針 Pi+1..修改結(jié)點 p和選定保留結(jié)點的關(guān)鍵碼個數(shù) ..在合并結(jié)點的過程中 ,雙親結(jié)點中的關(guān)鍵碼個數(shù)減少了 .49.若雙親結(jié)點是根結(jié)點且結(jié)點關(guān)鍵碼個數(shù)減到 0，則該雙親結(jié)點應(yīng)從樹上刪去 ,合并后保留的結(jié)點成為新的根結(jié)點 。否則將雙親結(jié)點與合并后保留的結(jié)點都寫回磁盤 ,刪除處理結(jié)束 ..若雙親結(jié)點不是根結(jié)點 ,且關(guān)鍵碼個數(shù)減到 ?m/2? 2,又要與它自己的兄弟結(jié)點合并 ,重復(fù)上面的合并步驟 .最壞情況下這種結(jié)點合并處理要自下向上直到根結(jié)點 .50515253545556
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1