→ w181496: 1.d是B吧 01/20 13:33
感謝w大，你說的沒錯
→ ken52011219: 題目是說worst case吧@@? 01/20 13:34
→ ken52011219: 哦哦哦哦 我看錯了 01/20 13:36
推 hut326521: 5.(b)是32噢 01/20 13:37
我找到32了，剛剛少畫一條3 感謝HUT大~
※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 13:48:09
→ AkariAkaza: 2.a) n^log_8 3, n^1/2=n^log_8 √8,√8小於3 01/20 14:18
感謝A大指正，如你所說的沒錯
→ w181496: 3.c最後一格是11吧 01/20 14:24
我打錯了QQQ~~~ 感謝
※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 14:27:46
※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 14:33:19
→ AkariAkaza: 第4.b)我覺得應該是要求n個node可以形成幾種相異BST? 01/20 15:34
沒錯，我看錯題目意思了@_@
推 yupog2003: 4b我有不同的答案： 01/20 15:34
→ yupog2003: num_BST(i,j){ 01/20 15:35
→ yupog2003: if i < j 01/20 15:35
→ yupog2003: count=0 01/20 15:35
→ yupog2003: for x = i to j 01/20 15:36
→ yupog2003: count = count + num_BST(i,x-1)*num_BST(x+1,j) 01/20 15:37
→ yupog2003: return count 01/20 15:37
→ yupog2003: else 01/20 15:37
※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 15:37:56
→ yupog2003: return 1 01/20 15:37
→ yupog2003: } 01/20 15:37
→ yupog2003: 呼叫方式:num_BST(1,n) 01/20 15:38
這題思考一下應該是使用Random Binary Search tree 將值隨機插入
最高達 n! 排列組合
※ 編輯: ken52011219 (36.224.10.229), 01/20/2017 15:45:36
推 yupog2003: 是說實際打成程式碼之後num_BST會回傳Catalan number 01/20 15:51
→ yupog2003: 也許題目就是想算Catalan number ? 01/20 15:51
→ ken52011219: 結果是卡特蘭數沒錯 ，只能朝這個方向著手了QQ 01/20 15:54
推 a19930301: 請問一下為何第一題d是O(n)而不是O(nlogn) 01/22 15:06
推 as23041248: 第六題是不是要設計一個potential 可是你沒設計 01/23 17:17
→ as23041248: 就蹦出來了 01/23 17:17
沒有要設計呀@@ 解釋它怎麼運作就行了
推 as23041248: 4.b 算出來的總數回傳是不是catalan number才對? 01/23 17:23
是，但我之前懶得改QQQ
→ as23041248: 4.a 他是不是只問bst性質 可是看到你有寫color 01/23 17:24
→ as23041248: 可能是小弟我頭昏了 再麻煩指點一下 01/23 17:26
題目是指要求找到最小AVL tree 的node 數且滿足 紅黑樹的性質
※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 20:47:45
※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 20:59:32
推 as23041248: 沒設計出potential function 怎麼能運作 我覺得怪怪的 01/23 21:25
你可能需要看一下 amorized 的章節，當題目已經給 Φ 的時候，我已經認定
出題教授很明白地讓我們用該符號去做potential function 的運算來表達
為何insertion & Extraction 為 amortized O(logn) & O(1) 就行了
不用再去額外設計potential function ，因為Φ本身就是potential function
至於內部細節 Φ = i log(i) 等之類的可以被預減 因此被我省略
→ as23041248: 4.a.就只有問bst性質而已吧 01/23 21:38
首先，AVL 與 RB tree 是不同的，它並非詢問 RB tree 的 balance
Draw a smallest AVL tree of height 3 (number of edges from the root
to the leaves )
畫一顆高度為3的最小 AVL tree (高度判定為: 從root到葉的邊數)
and then label its node with B(black) or R(red)
且標註它的 黑 與 紅 node
to make it satisfy the RB-tree property.
來滿足它的紅黑樹特性
這是我對於這題敘述的理解，有錯可以指正一下 感謝 <(_ _)>
※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 21:58:25
→ as23041248: 你說到的可能是4.c我說的是4.a喔 不是畫圖那題 01/23 22:00
原來是在指這題的問題 QQ .. 抱歉 我還認真回一串
我這題使用color 的想法是避免重複取到同一個 node
→ as23041248: potential function是cormen的習題 01/23 22:01
我知道這題是cormen 的習題~
※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 22:05:00
※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 22:08:05
→ as23041248: 我在看cormen的時候 他每一個potentialfunction 都有 01/23 22:07
→ as23041248: 先定義出來 不然無法算每個operation的cost才對呀 01/23 22:08
→ as23041248: 就像是fib heap他如果沒有想到那個設計也無法O(1)吧 01/23 22:09
如as大所說它會先定義c' = c_i + Φ(D_i)-Φ(D)
而上面 po 的這一篇我之前也有反覆參考過
我上述的寫法的確投機了一點，只不過那是我在當下遇到這題的解法
抱歉<(_ _)>
※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 22:25:04
→ as23041248: 我是覺得沒先定義是什麼可能會被扣分 提醒一下 ^^ 01/23 22:33
好的，我會這麼寫就代表在考這張考卷的時候就有覺悟了 XDD 還是感謝AS大
的提醒
另外4.a as大有其他的看法嗎??
※ 編輯: ken52011219 (36.224.18.42), 01/23/2017 22:34:59
→ as23041248: 說真的我很廢 我寫不出來 但我有找到別人寫的 哈 01/23 22:41
→ as23041248: 我不確定你的code對不對 但是你可以去leetcode驗證 01/23 22:42
→ as23041248: 想偷問一下ken大 你怎麼在這畫出binary tee的 01/23 23:07
→ as23041248: 還有一些很怪的數學符號 01/23 23:07
綜估時間來說算是倉促的，所以有些都是我自己假設
但到時候考試我還是會將假設的東西寫清楚，像是題目一定要給我們一個
input，以及一個 G(V,E)
且既然題目是要我們求BST的性質，那一定得給我們BT
否則我們也可以自行在code 內判定 是否有 adj[V].color = white 的 node 點
是否有超過 兩個 (不包含 V.parent.color = black )
寫這種 code 不太可能真的拿去測試 XDD , 除非照著官方的演算法，自己想的
code 絕對 bug 一堆
且像是我 code 內的連續 < 這在 C 等語言上面光是 compiler 就不會過了
只能盡可能的表達自己的想法在 code 上~
有哪些符號不懂得嗎@@? != 是不等於
※ 編輯: ken52011219 (36.224.18.42), 01/24/2017 09:31:28
推 h04mp6286: 可以詳細下2c嗎？ 01/24 09:49
沒問題 https://goo.gl/FgtW6R
※ 編輯: ken52011219 (36.224.18.42), 01/24/2017 10:00:50
推 as23041248: 感謝ken大討論這麼多 想問2能不能直接套master theor 01/24 10:01
→ as23041248: em 01/24 10:01
→ as23041248: 另外我上面想問的是你怎麼在ptt上畫出一棵樹的 還有 01/24 10:03
→ as23041248: 打出那些數學符號 01/24 10:03
https://goo.gl/vVewm6 請詳閱~ 我是從這裡學的
關於根號 我想應該只能用 subsutation (其實我大部分都是用這個方法去解)
另外符號的部分，你看你PTT (PC版) 上面那排工具列，有一個鎖的圖像
它左邊就是 符號表了
※ 編輯: ken52011219 (36.224.18.42), 01/24/2017 10:14:06
推 h04mp6286: 感謝詳細(消化ing) 祝考試時鉛筆芯不斷 原子筆不斷水 01/24 10:23
→ yupog2003: 根號系列應該是用n=2^2^k代入？ 01/24 10:45
→ yupog2003: 強化板master theorem的case 2&3，應該是log_b(a)? 01/24 10:46
→ yupog2003: 不過應該不會有人搞錯這個部份就是了，其他都很實用 01/24 10:47
推 k2shouai: 第2大題的C小題的M的次方應該為1.5 01/25 00:14
→ k2shouai: 上面忽略，爬文才發現我講錯...... 01/25 02:28
推 ted30503: 可以請問第三題A 的題目敘述 第二段對答案有影響嗎，另 01/25 12:17
不會有差別，除非為insertion
→ ted30503: 外想請問slot and bucket的差別 ，從第三題A來看 如果他 01/25 12:17
→ ted30503: 所為slot 就是bucket的話，那用AVL tree儲存並搜尋的時 01/25 12:17
→ ted30503: 間複雜度，就是每個SLOT平均會有(n/m)個資料，再套用AVL 01/25 12:17
→ ted30503: TREE的的搜尋時間log(n)，所以最後答案就是log(1+log(n/ 01/25 12:17
→ ted30503: m))這樣想是對的嗎 01/25 12:17
ii another hash table H' is used to hash all the elements with the same
hash value in H.Collisions in H' are resolved recursively.
Assume that each H' also has m slot
這段敘述在這裡最大的功用是 「 避免有 unstable 」的情況發生，若有相同
的 Value 時，它必須能夠使 AVL tree 能正確地把 「最後到達」 的 相同值
歸類在 AVL tree 的相同值的右邊
(
PS: 這樣講好像有點 bug ，當該相同值多到又重新繞回來原相同值的前後面
好像就悲劇了QQ
感覺比較像
1 ..... m
┌─┬─┬─┐
│ │..│ │
└┬┴─┴─┘
○ 1 ...... m
╱ ╲ ┌─┬─┬─┐
○ ｘ┤ｘ│..│x'│
└─┴─┴─┘
)
基本上來說，我是在這邊假設它為 linear probing 只不過不影響它的時間複雜
度 為 worst case O(m)
但這邊要注意的是，此為insertion的情況。而題目是要search，並非insert
以要 search 某值 的情況下， 某值先經過 mod 後找到其 slot( or bucket)值
後藉著 (i)chaining (time Complexity: O(1)) 找到對應的AVL tree
注意的是，題目有給「uniform hashing」，代表意義為每個 slot(or bucket)
的值皆為平均相等，意思是 AVL tree 中 共有 n/m 個 node
接著search AVL tree 找到該值，只需利用該值與node上的值判斷大小即可
直到該AVL tree 的 leaf 為 nil ，則回傳未找到
(time Complexity: O(log(n/m))
相乘即為所求
※ 編輯: ken52011219 (36.224.17.160), 01/25/2017 13:19:54
※ 編輯: ken52011219 (36.224.17.160), 01/25/2017 13:25:00
推 ted30503: 因為我在其他講義看過bucket and slot 不是一樣的東西 01/25 14:32
→ ted30503: 而是類似二維的儲存資料空間 一個TABLE下有N個BUCKET 每 01/25 14:32
→ ted30503: 個BUCKET下又有M個SLOT，類似這種敘述，所以題目是指有M 01/25 14:32
→ ted30503: 個BUCKET嗎 01/25 14:32
剛剛那個是水球嗎@_@ 我不太會用
嚴格來說slot 的確與 bucket 不太一樣，但大部分來說是指同一個分類方法
slot 專指 「欄」,一種類似 entry 的概念，而 這裡 bucket 指的是hash 對於
index 的區別
我是覺得大部分的時間是一樣的啦@@~，除非題目有特別敘述說其為不一樣才會
考慮有其他的闡述方法
因為wiki上面 是寫「bucket or slot」 皆可
→ Carlchen: 4.a的作法? 02/03 10:19
→ Carlchen: 看到有人回一篇了XD 02/03 10:21
※ 編輯: ken52011219 (36.224.3.46), 02/05/2017 17:07:30
推 kiillen: RBTree的leave不是一定要是黑的? 01/14 20:18
→ kiillen: nil不算高度@@ 01/14 20:22