It is a simply a type of B-Tree. Each node has 2,3 or 4 pointers. Thus a 2-3-4 tree consists of three kinds of nodes:

• 2-nodes (nodes with 1 data element and 2 pointers)
• 3-nodes (nodes with 2 data elements and 3 pointers) and
• 4-nodes (nodes with 3 data elements and 4 pointers)

Similar to a B-Tree and Binary Search Tree, each pointer from a node points to a (sub)tree containing data elements in the interval limited by the data elements surrounding the pointer.

The methods for insertion, deletion and searching resemble those in a B-Tree, and involve a similar splitting of 4-nodes into 2-nodes and transfer of data elements into parents. 2-3-4 are more correctly classified as top-down B-Trees.

2-3-4 trees are important because they are in many ways the logic behind Red-Black Tree . It is possible to redraw a Red-Black Tree as a 2-3-4 tree by grouping nodes connected together by black links. Color flip operations on Red-Black Trees are just a simpler way to split nodes. In a way, Red-Black Trees are the easier-to-implement versions of 2-3-4 trees.