algorithmtreeinsertionmultiway-tree2-3-4-tree

How to split node when inserting in 2-3-4 Tree?

Is there a rule for how to split the node in 2-3-4 tree?

E.g. If I insert 3, 7, 4, 9 into the 2-3-4 tree:

Will it be split like this (yellow) or that (green) as shown here:

enter image description here

Are both valid?

Solution

  • Green. You need to consider the algorithm steps. Check out the the wikipedia page for insertion steps. The key part is to split a 4-node (which has 3 values) by moving the middle value up a level before considering the next insert.

    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.