2-3-4ツリーに挿入するときにノードを分割する方法は？

Question

2-3-4ツリーでノードを分割する方法はありますか？

など。私は3,7、4を挿入した場合、2-3-4ツリーに9：ここに示されているように

は、この（黄色）、または（緑）のように分割される：

どちらも有効ですか？

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.