Core Data Structures

Five routines run over arrays that keep doubling. Watch how each one's step count answers the doubling: the same, one more, twice, a bit over twice, four times. That answer is its order.

A sorted array answers a question with one read: the middle rules out half the cells. Watch the range halve to the target or close on nothing, and see why a scan needs n reads where this needs log n.

One array read as a tree that always knows its minimum: a push climbs, a pop sinks, and building from a batch costs less than pushing one by one, every hop bounded by the height.

A key's slot is computed from the key itself, so a lookup goes straight there. What happens when two keys want one slot, why the load factor governs every cost, and when the table doubles.

A forest of parent pointers answers 'are these two in the same set?' in a few hops: find climbs to a root, union hangs one root under another, and two tricks keep every tree nearly flat.

A search tree is only as fast as it is shallow. Watch sorted keys hang a plain tree into a chain, then watch an AVL tree rotate on the way back up and stay a few levels deep.

A sorted list with express lanes: coin flips at insertion set each key's tower, a lookup walks right and down in about 2 log n hops, and nothing ever rotates.

Two arrays make a set over small integers with O(1) insert, remove, membership, and clear, no clearing of memory needed: dense packs the members, sparse points each value at its slot.

A row of bits and a few hashes answer 'have I seen this?' with no false negatives and a tunable chance of a false positive, in space far smaller than the keys themselves.

A few rows of counters, each indexed by its own hash, estimate how often anything appeared in a stream: never below the truth, rarely far above it, in space that ignores the stream's length.

Count distinct items in a stream with a few bytes: hash each one, let the longest run of leading zeros in each bucket estimate the count, and average the buckets harmonically.

Insert into a tree without touching the old one: copy the path from the root, share every other subtree, and every version stays readable forever at a logarithmic cost per change.

The fewest coins for an amount, defined by its own smaller copies. Plain recursion solves the same amounts again and again; a memo solves each once, and a table needs no recursion at all.