[理工] 資結2-3 tree畫法

[john2557 (WANG)]

如果有洪逸課本可參照9-98例題24的(3)

題目:Suppose a 2-3 tree of height 4 includes 19 elements in 16 nodes.
     How many external nodes are threr in the tree?

洪逸給的解答畫的2-3 tree如下(圖畫得有點醜請見諒)

                      O
                    /   \
                   O     O
                  / \   / \
                 O   O O   O
                /|\ /\ /\ / \
               O OOO O OO O  O         O:nodes

想請問這是怎麼得出這個畫法?

還是只能一直try height=4的2-3 tree 然後只有這個符合?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.170.200.62
推 banjmin:因為B tree leaf都在同一層 高度是四就固定leaf位置了
→ banjmin:因為2-3 tree只會有2-node和3-node
→ banjmin:所以都先畫最少的node的2-node 畫到第四層
→ banjmin:畫到第四層會發現少一個node 再補一個leaf 其父點key值多1
→ banjmin:剩下就是算leaf裡幾個是1key的 幾個是2key的
→ banjmin:後面就是算1key leaf有兩個外部node 2key leaf有3個外部
→ john2557:了解 忘記failure nodes在同一層@@ 感謝B大每次的解答^^