iT邦幫忙

2022 iThome 鐵人賽

DAY 14
0
Software Development

資料結構 - 我好想懂阿!30 天系列系列 第 14

資料結構 - 我好想懂阿!30 天系列 (14) - SMMH

  • 分享至 

  • xImage
  •  

定義

為一個 Completed B.T 且 root 為空,則滿足以下 3 個 path
p1. 左兄 ≤ 右兄
p2. 令 X 為某點,若此點有祖父,則祖父的左子點必須 ≤ X
p3. 令 X 為某點,若此點有祖父,則祖父的右子點必須 ≥ X
即代表整個 heap root 的左子為 min、右子為 max
https://ithelp.ithome.com.tw/upload/images/20220928/20151910tZz15voo4G.png
可以看到上圖的點 40,其有祖父(root),則祖父的左子點 (5) 會小於 40、右子點 (75) 會大於 40

Insert X

先放置到 Last node 下一個
check p1
check p2 調整至 SMMH
check p3 調整至 SMMH
不一定只調整一次
https://ithelp.ithome.com.tw/upload/images/20220928/20151910LL7xVclfLw.png
以插入 90 為例,由於他沒有右兄,所以不用換位置,然而其祖父之右子點 (40) 比起 90 還小,因此做第一回合交換
交換後發現其祖父之右子點 (75) 比起 90 還小,因此做第二回合交換

Delete Min

  1. 將 Root 左子刪除
  2. 將 The last node 刪除,令其為 X
  3. 放置 X 至 Root 左子依照 p1 p2 調整至 SMMH

https://ithelp.ithome.com.tw/upload/images/20220928/20151910PGg4ichYHz.png
欲刪除 5,將 last node 40 放入 root 之左子,由於左兄比右兄小,因此 p1 不用調整,當檢查 p2,發現 8 是要調整之最小點,予以交換

Delete Max

  1. 將 Root 右子刪除
  2. 將 the last node 刪除,令其為 X
  3. 放置 X 至 Root 右子依照 p1 p3 調整至 SMMH

https://ithelp.ithome.com.tw/upload/images/20220928/20151910fCsO6Cfqv7.png
欲刪除 90,將 last node 60 放入 root 之右子,由於左兄比右兄小,因此 p1 不用調整,當檢查 p3,發現 75 是要調整之最大點,予以交換


上一篇
資料結構 - 我好想懂阿!30 天系列 (13) - Deap
下一篇
資料結構 - 我好想懂阿!30 天系列 (15) - Extended Binary Tree
系列文
資料結構 - 我好想懂阿!30 天系列30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言