2-3-4 Trees and Insertion

A 2-3-4 tree is a self-balancing search tree used for efficient data storage and retrieval.

What is a 2-3-4 Tree?

• It's type of balanced tree where every node can have 2, 3, or 4 children.
• It remains balanced, meaning all leaves are at the same depth.
• It's used in file systems and databases due to its efficient search, insert, and delete operations.

Insertion in a 2-3-4 Tree

Insertion in a 2-3-4 tree follows these steps:

1. Locate the leaf node where the new value should be inserted.
2. If the node has space, insert the value in sorted order.
3. If the node is full (contains 3 values), **split** the node:
   • The middle value moves up to the parent.
   • The left and right values form two separate child nodes.
4. Repeat splitting up the tree if its necessary to maintain balance.

Diagram of a 2-3-4 Tree

Learn More

For more information, visit Wikipedia's 2-3-4 Tree Page.