→ goldflower: 2(c)cormen274~276 我看沒很懂... 02/16 16:17
→ goldflower: r/b max發生在每個red node恰有兩個black child時 02/16 16:21
→ goldflower: 也就是此時所有leaf都是red 02/16 16:21
→ goldflower: 那就有b=2r+1且r+b=n 就可得解 02/16 16:22
推 goldflower: 然後h(x)=1好像比較像probing method? 02/16 16:25
不太懂g大什麼意思 overflow不是search h1(x)+i*h2(x)嗎?
推 FRAXIS: 4(a) 不是紅黑樹的性質嗎？ 每一路徑紅黑點的比例最大為2 02/16 18:29
→ amge1524: o'_'o 可是4.a不是要internal node QQ 02/16 18:46
推 dddm49: 扣掉external node就是最大比例就是2 這是性質之一吧 02/16 19:22
推 goldflower: 他不是問路徑吧@@? 02/16 19:28
推 goldflower: 其實我當下直接寫2 但是覺得很不保險就查了別種 02/16 19:32
→ goldflower: 解法 ttps://cise.ufl.edu/class/ 02/16 19:33
→ goldflower: cot5405sp13/HW3_solution_sp13.pdf 覺得他的說法 02/16 19:33
→ goldflower: 也是頗有道理的? 02/16 19:33
推 FRAXIS: 路徑的比例最大是 2 那 internal node 比例可以比 2 大? 02/16 19:36
推 goldflower: 對啊 我是覺得找常數會是2 但是就覺得只寫常數抖抖 02/16 19:38
推 FRAXIS: 應該就是 2 吧 而且原 po 也建構出例子來了 02/16 19:40
推 goldflower: 但是如果他是把最後一層當作是leaf來看呢@@? 02/16 19:41
→ goldflower: 因為他特別說要internal node 所以才在想會不會要把 02/16 19:42
→ goldflower: 最後一層砍掉再去比? 02/16 19:42
→ yaxauw: 2吧 就是它某年考古題選擇題選項改成簡答 02/16 20:08
→ yaxauw: 2(a)好像也是某年考古題選擇題選項 02/16 20:08
推 goldflower: 這樣我的103考古題就能多五分了 QQ 02/16 20:09
感謝各位幫忙解答~~^_^
※ 編輯: prosperous (1.162.79.128), 02/16/2016 23:04:30
推 goldflower: 啊啊沒事我想成rehasing了 02/16 23:31
阿好喔! 謝謝~~
※ 編輯: prosperous (1.162.79.128), 02/17/2016 00:21:05
推 Transfat: 4(a) 可以參考 12/21 13:32