[理工]资结 2-3 tree
楼主: maque (Roadside) 2014-11-18 21:11:29
题目如下
![]()
![]()
有问题在于第二小题，删除部分
第一次删除30在root部分应该可以选择35作为root吧?
第二次删除7照原解没有疑问，
第三次删除18，自己是这样想的，
因无法做旋转只能合并，父节点16拉下来作合并，
父节点overflow，则拉祖父节点19下来，变成root为overflow，
等同删除root，从右子树找最小值22拉上来。
麻烦解答了!感谢
有问题在于第二小题，删除部分
第一次删除30在root部分应该可以选择35作为root吧?
第二次删除7照原解没有疑问，
第三次删除18，自己是这样想的，
因无法做旋转只能合并，父节点16拉下来作合并，
父节点overflow，则拉祖父节点19下来，变成root为overflow，
等同删除root，从右子树找最小值22拉上来。
麻烦解答了!感谢
作者: kather (Kather) 2014-11-18 22:01:00
第三次删除18 父节点拉下来后underflow=>可以rotation可以rotation就rotation 0.0 不能才尝试combination而第一题中 Horowitz书内的deletion是先看有没有右边sibling 有的话看他能不能rotation能则rotation 不能则把该node 右边sibling combine也就是说是先考虑与右边合并只不过你要写成先考虑跟左边合并也是可以啦....他那个答案跟右边的合并应该是根据这个来的
楼主: maque (Roadside) 2014-11-19 19:19:00
明白了!谢谢!