What is a 2-3 Tree?

A 2-3 Tree is a multiway search tree. It’s a self-balancing tree; it’s always perfectly balanced with every leaf node at equal distance from the root node.

Other than the leaf nodes, every node can be one of two types:

• 2-Node: A node with a single data element that has two child nodes

• 3-Node: A node with two data elements that has three child nodes

Structure of a 2-Node

Like a binary search tree, when a node only contains one data element the left subtree of that node (parent node) will contain nodes with data elements valued less than the parent node’s data elements, while the right subtree will contain nodes with data elements valued greater than the parent node’s data elements. Nodes having the same value as their parent node can be inserted in either the left or the right subtree.

Insertion

If a tree is empty, create a root node and insert the new element. In our examples below, the red square represents the new element to be inserted.

If a tree is not empty, locate the appropriate leaf node. If the leaf node has 1 data element, insert the new element in the leaf node.

After insertion, if the leaf node has more than two data elements, split the data elements into 3 separate nodes and appoint the node with the middle value as the parent node with the other two nodes as its child nodes. In our example below we end up with a 2-Node.

By inserting two more elements, we can create a 3-Node.

Time Complexity

The property of being perfectly balanced, enables the 2-3 Tree operations of insert, delete and search to have a time complexity of $O(log (n))$.