[理工] [資結] B tree

看板Grad-ProbAsk作者 (善良老百姓)時間9年前 (2016/10/13 13:19), 9年前編輯推噓5(5推 0噓 11→)
留言16則, 4人參與, 最新討論串1/1
想請問一下 洪逸上課有補充一題 "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
推
10/13 14:19, , 1F
不會有deg=1的node 不然failure node 不會全都在同一層
10/13 14:19, 1F
→
10/13 14:19, , 2F
你畫畫看就知道了
10/13 14:19, 2F
→
10/13 14:21, , 3F
至於key數公式是啥XD 太久沒讀了手邊沒筆記qq
10/13 14:21, 3F
→
10/13 14:26, , 4F
哦哦我看到了 可能要有>=2的條件吧 畢竟b tree 應該是不
10/13 14:26, 4F
→
10/13 14:26, , 5F
會存在degree 1 的node
10/13 14:26, 5F
→
10/13 17:15, , 6F
我覺得 b tree of order 2 本身是否存在很有問題
10/13 17:15, 6F
→
10/13 17:16, , 7F
插入兩個點就fail了(不在同一層上)
10/13 17:16, 7F
推
10/13 23:24, , 8F
我筆記沒這題@@ order=2不就是bst嗎 是我記錯了嗎 我
10/13 23:24, 8F
→
10/13 23:24, , 9F
亂了~~
10/13 23:24, 9F
推
10/14 10:50, , 10F
order 2 是full bst沒錯 但bst未必是order 2 像是skew bs
10/14 10:50, 10F
→
10/14 10:50, , 11F
t 就不符合b tree 我的理解是這樣啦@@
10/14 10:50, 11F
推
10/14 16:17, , 12F
照那個公式算出來key可以為0沒錯，不過這樣會違反fa
10/14 16:17, 12F
→
10/14 16:17, , 13F
ilure node都在同一層@@ 所以應該遵守failure node
10/14 16:17, 13F
→
10/14 16:17, , 14F
在同一層比較對。 畢竟在做B tree時，如果有key為空
10/14 16:17, 14F
→
10/14 16:17, , 15F
，都會做rotation或combine
10/14 16:17, 15F
有趣的是，如果將第二個點插入 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
推
10/16 08:54, , 16F
學到新東西謝謝~
10/16 08:54, 16F
‣ 更多 kyuudonut 的文章
文章代碼(AID): #1N_nbUkT (Grad-ProbAsk)