在2-3-4樹中插入時如何拆分節點？

Question

如何在2-3-4樹中分割節點是否有規則？

E.g.如果我插入3，7，4，9成2-3-4樹：如圖所示

將它拆分這樣的（黃色）或（綠色）位置：

都有效嗎？

Answer 1

綠色。您需要考慮算法步驟。查看the wikipedia page的插入步驟。關鍵部分是在考慮下一個插入之前，通過將中間值向上移動一級來分割4節點（其具有3個值）。

1. Insert 3 into blank. Result: 3   (a 2-node) 
2. Insert 7.   Result: 3 - 7  (a 3-node) 
3. Insert 4.   Result: 3 - 4 - 7 (a 4-node) 
5. Insert 9. There is already a 4-node, so this must be split. 
    The split will be to move 4 up a level, and 3 and 7 are now child nodes of 4 
    (like your green diagram). 9 is then added next to the 7.