Re: [理工] [DS]成大99-電通甲
※ 引述《ybite (小犬)》之銘言：
: ※ 引述《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
題目不是要求delete min後的結果嗎....
_
/ \
6 33
/ \ / \
12 25 8 9
/ \ /
14 17 16
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 122.118.65.75
→
02/08 06:59, , 1F
02/08 06:59, 1F
→
02/08 10:13, , 2F
02/08 10:13, 2F
討論串 (同標題文章)