[理工] 102台大电机资结 howard31622 PTT批踢踢实业坊

楼主: howard31622 (howard) 2017-12-18 17:35:59

https://i.imgur.com/xLhMh0A.jpg
因为没有答案
所以想问看看大家这题这样写对吗？

作者: sarsman (DeNT15T♠) 2017-12-18 17:47:00

最后不用把5拉上去吧

楼主: howard31622 (howard) 2017-12-18 17:53:00

题目说root要2node

作者: sarsman (DeNT15T♠) 2017-12-18 18:02:00

印象中这题在原考卷中是是非题XD

楼主: howard31622 (howard) 2017-12-18 18:08:00

我知道了应该false

作者: tidarren (tidarren) 2017-12-18 18:23:00

记得2-node的2指的是degree而非key的数量所以应该还是True吧啊sor我眼残应该还是False...

作者: kidplayhappy (kid) 2017-12-18 19:48:00

作者: TMDTMD2487 (ㄚ冰) 2017-12-18 21:02:00

上面的一开始是拉8上去噢

作者: kidplayhappy (kid) 2017-12-18 21:15:00

搜寻路径时遇到4-node要先做split。8,9,10的middle是9，因此一开始是9上拉

作者: TMDTMD2487 (ㄚ冰) 2017-12-18 23:37:00

是7 8 9 10 拉8噢取法你可以1到4取一半的floor, 或是写程式的话是0到3取一半的整数

作者: a020304888a (张小台) 2017-12-18 23:40:00

看程式怎么写去中间其中一个都可以*取

作者: TMDTMD2487 (ㄚ冰) 2017-12-18 23:43:00

不行噢不能乱取除了root以外其他点的degree是有最低限制的反正就正中间或是偶数的话两个之一啦应该是这个意思不过老师比较喜欢书上的解答XD像是这题不照书上的算法写的话答案会边true呢

作者: kidplayhappy (kid) 2017-12-18 23:52:00

T大的做法是bottom up, top down是在search for x时遇到4-node要先做split等到搜过的路node皆合法了才insert

作者: sarsman (DeNT15T♠) 2017-12-18 23:57:00

原来还有这种操作，谢谢k大分享xd

作者: TMDTMD2487 (ㄚ冰) 2017-12-19 00:01:00

我刚刚看了, 是top down 啊

作者: a020304888a (张小台) 2017-12-19 00:06:00

top down k大的说法比较没问题假如只是取m/2去floor可能会取到正要插入的key 这么说来这题是true！？*取 = =

楼主: howard31622 (howard) 2017-12-19 10:23:00

是false喔

作者: ShenJing (ShenJing) 2017-12-23 11:28:00

我的理解、画出来的跟kid大一样

继续阅读