2-3-4 Trees

Overview

2-3-4 Trees are trees with as many as 3 values and 4 children per node. This helps limit the height of the tree which helps improve memory storage.

Inserting into the tree

1. Start at the root node of the tree
2. Compare the value you are inserting to the values in the node.
3. If the inserted value is greater than the current value, move to the next value. If it is smaller, move down to the left child node and begin insertion again
4. If the current node already has 3 values, split the node into 3 nodes by moving the middle value up to the parent node, and making the left and right values the roots of the new left and right child nodes. Leave the other elements of the tree the same.
5. Repeat steps 2 to 6 until the value is inserted into a leaf node.
6. If you already passed a node during insertion, do not go back to that node to split it up later in the insertion process.

To learn more about 2-3-4 trees, click here