[课业] 资料结构 红黑树

楼主: lei70200 (Lei)   2015-04-12 17:50:43
各位好,由于上完王老师函授的资结,对于上课所提及到的红黑树着墨甚少,
所以心中还是有不少疑问,首先附上范例图:
一颗红黑树如下
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
以下提出我的疑问:
(1)老师有说过可以利用2-3-4树推出红黑树(但是只做了插入就下课了...)
那么,删除红黑树的步骤是先将2-3-4树删除完后再转换成红黑树吗?
(2)承(1)如果是,由于2-3-4树的特性在删除之前可能会有值的位置变动,
这样的变动是不是会让红黑树为不唯一?如果不是,那么每个步骤该怎么做?(
比如说旋转的时机等等...)资质驽钝,看不出来两棵树在删除的时候
有什么关联OTL
(3)我有另外去用红黑树的正式规则做一次,但是做出来的结果与解答相去甚远,
再这样的差异下,考试的时候应该要以哪个为主?(感觉很吃运气....)
后面的红黑树整个就大爆炸阿...出了感觉就很不妙....
希望有精通此树的大大们可以为小的开释...
作者: emstarbucks (花榭清风)   2015-04-12 18:42:00
我都记这些= = 红兄 黑兄二黑姪 黑兄红姪双黑处理
作者: malowda (malowda)   2015-04-12 18:44:00
可以先把这棵的234树画出来吗
楼主: lei70200 (Lei)   2015-04-12 18:44:00
我也是用这推的,可是推出来的树长的完全不一样 囧马上来新增一下2-3-4树已补上
作者: malowda (malowda)   2015-04-12 19:17:00
你的7和10是不是画错了你不是以小的值当父亲NODE吗
作者: kafka0829 (卡夫卡)   2015-04-12 19:21:00
你可以将书上每步的红黑树转回2-3-4树再比对自己作删除时的2-3-4树是否一样我当时是卡在删除16,因为17是2node要先对他处理才能删
作者: malowda (malowda)   2015-04-12 19:47:00
我是习惯用234树来做直接用红黑树来做红黑要变来变去会搞乱
作者: kafka0829 (卡夫卡)   2015-04-12 20:00:00
3node(6,7)本来就两种画法,看你要哪边先写都可以
作者: malowda (malowda)   2015-04-12 20:04:00
要画那一种全部要统一不是一个节点以小的另一个以大的否则会有很多种
作者: kafka0829 (卡夫卡)   2015-04-12 20:05:00
推楼上要统一~看是哪边要先画~
楼主: lei70200 (Lei)   2015-04-12 20:13:00
嗯嗯 了解!

Links booklink

Contact Us: admin [ a t ] ucptt.com