作者wagaru (wagaru)
看板Grad-ProbAsk
标题[问题] 2-3 tree
时间Thu Mar 19 00:34:27 2009
考试都考到现在了，还问2-3tree似乎有点蠢…
31
/ \
/ \
/ \
21 47
/ \ / \
/ \ / \
/ \ / \
(15 , 19) 24 43 50
/ | \ / \ / \ / \
/ | \ / \ / \ / \
(10,12) 18 20 22 30 33 45 48 52
现在要删除30…
我的算法是，因为无法rotation，所以要combination，把24拿下来
所以24现在是空的，进行rotation，19上去，21下来
那现在15这个node，会有三个child node 应该不符定义才对…
请问上面的步骤是哪里错了呢？
谢谢~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.91.160
1F：推 SPYKER:同学你确定你是113的吗? 03/19 00:40
2F：推 elfkiller:上面没错 20会跟着21接到另外一边 03/19 00:41
3F：推 ixjnpns:怎麽会有人不回答还反呛呢 = =? 03/19 00:45
4F：推 SPYKER:定义没错阿 2-3树 2<=degree<=3 03/19 00:46
5F：推 SPYKER:sorry! 应该说是父节点破产 要先去键结 所以20应该接在 03/19 00:57
6F：推 erictku:楼上 1父点怎麽接3子点..要2父点才能接3子点好吗 = = 03/19 00:57
7F：→ SPYKER:(20,21) 03/19 00:57
8F：→ erictku:给原po:你用BST的概念去想 20比19大 所以也会被移到右边 03/19 00:58
9F：→ SPYKER:误 (21,22) 下接20 22 30 03/19 00:59