Re: [课业] 资料结构 红黑树

楼主: malowda (malowda)   2015-04-12 19:42:12
※ 引述《lei70200 (客家一哥)》之铭言:
: 各位好,由于上完王老师函授的资结,对于上课所提及到的红黑树着墨甚少,
: 所以心中还是有不少疑问,首先附上范例图:
: 一颗红黑树如下
: 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
我以234树来说
15
: / \
: 6,12 17,20
: / | \ / | \
: 3 7,10 13 16 18 23
删10
15
: / \
: 6,12 17,20
: / | \ / | \
: 3 7 13 16 18 23
删18
15
: / \
: 6,12 17
: / | \ / |
: 3 7 13 16 20,23
删3
15
: / \
: 12 17
: / \ / \
: 6,7 13 16 20,23
删16
15
: / \
: 12 20
: / \ / \
: 6,7 13 17 23
删13
15
: / \
: 7 20
: / \ / \
: 6 12 17 23
删12
: 15 20
: / | \
: 6,7 17 23
删17
7,20
: / | \
: 6 15 23
再来就以小的值做为父亲节点转红黑树
7
: / \
: 6 20
: / \
: 15 23
就得到大大你PO的解答
以上个人的想法如有错请其他大大指教
楼主: malowda (malowda)   2015-04-12 19:44:00
不太会用颜色所以没表现出7和20之间是红色的
作者: lei70200 (Lei)   2015-04-12 19:56:00
谢谢!!! 这样看起来清楚多了@@!!!
作者: kafka0829 (卡夫卡)   2015-04-12 20:04:00
我234树删16那边和你不太一样耶.我root会变(12,15,20)
楼主: malowda (malowda)   2015-04-12 20:06:00
删16后原本16的右兄弟还有2个值也就要把17向下移,20向上移,还达不到要降阶的条件
作者: kafka0829 (卡夫卡)   2015-04-12 20:09:00
可我看书上步骤~除root外,遇到2node要先转成3或4node
楼主: malowda (malowda)   2015-04-12 20:11:00
没错阿你要先把20移上去和17成为17,20这样就是书上说的再向17,20借17向下移
作者: kafka0829 (卡夫卡)   2015-04-12 20:28:00
疑?所以他不是指搜寻的路上有遇到2node要先处理?而是找到要删除的元素再判断?
作者: lei70200 (Lei)   2015-04-12 20:32:00
搜寻的路上有遇到就要先处理没错两位大大都没错,只是删16跟删13的图错了
作者: APE36 (PT乡民)   2015-04-12 20:46:00
k大的比较没问题,那是王老师的版本...
楼主: malowda (malowda)   2015-04-12 21:14:00
B树是要删除的节点到树根没有办法借(都只有1个KEY)才会向下降一阶,这题还有一个节点有2个KEY怎么会就降阶
作者: kafka0829 (卡夫卡)   2015-04-12 21:25:00
不知道是否为top-down 2-3-4树和n-way树差别吗?topdown作法可避免backward restructuring path
楼主: malowda (malowda)   2015-04-13 11:08:00
k大你有看王老师的资料结构11-57(2014)delete有分三种情况,(1)sibling为2个node(分支为2)才和兄弟合并,(2)(3)都是兄弟有3或以上的node会先借1个来,所以我的删16和13没错,你的2node是指节点内的2个值吧
作者: kafka0829 (卡夫卡)   2015-04-13 12:14:00
是使用第(1)个情况没错呀~同你的图要删16的2-3-4树17为2node他的兄弟12也为2node所以合并变成(12,15,17)之后作删除16动作,root就会变成(12,15,20)过程是这样:http://i.imgur.com/VA60fs8.jpg不知道步骤是否有错~ 但参考步骤红黑树转回的2-3-4树应该是会长这样~ 有错再请高手补充...
楼主: malowda (malowda)   2015-04-13 14:55:00
错了,你删16要先看他的兄弟,不是先看父节点(17)(1)的情况是p为树叶,这题带(1)的话p指的是17那个它不是树叶
作者: kafka0829 (卡夫卡)   2015-04-13 15:08:00
这边的(1)是你回文的情况(1)=书上的(3)-①然后是依序往下处理q=17 p=parent=15所以使用3-1的casedownward pass,p与q是会移动的,当遇到2node先处理因为书上有些模糊,我有特地google找一些教材参考这张图说明的满清楚的:http://i.imgur.com/AYsjXfP
楼主: malowda (malowda)   2015-04-13 15:21:00
又不是要删17你q指向17对吗?第1个条件p有2个node则p为
作者: kafka0829 (卡夫卡)   2015-04-13 15:21:00
图中的第三点刚好就是此种情况q先指17确认不是2node才往下啊
楼主: malowda (malowda)   2015-04-13 15:22:00
root你觉得用你做的方式这个条件合吗?
作者: kafka0829 (卡夫卡)   2015-04-13 15:24:00
他不是root一开始q为15为2node->root情况排除 往下17为2node处理看那张投影片,我的理解是这样啦~
楼主: malowda (malowda)   2015-04-13 15:30:00
这个是刚好3层,如果是4层你不就要从第2层开始向下合并?
作者: kafka0829 (卡夫卡)   2015-04-13 15:30:00
投影片2的意思就表示遇到2node要先处理,而不是直接就是指到欲删除的元素应该不会有你说的情况应该没有第二层2node第三层也2node的case吧所以会到第三层,然后处理情况又和本题一样了
作者: lei70200 (Lei)   2015-04-13 15:58:00
k大讲得很对呀~先遇到2node先处理,全部处理完后再删除之后就停止做动作这样才符合Forward deletion,层层往下处理的意义
作者: kafka0829 (卡夫卡)   2015-04-13 16:04:00
我上面讲得有点跳:我的意思是指第二层和第三层若同为2node则因为第二层已和root合并,所以原来第三层会变成就会变成4个兄弟所以不会出现bug问题

Links booklink

Contact Us: admin [ a t ] ucptt.com