作者kaidi620 (万能史哥)
看板Grad-ProbAsk
标题[理工] 台大资工102 资演
时间Wed Jan 23 10:30:25 2019
不好意思 小弟又来打扰了 想请问几题
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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548210628.A.1E7.html
1F：推 FRAXIS: 1(a) 因为红黑树上的最长路径的长度最多是最短路径的两倍 01/23 12:33
2F：→ KWire: CLRS 16.3-2 跟这个几乎一样，可以去参考一下 01/26 05:28
3F：→ KWire: 概念是把子树往不 full 的节点移，就造出更短的编码了 01/26 05:32