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