2–3 tree

It follows that each right, center, and left subtree of a node contains the same or close to the same amount of data.

If the tree consists only of a 3-node, the node is split into three 2-nodes with the appropriate keys and children.

If the target node is a 3-node whose parent is a 2-node, the key is inserted into the 3-node to create a temporary 4-node.

If the target node is a 3-node and the parent is a 3-node, a temporary 4-node is created then split as above.

Alternatively, it's possible to use an algorithm which is both top-down and bottom-up, creating temporary 4-nodes on the way down that are then destroyed as you travel back up.

Insertion of a number in a 2–3 tree for 3 possible cases