作者malowda (malowda)
看板Examination
標題Re: [課業] 資料結構 紅黑樹
時間Sun Apr 12 19:42:12 2015
※ 引述《lei70200 (客家一哥)》之銘言: : 各位好,由於上完王老師函授的資結,對於上課所提及到的紅黑樹著墨甚少, : 所以心中還是有不少疑問,首先附上範例圖: : 一顆紅黑樹如下 : 15 : / \ : 6 17 : / \ / \ : 3 12 16 20 : / \ / \ : 10 13 18 23 : / : 7 : 補上其最初2-3-4樹如下 : 15 : / \ : 6,12 17,20 : / | \ / | \ : 3 7,10 13 16 18 23 : 其中節點7、12、20 為紅色節點,請一步步刪除圖中節點, : 依序為10、18、3、16、13、12、17 : 最後的解答為 : 7 : / \ : 6 20 : / \ : 15 23 我以234樹來說 15
: / \ : 6,12 17,20 : / | \ / | \ : 3 7,10 13 16 18 23 刪10 15
: / \ : 6,12 17,20 : / | \ / | \ : 3 7 13 16 18 23 刪18 15
: / \ : 6,12 17 : / | \ / | : 3 7 13 16 20,23 刪3 15
: / \ : 12 17 : / \ / \ : 6,7 13 16 20,23 刪16 15
: / \ : 12 20 : / \ / \ : 6,7 13 17 23 刪13 15
: / \ : 7 20 : / \ / \ : 6 12 17 23 刪12
: 15 20 : / | \ : 6,7 17 23 刪17 7,20
: / | \ : 6 15 23 再來就以小的值做為父親節點轉紅黑樹 7
: / \ : 6 20 : / \ : 15 23 就得到大大你PO的解答 以上個人的想法如有錯請其他大大指教 --
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.141.73.131 ※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1428838934.A.241.html
→ malowda: 不太會用顏色所以沒表現出7和20之間是紅色的 04/12 19:44
推 lei70200: 謝謝!!! 這樣看起來清楚多了@@!!! 04/12 19:56
→ kafka0829: 我234樹刪16那邊和你不太一樣耶.我root會變(12,15,20) 04/12 20:04
→ malowda: 刪16後原本16的右兄弟還有2個值也就要把17向下移,20向上 04/12 20:06
→ malowda: 移,還達不到要降階的條件 04/12 20:07
推 kafka0829: 可我看書上步驟~除root外,遇到2node要先轉成3或4node 04/12 20:09
→ malowda: 沒錯阿你要先把20移上去和17成為17,20這樣就是書上說的再 04/12 20:11
→ malowda: 向17,20借17向下移 04/12 20:12
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers.
留言列表