Balanced Search Trees

Suppose you keep a million records and need to find one by its key. If they sit in a sorted array, binary search nails any lookup in about twenty comparisons. Wonderful — until you have to insert a new key in the middle, which means shifting half a million entries.

A plain binary search tree fixes inserts but has its own trap: feed it keys in sorted order and it degenerates into a linked list, turning every lookup back into a slow linear scan.

Balanced search trees are the answer to both problems at once. After every insertion or deletion they quietly reshape themselves so that the tree's height stays proportional to log n — meaning a lookup, an insert, and a delete each touch only a handful of nodes, even with billions of keys. This is the structure that indexes databases and filesystems.

Below is a small B-tree where every node holds at most three keys. Insert numbers and watch what happens: when a node overflows, it splits in two and pushes its middle key up to the parent. That single rule keeps every leaf at exactly the same depth.

<p class="hint">{{hint}}</p>
<div class="controls">
  <input id="key" type="number" placeholder="{{placeholder_key}}" />
  <button id="add" type="button">{{btn_insert}}</button>
  <button id="seq" type="button">{{btn_seq}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div class="stats">
  <span>{{stat_keys}} <b id="count">0</b></span>
  <span>{{stat_height}} <b id="height">0</b></span>
  <span>{{naive_pre}} <b id="naive">0</b> {{naive_post}}</span>
</div>
<div id="tree" class="tree"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.controls { display: flex; gap: .5rem; flex-wrap: wrap; align-items: center; margin-bottom: .6rem; }
input { font: 600 14px system-ui, sans-serif; padding: .4rem .55rem; width: 86px;
        border: 1px solid #adb1b8; border-radius: 8px; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats { font-size: .9rem; color: #444; display: flex; gap: 1.1rem; flex-wrap: wrap; margin-bottom: .8rem; }
.stats b { color: #1d3557; }
.tree { display: flex; flex-direction: column; gap: 1.4rem; align-items: center; padding: .4rem 0; overflow-x: auto; }
.level { display: flex; gap: 1.4rem; justify-content: center; flex-wrap: nowrap; }
.node { display: flex; border: 1px solid #cdd9e3; border-radius: 8px; overflow: hidden;
        background: #e8eef3; box-shadow: 0 1px 2px rgba(0,0,0,.08); }
.node .k { padding: .35rem .55rem; font: 700 15px ui-monospace, monospace; color: #1d3557;
           border-right: 1px solid #cdd9e3; min-width: 30px; text-align: center; }
.node .k:last-child { border-right: none; }
.node.flash { animation: pop .5s ease; }
@keyframes pop { 0% { background: #ffe08a; } 100% { background: #e8eef3; } }

// Code not found

Try inserting keys in sorted order (1, 2, 3, 4, …). A plain binary tree would grow into a tall thin chain; the B-tree instead stays short and wide. Watch the height counter — it barely moves while the number of keys climbs. That flat height is exactly why a lookup stays fast no matter how much data you pour in.

How fast is a balanced tree, really — and is this a settled question?

• Search, insert, delete are all $O(\log n)$. Because the height never exceeds a constant times log n, every operation walks one root-to-leaf path, so it scales beautifully: doubling the data adds just one level.
• The balancing is cheap. A split (in a B-tree) or a rotation (in an AVL or red-black tree) is a local, constant-time fix-up after each update — you never rebuild the whole tree.
• This is solved. The AVL tree (Adelson-Velsky & Landis, 1962) was the first; B-trees came from Bayer & McCreight (1970) for disk storage; red-black trees were introduced by Bayer (1972) and refined by Guibas & Sedgewick (1978). These aren't open problems — they are textbook, proven, everyday structures.
• No magic, just invariants. Each variant enforces a simple rule (heights differ by at most one; or no two red nodes in a row; or all leaves at the same depth) that mathematically forces logarithmic height.

The contrast with a hard problem like P vs NP is the point: here the efficient algorithm is known, simple, and provably optimal for comparison-based ordered search.

"Keep ordered data searchable while it changes" is one of computing's most universal needs, and balanced trees are the standard answer:

• Database indexes: PostgreSQL, MySQL, Oracle and SQLite all use B-trees (usually B+ trees) so a query can find rows among billions without scanning the table.
• Filesystems: NTFS, HFS+, Btrfs and others store directory entries and metadata in B-trees for fast lookups on disk.
• Language libraries: C++'s std::map/std::set and Java's TreeMap are red-black trees, giving ordered iteration plus $O(\log n)$ access out of the box.
• In-memory and key-value stores: ordered indexes, range queries, and schedulers lean on the same logarithmic guarantee.

Understand why a balanced tree stays short and you understand the engine under SQL query optimization and the pattern matching indexes that make search feel instant.

Balanced search trees are one of computer science's quiet triumphs: a handful of local rules — split a full node, rotate an unbalanced one — keep the tree's height proportional to log n forever. Search, insert and delete all stay fast no matter how much data arrives.

So the next time a database returns a row from a billion in milliseconds, you're watching a balanced tree at work. It isn't an open mystery like P vs NP; it's a problem we solved decades ago — and then built the digital world on top of.