2-3-4 Trees

Properties

Values are ordered and children are ordered. All leaves on same level. All intervals nodes must have one more child than values. They grow from the root upwards

Steps of the Insertion

  1. Search for value to find leaf to insert to.
  2. Insert new value into node and preemptive split if needed
  3. Move node down and repeat process until in correct spot.

Example Diagram

2-3-4 Preemptive Split Diagram

Learn More

2-3-4 Trees on Wikipedia