[理工] [資結] B tree

[kyuudonut (善良老百姓)]

想請問一下 洪逸上課有補充一題

"B tree of order 2 must be a full binary tree"

給的答案是True，原因是外部節點都在同一層

想問：
1. b tree of order 2 照他提供的公式算下來，會有 1-node, 2-node
   跟外部節點都在同一層並不衝突，但為什麼是 full b.t

2. 照他 key數 的公式算下來，可以是0或1，
   但一個 node 裏面沒有 key 是不是我誤會了什麼？

http://i.imgur.com/v7AJqp0.jpg

手機排版可能傷眼，請見諒

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.139.172.219
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1476335966.A.B9D.html
推 aa06697: 不會有deg=1的node 不然failure node 不會全都在同一層
→ aa06697: 你畫畫看就知道了
→ aa06697: 至於key數公式是啥XD 太久沒讀了手邊沒筆記qq
→ aa06697: 哦哦我看到了 可能要有>=2的條件吧 畢竟b tree 應該是不
→ aa06697: 會存在degree 1 的node
→ kyuudonut: 我覺得 b tree of order 2 本身是否存在很有問題
→ kyuudonut: 插入兩個點就fail了(不在同一層上)
推 a15151616: 我筆記沒這題@@ order=2不就是bst嗎 是我記錯了嗎 我
→ a15151616: 亂了~~
推 aa06697: order 2 是full bst沒錯 但bst未必是order 2 像是skew bs
→ aa06697: t 就不符合b tree 我的理解是這樣啦@@
推 yorunohoshi: 照那個公式算出來key可以為0沒錯，不過這樣會違反fa
→ yorunohoshi: ilure node都在同一層@@ 所以應該遵守failure node
→ yorunohoshi: 在同一層比較對。 畢竟在做B tree時，如果有key為空
→ yorunohoshi: ，都會做rotation或combine
有趣的是，如果將第二個點插入 B tree of order 2

root 擁有的 key 會變成兩個，也違反了 B tree of order 2 的 properties
(key數只能0或1)

然後我在聖經本有翻到了，這題是直接抄下來的，但是下面那句話老師沒有抄

"B-trees of order 2 exist only when the number of key values
 is 2^k - 1 for some k"

姑且就先把他當成特例吧，謝謝各位的討論
※ 編輯: kyuudonut (140.116.1.136), 10/15/2016 11:56:14
推 a15151616: 學到新東西謝謝~