作者g2578141 (CJR)
看板Grad-ProbAsk
标题[理工] 资演 红黑树插入
时间Sun Apr 26 23:41:42 2020
各位安安
洪毅老师说红黑树的插入规则其中一项
Insert一个新值 在search过程中所经的Node若遇
两子点皆红需color change 和 连续红色Nodes需要做rotation
然後这种情况每插入一次顶多发生一次
回家练习到有个例子 插入18做完後 接着插入2
search Node的过程中发生两次cc的状况
前面的步骤来回检查也都有符合红黑树的定义
https://imgur.com/5YEylk4
是我误会老师的意思吗? 第一次发文 小弟不才请大大们帮我解答
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.228.242.143 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1587915708.A.170.html
※ 编辑: g2578141 (36.228.242.143 台湾), 04/26/2020 23:46:16
1F：推 mi981027: color change本来就可能发生很多次 是rotation只会发生 04/28 05:24
2F：→ mi981027: 一次 04/28 05:24
3F：→ mi981027: 不过这边要劝世一下 洪毅教的是红黑树的top down insert 04/28 05:24
4F：→ mi981027: , 其实很冷门 洪毅选择这样教的原因是比较好教 04/28 05:24
5F：→ mi981027: 但圣经本CLRS用的是bottom up insert，两者有什麽差吗？ 04/28 05:24
6F：→ mi981027: 有，印象中交大曾经考过一题红黑树 insert，用top down 04/28 05:24
7F：→ mi981027: 跟bottom up做出来的答案不一样 而交大那年给的答案是 04/28 05:24
8F：→ mi981027: 用bottom up做出来的结果 04/28 05:24
9F：→ mi981027: 而且事实上大部分的学校都是用CLRS的定义，所以建议趁 04/28 05:24
10F：→ mi981027: 早把top down insert忘掉 网路上有很多红黑树insert的 04/28 05:24
11F：→ mi981027: 教学都不错 可以参考看看 04/28 05:24
12F：→ mi981027: 事实上bottom up insert只需考虑uncle为红 跟uncle为黑 04/28 05:24
13F：→ mi981027: 两种情况 一点都没有比较难 04/28 05:24
14F：→ g2578141: 原来如此！那我会在去查查bottom up的插入法 谢谢mi大 04/28 12:16
15F：→ g2578141: 的解释 04/28 12:16
16F：推 zuchang: 以top down来讲 20插入就好了 不用回头检查 04/29 16:34
17F：推 Handsomeshen: 可以去youtube找教学，有人画例子会比较好懂 05/03 03:42