作者madd1412 (放肆)
看板Grad-ProbAsk
標題Re: [理工] [DS] Tree 的定理/引理相關
時間Thu Dec 15 22:37:08 2011
關於第一個問題..
就當作台大都是以 root 是在 level 0 為準的背起來好了XD~
#
第11題 B選項
B tree of order n 的定義
_ _
|n/2 | <= degree <=n
_ _
|n/2 | - 1 <= Key <=n-1 (key:node裡面的值的數量)
所以如下圖:
Level
0 ○ ←ROOT
/.....\
1 ○ ○ ○..○ ←d 個node (這樣就滿足題意的degree為d)
. |
2 ○
. |
. .
. .
h ○ 這樣應該就滿足 題目說的條件了 總 Node=1+d+(h-2+1)=h+d
#
第14題的 B-tree of order 2
其實 B-tree of order 2 is full binary tree 好像是定義的樣子(?!)
好像有在課本看過這句話..
根據定義的話 0<=key<=1
然後 B-tree又規定root至少有>=2個children..
所以就只會長出full binary tree ~
(有錯的話請指正@@)
※ 引述《metalalive (想玩音樂)》之銘言：
: http://www.lib.ntu.edu.tw/exam/graduate/96/96412.pdf
: 第11題
: 選項A
: 手邊解答是true
: 我是寫false
: 我是假設 root level = 1 (DS也是這樣定義沒錯吧)
: 然後 d^0 + d^1 + d^2 + ..... + d^(h-1)
: ↑因為題目說tree height = h
: 解出來就是 (d^h-1)/(d-1)
: 但是手邊解答說true , 似乎是假設 root的level是 0
: 這蠻困擾我的,不知道用哪一套定義
: 選項B
: 解答是true
: 我的疑問是 , 即使題目有給 degree = d 的值
: 可是選項只說 minimum nodes
: 似乎沒提到有哪一個node的degree一定要達到d
: 那這樣我假設這個tree是 height = h 且 node數量 = h
: 不就比 h+d 的node來的少
: (SORRY,我不太會敘述我的疑惑)
: 第14題
: 選項A
: 如果這個 B-tree of order 2 只存2個 key 值 ,
: (每個node都只存一個KEY值,應該沒搞錯定義吧)
: 那這樣的話此 B-tree 就不是 full binary tree了?
: 順便請教
: 如果它是 full binary tree
: 那會長什麼樣子呢?
: 很多細小的觀念當初看書都沒抓到
: 真麻煩
: 感謝各位的解答! @@
--
◢ █ █ ◢█ ◢ █ ◢█ ◢█◣
██◣◢◣◢◣ ◢███◣ ◢███ ◢███ ██ █ █ ██ █ █
███████ █████ ◢████ ◢████ █ █ █ █ █ █
██◤█◤██ ██◤ █ ██◤ █ ██◤ █ █ ◥██ █ ◢◤
██ █ ██ ██ █ ██ █ ██ █ █ █ █ ◢◤
◥█ ◥ █◤ ◥██◤◥ ◥██◤◥ ◥██◤◥ ███ █ ███ ███
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.173.129.243
推 pikachu123:那個在聖經P530 不是定義 那是因為Failure Node要在同 12/15 23:02
→ pikachu123:一層才會造成這樣的結果 12/15 23:02
→ pikachu123:他在定義下面順便講一下 12/15 23:04
→ madd1412:哈~原來不是定義阿...感謝樓上的大大!! 12/16 00:04
推 kiwidoit:11.(B)題有說是B tree嗎? 12/16 14:49
→ madd1412:...靠~對耶...題目沒說= = 12/16 18:01
→ madd1412:不對...題目有說Degree d阿..= = 12/16 18:03
→ kiwidoit:degree d 不代表一定是B tree吧@-@? 12/16 19:25
推 pikachu123:11題跟B Tree一點關西都沒有 純粹考Tree的定理 12/16 23:36
→ madd1412:哈~我有點昏了..話說~我畫出來的也不是B-tree阿~ 12/17 08:05