2-3-4 Tree

Definition

2-3-4 tree is a type of B-tree. It is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The name comes from the fact that each internal node (except the root) has between 2 and 4 children.

Properties

• Each internal node has 2, 3, or 4 children and 1 less key value.
• Each leaf node has 0 children and 1 less key value.
• All leaves have the same depth