[理工] 106台大電機資結

看板Grad-ProbAsk作者 (揪立)時間7年前 (2017/02/12 17:51), 編輯推噓32(32推 0噓 58→)
留言90則, 20人參與, 最新討論串1/1
小弟資質不夠好 想問一下234那題答案多少呢？ 插了各種插法插不出答案 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.179.81 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486893104.A.3B6.html
推
02/12 17:52, , 1F
插不出+1 最後猜了QQ
02/12 17:52, 1F
→
02/12 17:53, , 2F
Top down 我按照網路上的教法，插出來，無解
02/12 17:53, 2F
推
02/12 17:56, , 3F
我寫ab
02/12 17:56, 3F
→
02/12 17:56, , 4F
我只有猜B，a試過各種方法都只有2QQ你怎麼插的呢
02/12 17:56, 4F
推
02/12 17:56, , 5F
AB
02/12 17:56, 5F
推
02/12 17:57, , 6F
我也猜B哈哈
02/12 17:57, 6F
推
02/12 17:58, , 7F
兩種方法會得到不同答案，AB或BD都有可能，不知道老師
02/12 17:58, 7F
→
02/12 17:58, , 8F
到底要哪一種，乾
02/12 17:58, 8F
推
02/12 17:59, , 9F
在搜尋插入路徑時 如果有4-node就要先分裂
02/12 17:59, 9F
→
02/12 18:00, , 10F
分裂到路徑上皆無4-node為止 再放入data
02/12 18:00, 10F
→
02/12 18:00, , 11F
4-node 是指4個子點…乾
02/12 18:00, 11F
→
02/12 18:00, , 12F
對，我就是用這個方法，然後沒答案，T大你們教授怎麼教的
02/12 18:00, 12F
→
02/12 18:00, , 13F
呢？
02/12 18:00, 13F
→
02/12 18:02, , 14F
我寫BD
02/12 18:02, 14F
推
02/12 18:04, , 15F
沒答案啊....我造了三次QQQ
02/12 18:04, 15F
→
02/12 18:05, , 16F
感覺要掰了QQ
02/12 18:05, 16F
→
02/12 18:08, , 17F
這種無解的有沒有辦法上訴啊，真的很靠北
02/12 18:08, 17F
推
02/12 18:09, , 18F
推五樓神人 我有造出來 我是寫AB
02/12 18:09, 18F
→
02/12 18:10, , 19F
B不太確定 在leaf data有三個 算不算4 node 最後我還是選
02/12 18:10, 19F
→
02/12 18:10, , 20F
了 想說指向null應該也算link吧
02/12 18:10, 20F
→
02/12 18:10, , 21F
02/12 18:10, 21F
→
02/12 18:10, , 22F
我當初看這個影片學的，然後今天沒答案0...0
02/12 18:10, 22F
→
02/12 18:12, , 23F
top down插入只有一種不是嗎？就是y大說的那樣
02/12 18:12, 23F
推
02/12 18:12, , 24F
我也寫AB
02/12 18:12, 24F
推
02/12 18:26, , 25F
4-node是指4 key還是4degree啊？？？
02/12 18:26, 25F
→
02/12 18:27, , 26F
4個children ，就是3個jey
02/12 18:27, 26F
→
02/12 18:27, , 27F
Key
02/12 18:27, 27F
推
02/12 18:32, , 28F
問題同jay +1
02/12 18:32, 28F
→
02/12 18:33, , 29F
joe
02/12 18:33, 29F
推
02/12 18:35, , 30F
B選項是啥？過半那個？
02/12 18:35, 30F
推
02/12 18:36, , 31F
一個4-node跟過半那個選項～ 我選這兩個
02/12 18:36, 31F
推
02/12 18:36, , 32F
我有選b，d是啥忘了可以說一下嗎
02/12 18:36, 32F
→
02/12 18:36, , 33F
如果4-node、3-node是指degree有幾個那應該就是這樣了
02/12 18:36, 33F
→
02/12 18:36, , 34F
，畫了兩種都一樣結果@@
02/12 18:36, 34F
推
02/12 18:38, , 35F
難得很確定的一題 卻選項鳥掉..
02/12 18:38, 35F
推
02/12 18:40, , 36F
AB，但B的4-node是在最左下角deg=0，讓我選的很猶豫
02/12 18:40, 36F
推
02/12 18:46, , 37F
02/12 18:46, 37F
→
02/12 18:47, , 38F
答案同上
02/12 18:47, 38F
→
02/12 18:48, , 39F
我很確定是那張圖，我畫了至少3次以上
02/12 18:48, 39F
→
02/12 18:49, , 40F
這樣答案就是AB呀@@
02/12 18:49, 40F
推
02/12 18:49, , 41F
0.0 所以root是3-node，然後只有一個4-node(左下
02/12 18:49, 41F
→
02/12 18:49, , 42F
A選項是root為3 node B是只有一個4 node
02/12 18:49, 42F
→
02/12 18:49, , 43F
Root是2node吧？
02/12 18:49, 43F
→
02/12 18:50, , 44F
等一下，他那個node該不會是children吧？
02/12 18:50, 44F
→
02/12 18:50, , 45F
幾node是看degree
02/12 18:50, 45F
→
02/12 18:50, , 46F
靠北.....難怪我覺得沒答案
02/12 18:50, 46F
→
02/12 18:50, , 47F
3 node => link 有3條
02/12 18:50, 47F
→
02/12 18:51, , 48F
好吧，那確定答案是AB了
02/12 18:51, 48F
→
02/12 18:51, , 49F
純看deg的話不知道左下角那個是不是4 node耶....
02/12 18:51, 49F
推
02/12 18:51, , 50F
嚴格說起來 插完8 root 要維持是4-node 等7來插的時候才sp
02/12 18:51, 50F
→
02/12 18:51, , 51F
lit
02/12 18:51, 51F
→
02/12 18:52, , 52F
選AB 加一
02/12 18:52, 52F
→
02/12 18:53, , 53F
應該算 不然leaf那些點不知道要叫幾node@@
02/12 18:53, 53F
→
02/12 18:53, , 54F
Top down 我猜應該就是 forward insertion 跟上面y大說的
02/12 18:53, 54F
→
02/12 18:53, , 55F
一樣
02/12 18:53, 55F
推
02/12 18:54, , 56F
02/12 18:54, 56F
→
02/12 18:54, , 57F
因為插8，10上拉時又會再產生一個4-node，所以就直
02/12 18:54, 57F
→
02/12 18:54, , 58F
接再分裂@@
02/12 18:54, 58F
推
02/12 18:56, , 59F
好吧 大家都ab 那我應該畫錯了QQ
02/12 18:56, 59F
→
02/12 18:57, , 60F
我跟c大畫一樣欸...不是4個key才要拆嗎？你們怎麼都三
02/12 18:57, 60F
→
02/12 18:57, , 61F
個就拆了
02/12 18:57, 61F
推
02/12 18:58, , 62F
你畫的是拉左二 有些人拉左三
02/12 18:58, 62F
→
02/12 18:58, , 63F
兩個劃法答案不同
02/12 18:58, 63F
→
02/12 18:58, , 64F
''top down'' insert
02/12 18:58, 64F
推
02/12 19:00, , 65F
top down在放進去之前就要先拉 放進去再拉就變bot up
02/12 19:00, 65F
→
02/12 19:00, , 66F
Top down是3個key就要拉了吧？
02/12 19:00, 66F
→
02/12 19:00, , 67F
沒有拉左二左三的問題 因為他是在往下搜尋的時候發現有3
02/12 19:00, 67F
→
02/12 19:00, , 68F
個key的node就直接把中間往上拉 所以他可能會導致樹高較
02/12 19:00, 68F
→
02/12 19:00, , 69F
高 優點是他只要往下跑一次然後插入 一般跑法往下跑完插
02/12 19:00, 69F
→
02/12 19:00, , 70F
入後可能還要在往上調整到root
02/12 19:00, 70F
推
02/12 19:01, , 71F
原來是這樣 受教了
02/12 19:01, 71F
推
02/12 19:02, , 72F
好...現在才知道 上了一課 謝謝各位大大
02/12 19:02, 72F
推
02/12 19:07, , 73F
看這串討論串我真心覺得我還太菜了
02/12 19:07, 73F
推
02/12 19:07, , 74F
懂了！謝謝
02/12 19:07, 74F
→
02/12 19:07, , 75F
所以照aa大說的 yuro大插的那個 頂多往上調一次 再繼續往
02/12 19:07, 75F
→
02/12 19:07, , 76F
上調就不是 top down 了？
02/12 19:07, 76F
→
02/12 19:15, , 77F
疑 4-node不是指child有四個喔orz我沒選B
02/12 19:15, 77F
→
02/12 19:30, , 78F
Node是看有幾個child 又=link
02/12 19:30, 78F
→
02/12 19:33, , 79F
我跟yo大的圖一樣，左下不是3-node?
02/12 19:33, 79F
→
02/12 19:34, , 80F
該不會是指空鏈結吧QQ
02/12 19:34, 80F
→
02/12 19:35, , 81F
3個key = 4個node
02/12 19:35, 81F
→
02/12 19:35, , 82F
是extended tree 不是空指標
02/12 19:35, 82F
推
02/12 19:35, , 83F
喔喔 對耶我沒仔細看 他應該只會調一次喔 不會再往上拉
02/12 19:35, 83F
→
02/12 19:35, , 84F
可是答案跟y大最後畫的一樣
02/12 19:35, 84F
推
02/12 19:36, , 85F
謝謝G大，我難過
02/12 19:36, 85F
→
02/12 19:36, , 86F
原來G大在前面就發現了Orz
02/12 19:36, 86F
推
02/12 19:44, , 87F
重新讀了一次 確實一次只會拉一次 下一回合插入才會
02/12 19:44, 87F
→
02/12 19:44, , 88F
再拉orz 感謝G大
02/12 19:44, 88F
推
02/12 19:53, , 89F
寫的跟aa大一樣 我就放心了
02/12 19:53, 89F
推
01/21 16:46, , 90F
看影片就行啦嘻嘻
01/21 16:46, 90F
‣ 更多 joeboy 的文章
文章代碼(AID): #1Oe30mEs (Grad-ProbAsk)