Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Binary search tree — where it appears

A tree in which every left descendant is smaller and every right one larger, so an in-order walk is sorted and a search follows one path. Its search follows one path, so its cost is its height — which for an unbalanced tree is decided by the order the keys arrived in.

Named by 4 essays across 2 fields — each of them below, with the objects they name alongside it.

level 1level 2level 3level 4level 5key 21search: 8 comparisons, 3 hops26 keys, p = 0.5, seed 2026081057 coin flips decided the shape

A structure made of coin flips

Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.

randomness · Randomness sorted insertion — height 62shuffled insertion — height 10truncated at depth 1663 keys, identical set, different arrival order62 deep against 10

The tree that is a list

A binary search tree gives logarithmic lookup. Build one from 128 keys in sorted order and it has height 127 — every node has one child, and a lookup is a linear scan. The failure is not gradual and it happens on the input people try first, which makes "O(log n) lookup" a claim about the insertion order rather than about the structure.

structures · Structure root, priority 0.9651.00.0prioritykey24 keys, sorted insertion, seed 20260810height 8 against an ideal of 4

The priority nobody supplied

Insert 4,096 sorted keys into a binary search tree and it reaches height 4,095, costing 8,386,560 comparisons to build. Give every key a second, random key and keep the tree heap-ordered on that instead, and the same insertion reaches height 26 for 32,750 comparisons. Nothing detected the imbalance, and nothing rebalanced.

structures · Structure levels on the path (outline) · transfers actually paid (filled)B = 411 levels · 6.99 transfers · 16,384 blocks residentB = 166 levels · 3.23 transfers · 4,096 blocks residentB = 644 levels · 1.99 transfers · 1,024 blocks residentB = 2563 levels · 1.30 transfers · 256 blocks residentB = 10243 levels · 1.01 transfers · 64 blocks residentbinary search over the same 4,194,304 keys: 20 transfersB = 1024, M = 65,536 (M/B = 64)20× between binary search and the widest tree

A tree with nodes the size of a block

A B-tree is a binary search tree that has read the hardware manual. Its node holds as many keys as fit in one transfer, so the height falls from log₂ n to log_B n — and the measured cost falls further still, to 1.01 transfers over four million keys, because the top of the tree is small enough to stay in memory. The comparison count goes up.

structures · Transfer

Named alongside it

The objects these essays reach for when they reach for this one.

Binary searchDistributionGuaranteeInsertion orderRotationSkip listTreapTree heightAmortised analysisB-treeBalanceBlock transfer

All concepts