The Core Concept

In a standard BST, nodes only have one value. In a 2-3-4 tree, nodes can have 1, 2, or 3 values. This helps keep the tree short and reduces the number of memory accesses needed to find data.

Tree Properties

1. Balance: Every leaf node in the tree must be at the exact same depth.

2. Child Logic: A node with X values always has X+1 children.

3. Sorted Data: All values within a single node are kept in ascending order.

Visual Representation

A 2-3-4 tree diagram

This diagram shows how 4 nodes split to maintain the balance of the tree during insertion.

Algorithm Steps for Search

  1. Start at the root node.
  2. Compare target value to the values in the current node.
  3. If found, return the node.
  4. If not found, move to the appropriate child subtree and repeat.

External Resources

You can find more technical details here:

Wikipedia: 2-3-4 Tree Details