[理工] 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大一樣

繼續閱讀