各位安安
洪毅老师说红黑树的插入规则其中一项
Insert一个新值 在search过程中所经的Node若遇
两子点皆红需color change 和 连续红色Nodes需要做rotation
然后这种情况每插入一次顶多发生一次
回家练习到有个例子 插入18做完后 接着插入2
search Node的过程中发生两次cc的状况
前面的步骤来回检查也都有符合红黑树的定义
https://imgur.com/5YEylk4
是我误会老师的意思吗? 第一次发文 小弟不才请大大们帮我解答
color change本来就可能发生很多次 是rotation只会发生一次不过这边要劝世一下 洪毅教的是红黑树的top down insert, 其实很冷门 洪毅选择这样教的原因是比较好教但圣经本CLRS用的是bottom up insert，两者有什么差吗？有，印象中交大曾经考过一题红黑树 insert，用top down跟bottom up做出来的答案不一样 而交大那年给的答案是用bottom up做出来的结果而且事实上大部分的学校都是用CLRS的定义，所以建议趁早把top down insert忘掉 网络上有很多红黑树insert的教学都不错 可以参考看看事实上bottom up insert只需考虑uncle为红 跟uncle为黑两种情况 一点都没有比较难
color change本来就可能发生很多次 是rotation只会发生一次不过这边要劝世一下 洪毅教的是红黑树的top down insert, 其实很冷门 洪毅选择这样教的原因是比较好教但圣经本CLRS用的是bottom up insert，两者有什么差吗？有，印象中交大曾经考过一题红黑树 insert，用top down跟bottom up做出来的答案不一样 而交大那年给的答案是用bottom up做出来的结果而且事实上大部分的学校都是用CLRS的定义，所以建议趁早把top down insert忘掉 网络上有很多红黑树insert的教学都不错 可以参考看看事实上bottom up insert只需考虑uncle为红 跟uncle为黑两种情况 一点都没有比较难
楼主: g2578141 (CJR) 2020-04-28 12:16:00
原来如此！那我会在去查查bottom up的插入法 谢谢mi大的解释
作者:
zuchang (chang)
2020-04-29 16:34:00以top down来讲 20插入就好了 不用回头检查
作者: Handsomeshen (洗澡是肮脏人的事) 2020-05-03 03:42:00
可以去youtube找教学，有人画例子会比较好懂