Intro to 2-3-4 Trees:

• A 2-3-4 Tree is a tree data structure made up of 2-nodes, 3-nodes, and 4-nodes.
• Each node stores 1, 2, or 3 values, respectively.
• The values within a node are in sorted order, as are the values of each node's children.

How to insert a value into a 2-3-4 Tree:

1. Perform a search for the desired value.
2. During the search, for every full node with 3 values on path to value during the search, perfom a pre-emptive split of the node.
3. Continue the search at the parent node. Do not split it even if it has now been made full.
4. Insert the new value into the leaf at the end of the search. All leaves should be at the same level.

For more information and examples, watch this helpful video from a CS400 lecture courtesy of Prof. Florian: