A 2–3–4 self-balancing search tree built from scratch in Java — guaranteed O(log n) insert, search, and delete.
┌─────────────┐
│ [19 | 53] │ ← 3-node (root)
└──────┬──────┘
┌───────────┼───────────┐
┌────┴────┐ ┌────┴────┐ ┌───┴──────────┐
│[5|11|13]│ │[29|31|41]│ │[67|71|83|89] │ ← 4-nodes
└─────────┘ └─────────┘ └──────────────┘
Balanced at every level — height = O(log n)
A 2–3–4 tree (also called a 2–4 tree) is a self-balancing multiway search tree where every node holds 1, 2, or 3 values and has 2, 3, or 4 children respectively. It maintains perfect balance by splitting 4-nodes on the way down during insertion and merging/rotating during deletion — guaranteeing O(log n) height at all times.
It is the direct structural equivalent of a red-black tree: every red-black tree is a 2–3–4 tree in disguise, which is why TreeSet (backed by a red-black tree) shows nearly identical benchmark performance.
| Node | Values | Children |
|---|---|---|
| 2-node | 1 | 2 (left, right) |
| 3-node | 2 | 3 (left, center, right) |
| 4-node | 3 | 4 (left, centerLeft, centerRight, right) |
TwoFourTree
│
├── TwoFourTreeItem Internal node class
│ ├── value1 / value2 / value3
│ ├── leftChild / centerChild / centerLeftChild / centerRightChild / rightChild
│ ├── isTwoNode() / isThreeNode() / isFourNode()
│ └── printInOrder(indent)
│
├── addValue(int) Insert — splits 4-nodes top-down
├── hasValue(int) Search — O(log n) traversal
├── deleteValue(int) Delete — merges/rotates via merge()
├── merge(node) Rebalance helper for deletion
└── printInOrder() In-order traversal for validation
Tested against Java's TreeSet (red-black tree) — structurally equivalent, JVM-tuned C internals:
| n | Structure | Add | Find | Delete |
|---|---|---|---|---|
| 100K | TwoFourTree | 13ms | 3ms | 4ms |
| 100K | TreeSet | 8ms | 2ms | 1ms |
| 1M | TwoFourTree | 153ms | 25ms | 28ms |
| 1M | TreeSet | 131ms | 20ms | 15ms |
| 10M | TwoFourTree | 2,140ms | 279ms | 342ms |
| 10M | TreeSet | 1,998ms | 364ms | 209ms |
At 10M elements,
TwoFourTreematches or beatsTreeSeton search — the two structures are asymptotically identical because a 2–3–4 tree is the conceptual foundation of the red-black tree. The gap on add/delete reflects JVM C-level optimizations inTreeSet, not algorithmic difference.
javac TwoFourTree.java App.java
java AppOutput includes:
- Static correctness test — inserts the first 24 primes, prints in-order, deletes 37, 73, and 97, prints again
- Full benchmark comparing
TwoFourTreevsTreeSetfrom 100 to 10M elements
.
├── TwoFourTree.java 2–3–4 tree implementation
├── App.java Correctness tests + benchmark driver
└── README.md