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 and hence 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 at max three keys

• Each internal node can have at max four child nodes

• 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

Given below is an example of 2-3-4 Trees. The insertion/deletion is performed in the same way as we did in 2-3 Trees keeping just one fact in mind that here, nodes are allowed to have three keys at a time instead of two.