How to insert 7 into this 2-3 tree

Question

I am trying to insert the element 7 into this 2-3 tree (see picture):

Since the node containing 6 and 9 is already full, I should move 7 to the parent of 6 and 9, but that node is also already full, so then what do I do?

Answer 1

You are correct that the leaf (6, 9) is full and must split when inserting 7. This means that the middle value (which then is 7) must be inserted in the parent node (the root in this case). As you correctly note, that node (2, 5) is also full. So... it must also split. When considering 7, the middle value is 5, which has to move "up". As there is no "up", it will form a new root node:

If we visualise the intermediate, violating states, we get this during the insertion process:

              ┌───┬───┐
              │ 2 │ 5 │
              └───┴───┘
             /    |    \
         ┌─┬─┐  ┌─┬─┐  ┌─┬─┬─┐
         │1│ │  │3│4│  │6│7│9│ (overflow)
         └─┴─┘  └─┴─┘  └─┴─┴─┘

Then 7 moves up:

              ┌───┬───┬───┐
              │ 2 │ 5 │ 7 │ (overflow)
              └───┴───┴───┘
             /    |   |    \
         ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
         │1│ │ │3│4│ │6│ │ │9│ │ 
         └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘

Then 5 moves up:

                   ┌─┬─┐
                   │5│ │
                   └─┴─┘ 
                  /   \
             ┌─┬─┐     ┌─┬─┐
             │2│ │     │7│ │
             └─┴─┘     └─┴─┘
            /   \     /   \
        ┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
        │1│ │ │3│4│ │6│ │ │9│ │
        └─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘