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)\).