2-3-4 Trees

What they are

A 2-3-4 tree is a balanced search tree where each node can store multiple keys. Because of that, it can keep its height under control as values are added. That makes searching and insertion efficient.

Why they matter in CS400

2-3-4 trees are useful because they give a clear example of how a tree can stay balanced while still supporting fast operations. They also connect to red-black trees, which represent similar balancing ideas in binary-tree form.

A few important things to remember

Simple example

During insertion, you compare the new value with the keys in each node and follow the correct branch downward. If a node is already full, it can split as part of the insertion process. This helps keep the tree balanced.

Diagram of a 2-3-4 tree

More information

Here is a page with a fuller explanation: UC Berkeley CS61B notes on 2-3-4 trees.