Re: [理工] [DS]成大99-電通甲
※ 引述《aerystyle (阿che)》之銘言：
: 輸入:12.8.14.17.9.6.3.33.25.16
: 求SMMH結果?
: _
: / \
: 3 33
: / \ / \
: 6 25 8 9
: / \ / \
: 12 14 16 17
: 這是我的答案,_代表空NODE，請各位高手幫我檢查一下是否有誤，謝謝
算了，寫下來好了。
SMMH的性質：
* Root放空
* 任何一個節點的左子樹比右子樹小
* 對某個節點而言，考慮以此節點為根的子樹
根的左子樹擁有樹根所有後代中最小的值（所以不考慮樹根）
根的右子樹擁有樹根所有後代中最大的值（一樣不考慮樹根）
舉例：整顆樹的值都介於3～33，以3為根的子樹除了3以外都介於6～25。
因此在整個SMMH過程中都必須維持三個性質：
P1. 如果某個節點有兄弟，左兄弟<右兄弟
P2. 如果某個節點有祖父，祖父的左兒子<該節點
P3. 如果某個節點有祖父，祖父的右兒子>該節點
插入時：
1. 先放在整顆 Heap 中最「後面」的位置（最後一層最右邊）
2. 如果他有左兄弟而且比他大（不滿足P1），交換左右兄弟
3. 由下往上檢查新節點祖父的左兒子和祖父的右兒子
如果新節點比祖父的左兒子小（不滿足P2），兩點交換
如果新節點比祖父的右兒子大（不滿足P3），兩點交換
在同時滿足P2和P3性質過後就算插入完成
Delete-min或Delete-max：
1. 把Heap最後一層最右邊的值拿去補要刪掉的值
2. 由上而下重新檢查P2和P3性質（類似上者）
有些書/講義會特別用「E」表示要插入/遞補的新節點...
在大小檢查完之後，最後再把E填上數字，這種表記方式好像還蠻常見的？
ok，所以原題是要輸入:12.8.14.17.9.6.3.33.25.16
插入12
_
/
12
插入8，此時違反P1規則，交換左右：
_ -
/ \ → / \
12 8 8 12
插入14，但此時14比12更大，交換：
_ -
/ \ / \
8 12 → 8 14
/ /
14 12
插入17，此時17比14還大，交換：
_ -
/ \ / \
8 14 → 8 17
/ \ / \
12 17 12 14
插入9，由於9位在8～17之間，沒問題：
_
/ \
8 17
/ \ /
12 14 9
插入6，首先由於左兄弟比較大，交換左右：
然後因為6比8還要小，因此交換:
_ _ _
/ \ / \ / \
8 17 → 8 17 → 6 17
/ \ / \ / \ / \ / \ / \
12 14 9 6 12 14 6 9 12 14 8 9
插入3：此時3比12還小，交換
再往上一層後，3還是比6小，再換：
_ _ _
/ \ / \ / \
6 17 → 6 17 → 3 17
/ \ / \ / \ / \ / \ / \
12 14 8 9 3 14 8 9 6 14 8 9
/ / /
3 12 12
插入33：此時33比14還大，交換
再往上一層後，33還是比17大，再換：
_ _ _
/ \ / \ / \
3 17 → 3 17 → 3 33
/ \ / \ / \ / \ / \ / \
6 14 8 9 6 33 8 9 6 17 8 9
/ \ / \ / \
12 33 12 14 12 14
插入25：25比17大，交換。交換之後25位在3～33之間，沒問題！
_ _
/ \ / \
3 33 3 33
/ \ / \ → / \ / \
6 17 8 9 6 25 8 9
/ \ / / \ /
12 14 25 12 14 17
插入16：左兄弟比他大，左右交換。
_
/ \
3 33
/ \ / \
6 25 8 9
/ \ / \
12 14 17 16
交換過後16位在6～25之間，沒問題！因此做完就是這樣：
_
/ \
3 33
/ \ / \
6 25 8 9
/ \ / \
12 14 16 17
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.127.180.129
推
02/07 11:24, , 1F
02/07 11:24, 1F
推
02/07 11:59, , 2F
02/07 11:59, 2F
推
02/07 12:09, , 3F
02/07 12:09, 3F
推
02/07 15:37, , 4F
02/07 15:37, 4F
推
02/07 23:06, , 5F
02/07 23:06, 5F
推
02/07 23:27, , 6F
02/07 23:27, 6F
推
02/07 23:36, , 7F
02/07 23:36, 7F
→
02/09 00:19, , 8F
02/09 00:19, 8F
推
02/23 19:18, , 9F
02/23 19:18, 9F
推
02/25 21:58, , 10F
02/25 21:58, 10F
推
12/29 00:17, , 11F
12/29 00:17, 11F
推
01/09 19:55, , 12F
01/09 19:55, 12F
討論串 (同標題文章)