2-3-4 Trees

What is a 2-3-4 Tree?

A 2-3-4 tree is a self-balancing search tree where every node can have 2, 3, or 4 children.

Key Properties

• Every node has at most 3 keys and 4 children
• Nodes are split when they reach their maximum capacity of 3 keys during an insertion
• Search, insert, and delete all run in O(log n) time

Diagram

Learn More