2-3-4 Trees

Introduction

2-3-4 is a search tree that is an advanced version of 2-3 trees. This tree can accommodate more keys; hence, there are more child nodes as compared to 2-3 trees. 2-3-4 satisfies all the properties covered in 2-3 trees along with some additional key features:

• Each internal node can contain three keys at max.

• Each internal node can have four child nodes at max.

• In case of three keys at an internal node namely left, mid, and right key, all the keys present at LeftChild node are smaller than the left key, which can be mathematically expressed as:

$$LeftChild.keys < LeftKey.$$

• All the keys present at LeftMidChild node are smaller than the mid key, which can be mathematically expressed as:

$$LeftMidChild.keys < MidKey.$$

• All the keys present at RightMidChild node are smaller than the right key, which can be mathematically expressed as:

$$RightMidChild.keys < RightKey.$$

• Finally, all the keys present at RightChild node are greater than the right key, which can be mathematically expressed as:

$$RightChild.keys > RightKey.$$

$$$$

Example

Provided below is an example of 2-3-4 trees. The insertion/deletion is performed in the same way as the 2-3 trees. Keeping just one fact in mind, nodes are allowed to have three keys at a time instead of two.