What is a 2-3 Tree?

Introduction

A 2-3 Tree is another form of a search tree, but it is very different from a Binary Search Tree. Unlike BST, 2-3 Tree is a balanced and ordered search tree that provides a very efficient storage mechanism to guarantee fast operations. We will take a detailed look at a 2-3 Trees’s structure, the limitations it follows, and how elements are inserted and deleted from it.

One key feature of a 2-3 Tree is that it remains balanced, no matter how many insertions or deletions you perform. The leaf nodes are always present on the same level and are quite small in number. This is to make sure the height doesn’t increase up to a certain level as the time complexity of all the operations is mainly dependent upon it. Ideally, we want the height to be in logarithmic terms because the tree will require more time to perform operations as it grows larger. In 2-3 Trees, the height is logarithmic in the number of nodes present in the tree. They generally come in 2 forms:

• 2 Node Tree
• 3 Node Tree

See the figures below to get an idea of how they are different. The first figure is a 2-3 Tree with only two nodes. To keep it ordered, the left child key must be smaller than the parent node key. Similarly, the right child key must be greater than the parent key.