[理工] 資結-B tree

[white8824 (hypocrisy*)]

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)
推 cksh8008:為什麼1,2會overflow
推 Bearcome:一開始的兩個數應該是非root的 所以degree應該是3
推 cksh8008:http://0rz.tw/ma8qs 1,2不會overflow
→ white8824:感謝c大的連結 不過2-3tree 不是b tree of order 3嗎?
→ white8824:b tree of order的定義不是
→ white8824:1. root 至少有2個children
→ white8824:2. 除root和 external node外的degree範圍:┌ m/2 ┐~ m
→ white8824:也就是key數要在┌m/2┐-1 ~ m-1 之間
→ white8824:我的想法是 order 2的key ┌2/2┐-1 ~ 2-1 之間=0~1之間
→ white8824:所以key最多不是只能有一個? 超過一個就overflow