作者SPYKER (成功客)
站内Grad-ProbAsk
标题Re: [问题] 2-3 tree
时间Thu Mar 19 01:14:05 2009
※ 引述《wagaru (wagaru)》之铭言：
: 考试都考到现在了，还问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 应该不符定义才对…
: 请问上面的步骤是哪里错了呢？
: 谢谢~
step 1 combination 父破产 去键结
31
/ \
/ \
/ \
21 47
/ \ / \
/ \ / \
/ \ / \
(15 , 19) 空 43 50
/ \ / \
/ \ / \
(10,12) 18 20 (22,24) 33 45 48 52
step 2 rotation
31
/ \
/ \
/ \
19 47
/ \ / \
/ \ / \
/ \ / \
15 21 43 50
/ \ / \
/ \ / \
(10,12) 18 20 (22,24) 33 45 48 52
step 3 连回
31
/ \
/ \
/ \
19 47
/ \ / \
/ \ / \
/ \ / \
15 21 43 50
/ \ / \ / \ / \
/ \ / \ / \ / \
(10,12) 18 20 (22,24) 33 45 48 52
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 124.218.131.186