What are 2-3 Trees?

Introduction

A 2-3 tree is another form of search tree, but it is very different from the binary search tree. Unlike BST, 2-3 tree is a balanced and ordered search tree, which provides a very efficient storage mechanism to guarantee fast operations. In this chapter, you will take a detailed look at 2-3 trees’ 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. It does not matter how many insertions or deletions you perform. The leaf nodes are always present on the same level and are 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 are mainly dependent upon it. Ideally, you want the height to be in logarithmic terms because as the tree grows larger, it will require more time to perform operations. In 2-3 trees, the height is logarithmic in the number of nodes present in the tree. They generally come in two forms:

• 2 node tree
• 3 node tree

See the figures below to understand how they are different. Given below 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.

The figure below shows a 3-node tree where each node can contain two keys and three children at max. Here the parent node has two keys and three children who are all at the same level. Let’s say the first key at the parent node is X, and you call the second one Y. As shown in the figure, the X key is greater than the left child, and the Y key is smaller than the child key at right. The middle child has a value that is greater than X and smaller than Y.

Concluding from the explanation above, 2-3 trees acquire a certain set of properties to keep the structure balanced and ordered. Take a look at these properties.

Properties

• All leaves are at the same height.

• Each internal node can either have two ...