2-3-4 Trees

What is a 2-3-4 Tree?

A 2-3-4 tree (also known as a B-tree of order 4) is a self-balancing search tree where each node can contain 1, 2, or 3 keys and have 2, 3, or 4 children respectively. This structure ensures that the tree remains balanced and operations are performed in O(log n) time.

Key Properties

• Nodes can be 2-nodes (1 key, 2 children), 3-nodes (2 keys, 3 children), or 4-nodes (3 keys, 4 children)
• All leaves are at the same level (perfectly balanced)
• Keys within a node are stored in sorted order
• All keys in a subtree fall within specific ranges defined by parent keys

Common Operations

1. Search: Find a specific key by traversing from root to leaf
2. Insert: Add a key, splitting 4-nodes as needed to maintain balance
3. Delete: Remove a key, potentially requiring rotation or merging
4. Split: When a 4-node is encountered during insertion, split it into two 2-nodes

For more detailed information about 2-3-4 trees, visit Wikipedia's 2-3-4 Tree page.