作者chenbojyh (阿志)
看板Grad-ProbAsk
标题Re: [理工] [资结]2-3 tree的删除问题
时间Sun Jan 3 22:26:33 2010
※ 引述《chenbojyh (阿志)》之铭言：
※ 引述《GraffitiK (GraffitiK)》之铭言：
: 75
: / \
: 35 85
: / \ / \
: 15 50 80 96
: 请问像是以上这种2-3 tree，要删掉的node位置分别为75和35时，该怎麽操作呢？
: 谢谢！
删75
80 35,80
/ \ / │ \
35 85 -> 15 50 85,96
/ \ \
15 50 96
删35
35,80 80
/ │ \ -> / \
15 50 85,96 15,50 85,96
应该是这个样子.....
1F：推 polomoss:找左子最大~~或右子最小~~其他调整一样 01/03 13:46
2F：→ kkman0120:这样对嘛？看起来怪怪的 01/03 19:34
删35应该是这样才对
35,80 50,85
/ │ \ -> / │ \
15 50 85,96 15 80 96
sorry 之前写错
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.227.129.123
3F：推 GraffitiK:? 可是删35的部分我写的和之前的一样欸, 欲删的点若在非 01/03 23:47
4F：→ GraffitiK:叶节点的话, 先和左子树最大或右子树最小作交换, 再用删 01/03 23:47
5F：→ GraffitiK:leaf的方式删. 假设35和50交换之後, 15再和50 combine, 01/03 23:47
6F：→ GraffitiK:结果就变成像之前的那个答案.. 还是因为一定要先用 01/03 23:47
7F：→ GraffitiK:rotation的方式?? 01/03 23:48
8F：推 ck1115:可是如果再新增回去怎麽怪怪的 我错了吗? 01/04 00:02
9F：→ chenbojyh:我也在想 删35好像怪怪的 01/04 09:43
10F：推 kkman0120:我觉得一开始删75好像也怪怪的@@ 01/04 21:39