2-3-4 Trees

A 2-3-4 tree is a self-balancing search tree where each node can contain 1, 2, or 3 keys and have 2, 3, or 4 children respectively.

Node Types

Understanding the different node configurations is very important:

Key Properties

Balance

All leaf nodes are at the same depth, ensuring the tree remains perfectly balanced.

Search Efficiency

Search, insertion, and deletion operations all run in O(log n) time.

Insertion Steps

  1. Search for the correct leaf position
  2. Insert the key into the leaf node
  3. If the node becomes a 4-node, split it into two 2-nodes
  4. Promote the middle key to the parent

Visual Example

2-3-4 Tree Structure

Fun Fact: 2-3-4 trees are isomorphic to red-black trees. Each 2-3-4 tree can be directly converted to a red-black tree.

Learn More

For additional information, visit:

Wikipedia: 2-3-4 Trees