A **2-node** is like a regular node in a binary search tree: It has one
key and two children.

A **3-node** has 2 keys and 3 children. The middle child’s key is in
between the left and right child’s key. One key of the 3-node is larger
than all keys in the left subtree, but smaller than all keys in the
middle subtree. The other key is larger than all keys in the middle
subtree, but smaller than all keys in the right subtree.

Let’s build a “binary” tree with these nodes. You’ll end up with a perfectly balanced tree. Every path from the root to a leaf node has the same length.

## Operations

### Insertion

If the insertion is under a 2-node, then convert it into a 3-node.

If the insertion is under a 3-node, follow the following steps:

- Add a new key into the 3 node to create a 4-node (it has 3 keys).
- Move the middle key in the 4 node into its parent, and split the
current 3 node into 2 nodes. The left one becomes the middle child of the
parent 3-node, and the right one becomes the right child of the
parent 3-node.
- If the parent is also a 3-node originally, simply recurse.

.

.

If the root becomes a 4-node, then split it. This is the *only* way the
height increases in a 2-3 tree!

## Properties

- The trees are perfectly balanced. Every path from the root to a leaf node has the same length.
- The worst case tree height is \(\lg N\), which occurs when all your nodes are 2-nodes.
- The best case tree height is \(\log_{3}N\), which occurs when all your nodes are 3-nodes.
- Performance for search and insert is now guaranteed to be \(O(\lg N)\).