[理工] 資結-B tree

看板Grad-ProbAsk作者 (hypocrisy*)時間11年前 (2012/11/01 21:32), 編輯推噓3(3推 0噓 7→)
留言10則, 3人參與, 最新討論串1/1
B tree of order 2 is full binary tree Why? 假如依序插入 1 2 --- --- | 1 | |1,2| --- , --- (overflow作split, 1上拉當父點} 得到的結果 1 \ 2 這就不是full binary tree 了吧?? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.248.85.134 ※ 編輯: white8824 來自: 111.248.85.134 (11/01 21:45)
推
11/01 23:07, , 1F
為什麼1,2會overflow
11/01 23:07, 1F
推
11/01 23:19, , 2F
一開始的兩個數應該是非root的 所以degree應該是3
11/01 23:19, 2F
推
11/02 00:18, , 3F
http://0rz.tw/ma8qs 1,2不會overflow
11/02 00:18, 3F
→
11/02 01:52, , 4F
感謝c大的連結 不過2-3tree 不是b tree of order 3嗎?
11/02 01:52, 4F
→
11/02 01:52, , 5F
b tree of order的定義不是
11/02 01:52, 5F
→
11/02 01:53, , 6F
1. root 至少有2個children
11/02 01:53, 6F
→
11/02 01:54, , 7F
2. 除root和 external node外的degree範圍:┌ m/2 ┐~ m
11/02 01:54, 7F
→
11/02 01:55, , 8F
也就是key數要在┌m/2┐-1 ~ m-1 之間
11/02 01:55, 8F
→
11/02 01:58, , 9F
我的想法是 order 2的key ┌2/2┐-1 ~ 2-1 之間=0~1之間
11/02 01:58, 9F
→
11/02 01:58, , 10F
所以key最多不是只能有一個? 超過一個就overflow
11/02 01:58, 10F
‣ 更多 white8824 的文章
文章代碼(AID): #1GaddpcA (Grad-ProbAsk)