This site's Node-Linked Trees category holds twenty-three
entries, but only seven answer the same question: keep a set of comparable keys ordered,
supporting fast insert, search, and delete on any of them. Binary Search Tree, AVL Tree, Red-Black Tree, Splay Tree, Scapegoat Tree, B-Tree, and B+ Tree all answer it by comparing whole keys against
each other on the way down. Sixteen entries sit outside that comparison, each answering a different
question entirely — three of them the same different question, by three different routes,
and five more the same different question again, by five more. Trie — its own page draws the line directly: a trie "spends
one node per character, not one node per key," and never compares two whole keys against
each other at all. Ternary Search Tree
answers that exact same question (store strings, answer prefix queries) by turning each
character's branch decision into a small binary search — one node holding one character and three
pointers — instead of a trie's per-node array or map; its own page measures the two structures out
to always need the identical node count for the same word list, so the real tradeoff is what each
node costs to store, not how many exist. Radix Tree
answers it a third way: instead of changing what a node costs, it changes how many nodes exist at
all, collapsing every run of single-child trie nodes into one edge labeled with the whole shared
substring — its own page measures 14 nodes against a plain trie's 28 for the same word set. Merkle Tree isn't
about ordering or lookup by key at all — it answers "does this one item belong to this dataset,"
provable without the rest of the dataset, the same way the Range Query guide sets Binary Heap
aside before comparing the five entries that answer its own shared question. Rope isn't about a set of keys at all — it holds one mutable-
feeling string, and answers "index, split, or join this text efficiently," a question none of the
six comparable-key entries even attempt (they don't support O(1) concatenation of two whole trees,
and don't need to: rope's leaves aren't keys to compare, just chunks of one shared string). Cartesian Tree isn't about a set of keys either —
it's a Treap with the randomness removed, and its lowest common ancestor answers a stored array's
range-minimum queries, a structural trick rather than a comparison-driven set operation. Order Statistics Tree is a Treap with the
opposite move — keep the randomness, add one field (subtree size) — and it isn't about membership
either: it answers select(k) and rank(x), the k-th smallest stored value and how many are smaller
than x, neither of which any of the seven comparison entries can do without an O(n) full walk. Fibonacci Heap, Pairing Heap, Leftist Heap, Skew Heap, and Binomial Heap are all mergeable priority queues, not
ordered sets — none supports a general search for an arbitrary key at all, only
extract-min and, for three of the five, decrease-key — and they answer
their shared question by five deliberately different routes: Fibonacci Heap earns a fully proven
O(1) amortized decrease-key at the cost of marked bits and cascading cuts,
Pairing Heap keeps one merge rule and no bookkeeping at all but leaves its own exact bound an open
question, Leftist Heap doesn't build decrease-key at all, trading it for a worst-case
(not amortized) merge/insert/extract-min bound, Skew Heap goes past Leftist Heap's own
simplification — no augmented field at all, an unconditional child swap instead of a
compare-then-swap rule — settling for an amortized bound the same way Pairing Heap does, proven
instead of open, and Binomial Heap is the oldest of the five (Vuillemin, 1978, the structure
Fibonacci Heap was built to beat): a forest shaped exactly like the binary representation of its own
size, with every operation including decrease-key bounded worst-case rather than
amortized, the "no free lunch" combination none of the other four offer. See any of the five pages
for the full tradeoff. The remaining four all answer questions
about a tree's own shape rather than about a set of keys stored in one: Binary Lifting answers ancestor queries
(LCA(u, v)) on a fixed tree, Heavy-Light Decomposition flattens a
tree into array ranges so a range structure can answer path queries, Centroid Decomposition builds a second,
shallower tree over the same nodes to answer questions about every path at once, and Link-Cut Tree goes further still — the tree itself
isn't fixed, reusing splay tree's own rotations over a changing "preferred path" so
link/cut/findRoot can restructure the forest in any
interleaved order — none of the four ever compares two keys against each other to decide which way
to branch.
Does the structure live on disk, or behind a cache/page boundary where each node visit is expensive regardless of how cheap the comparison inside it is? If so, nothing else below matters — the shape of the tree itself needs to change. If not, does every single operation need its own worst-case guarantee, or is a guarantee over a long sequence of operations enough — and is access skewed toward a working set that isn't known in advance? If a per-operation guarantee is required, does the workload lean read-heavy or write-heavy? And if none of the above forces a choice, can the insertion order actually be trusted not to be sorted or adversarial? That last question is cheapest to answer but decides the least on its own — it's the fallback once the first three have already ruled everything else out.
Every other entry here is a binary tree — at most two children per node — so its cost
is dominated by how many comparisons it takes to walk root to leaf. A B-Tree changes what's being minimized: each node holds
several sorted keys at once and branches one more way than it has keys, trading a wider node (more
comparison work per visit) for a shallower tree (far fewer visits total). Its own page makes the
payoff concrete: at a minimum degree of t = 100, a million keys need a height of at
most 2 — three node reads, root included, to find any key among a million, against roughly 20
levels for the same key count in a perfectly balanced binary tree. That trade only pays off when a
node visit itself is expensive — one disk seek, one cache-line fetch past what already sits close
by — which is exactly why B-trees are sized to match a disk page and are the structure behind most
database indexes and filesystem directory trees. B-tree's own page is equally direct about the
other direction: "when there's no disk seek to amortize, the constant-factor cost of scanning
several keys per node buys nothing," and a binary structure like red-black tree is "simpler to
implement and just as fast in RAM." Reach for a B-tree specifically when node visits, not
comparisons, are the expensive resource; for anything purely in memory, skip to the next
question.
Once disk- or cache-backed storage is the answer, one more question decides between the two disk-shaped entries: does anything in the workload ask for a contiguous range, not just single-key lookups? A plain B-tree has no answer to that beyond repeating single-key search once per result. B+ Tree is the same node-visit-is-expensive trade taken one step further: internal nodes hold nothing but routing-key copies, every real key lives in a leaf, and the leaves are threaded into their own linked list — so a range query costs one descent plus a straight walk, with zero further internal-node reads no matter how many results come back. Its own page measures the gap directly: a 6-result range query touches 6 node visits total against 18 for the same 6 results as six independent single-key searches, the same 2 internal nodes re-read every time in the naive approach. That's not a reason to always prefer B+ Tree over plain B-Tree, though — the linked leaves and copy-then-recompute delete logic are extra bookkeeping with no payoff if every query really is a single-key lookup, in which case plain B-Tree does the identical job with one less structure to maintain.
The other three in-memory trees (AVL, red-black, and B-tree) all keep a shape invariant — a cached height, a color, a wide branching factor — enforced after every write specifically so that every single operation is bounded. Two entries give that up on purpose, in exchange for carrying zero per-node balance metadata, but they disagree about which operations get to be cheap and which pay the price.
A Splay Tree gives up the guarantee on
every operation, including reads: any single search, insert, or delete can legitimately
cost O(n), because every one of them restructures the tree — rotating whatever was
just touched all the way to the root. That buys a self-adjusting property none of the other entries
have: whatever was just accessed is cheap to reach again immediately after. Its own page measured
exactly when that trade pays off: walking a 1,000-node degenerate chain from deepest to shallowest
node once each, proper splaying takes 5,374 total comparison steps (~5.4 per access, consistent
with amortized O(log n)); a naive "rotate one level at a time" variant that looks
superficially similar takes 501,499 (~501.5 per access — O(n), exactly what splaying
exists to avoid). That gap only opens up over a sequence of accesses with real skew — a
single one-off lookup gets no benefit and no protection from the worst case.
A Scapegoat Tree gives up the guarantee on
writes only. It enforces the same kind of height rule AVL and red-black do — no node may sit
deeper than a computed limit — but restores it by occasionally flattening and rebuilding one whole
unbalanced subtree instead of rotating on every write, and only when an insert actually crosses the
line (or a run of deletes shrinks the tree far enough below its own high-water mark). Because that
check runs after every insert, a plain search is worst-case O(log n) at
all times — the same class of guarantee as AVL or red-black, not merely an amortized one the way a
splay tree's search is — while insert/delete stay amortized
O(log n), same shape as splay tree's guarantee, just reached by rebuilding instead of
restructuring on touch. Its own page measured the same kind of worst-case-sequence stress splay's
page did: inserting 1 through 2000 in ascending order produced a final height of 25 (against a
theoretical bound of 26.4), doing an average of 9.02 nodes of rebuild work per insert at the
conventional balance constant.
The two rarely compete for the same job, despite sharing "no per-node metadata": reach for a splay tree when access is genuinely skewed toward an unpredictable working set and even reads are allowed to cost more on a cold value; reach for a scapegoat tree when reads need their own worst-case bound but writes don't, and the per-node memory of AVL's height field or red-black's color bit is itself the thing being economized on. Neither is the default for a general-purpose container — as splay tree's own page notes, standard libraries reach for red-black trees instead, "precisely because they need the worst-case-per-operation guarantee splay trees don't offer," and the same reasoning rules out scapegoat tree's amortized-not-worst-case writes for that role. If neither of these apply — a per-operation guarantee actually is required — move to the next question.
Once every operation individually needs to stay O(log n), the choice is between AVL Tree and Red-Black Tree — both guarantee it, by bounding
height two different ways: AVL tracks a height number per node and enforces that every node's two
subtrees differ by at most 1; red-black colors every node red or black under four rules that bound
height more loosely. Red-black's own page names the trade directly: it "closes the same gap with a
looser rule, paid for in a different currency," accepting a somewhat deeper tree — its own
worst-case bound is 2·log₂(n+1) against AVL's roughly 1.45·log₂(n) — in
exchange for cheaper rebalancing: an AVL insert triggers at most one rotation, but an AVL
delete can require rebalancing every ancestor back to the root; red-black's fixup, insert
or delete, only ever walks one root-to-leaf path, and most of its steps are a plain recolor — an
O(1) field write, no pointer restructuring — rather than a rotation. Both pages
measured the same concrete case rather than just asserting the tradeoff: inserting 1 through 2000
in ascending order (the classic worst case for a plain BST) produces an AVL tree of height 11, but
a red-black tree of height 19, both checked against their own shipped code. That's the whole
decision in one number each way: AVL's stricter balance buys a measurably shallower tree — faster
for every future search — while red-black's looser rule buys cheaper writes. AVL's own page states
the resulting rule of thumb outright: reach for AVL "specifically when reads dominate writes";
red-black's own page states the mirror image just as directly: reach for red-black "anywhere writes
dominate reads" — which is also why most language standard libraries' ordered map/set types
(C++'s std::map, Java's TreeMap, the Linux kernel's rbtree) default to
red-black rather than AVL: a general-purpose container rarely gets to assume reads dominate.
If the structure lives entirely in memory, no single operation needs its own bound, and access
isn't especially skewed, a plain Binary Search
Tree is the simplest of the five to build — no rotations, no colors, no splaying, just "smaller
goes left, bigger goes right." The catch is the one every other entry on this page exists to close:
its own Pitfalls section shows that inserting already-sorted data turns the tree into a straight
line, with every operation degrading to O(n) — "exactly as bad as a linked list."
That's not a rare adversarial case; sorted or near-sorted input (imported data, timestamps,
auto-incrementing IDs) is common in practice, which is precisely the failure AVL's own page cites
as its reason to exist. A plain BST is only the right choice when the insertion order can actually
be trusted to stay unpredictable — genuinely randomized keys, or a workload where a rare bad case
is acceptable — not as a default "simple until proven otherwise" pick.
| Entry | Guarantee | Per-node overhead | Reach for it when |
|---|---|---|---|
| B-Tree | O(log_t n), guaranteed | up to 2t-1 keys, 2t child pointers | node visits (disk seeks, cache misses) dominate cost, not comparisons |
| B+ Tree | O(log_t n) search/insert/delete, O(log_t n + k/t) range scan, all guaranteed | up to 2t-1 keys, 2t child pointers (internal), plus one linked-list pointer (leaf) | same as B-Tree, plus the workload asks for contiguous ranges, not just single keys |
| Splay Tree | O(log n) amortized, single op up to O(n) | 2 child pointers + parent, no metadata | access is skewed toward an unpredictable working set, no per-op guarantee needed |
| Scapegoat Tree | search O(log n) guaranteed; insert/delete O(log n) amortized, up to O(n) | 2 child pointers, no metadata (2 counters shared tree-wide) | reads need a worst-case bound but writes don't, and per-node memory is the constraint |
| AVL Tree | O(log n), guaranteed, strict (height ±1) | 2 child pointers + cached height | reads dominate writes, want the shallowest tree |
| Red-Black Tree | O(log n), guaranteed, looser bound | 2 child pointers + parent + color bit | writes dominate reads, want cheaper rebalancing |
| Binary Search Tree | O(log n) average, O(n) worst case | 2 child pointers | insertion order is genuinely trusted not to be sorted or adversarial |