各位好,由于上完王老师函授的资结,对于上课所提及到的红黑树着墨甚少,
所以心中还是有不少疑问,首先附上范例图:
一颗红黑树如下
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)我有另外去用红黑树的正式规则做一次,但是做出来的结果与解答相去甚远,
再这样的差异下,考试的时候应该要以哪个为主?(感觉很吃运气....)
后面的红黑树整个就大爆炸阿...出了感觉就很不妙....
希望有精通此树的大大们可以为小的开释...