推 FRAXIS: 1(a) 因為紅黑樹上的最長路徑的長度最多是最短路徑的兩倍 01/23 12:33
→ KWire: CLRS 16.3-2 跟這個幾乎一樣，可以去參考一下 01/26 05:28
→ KWire: 概念是把子樹往不 full 的節點移，就造出更短的編碼了 01/26 05:32
不好意思 小弟又來打擾了 想請問幾題
https://imgur.com/7lgerGs.jpg
(1)a小题 不知道小弟的答案是否正確 小弟的答案：
若只對internal node做color changing則可以分為
1.若樹根的左兒和右兒皆為紅色，則做一次color changing樹根必為紅
色，最後還是要進行修正為黑色
2.若樹根的左(右)兒和左(右)子孫為連續紅點，則進行color changing
還是得讓樹根在進行修正為黑色
(2)b小題 小弟完全不懂怎麼把binary tree轉為red black tree 可以請大神畫給我嗎
希望步驟詳細一點 謝謝大神
https://imgur.com/UJbqibk.jpg
(3)想請問一下 (a)小題要怎麼證明呢? 小弟以往碰到的都是binary tree 所以很頭痛
感謝大神們
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 163.13.17.107
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548210628.A.1E7.html