Treaps, Splay Trees & Skip Lists
AVL and red-black trees buy their guarantee with bookkeeping: a balance factor or a colour on every node, and a case analysis on every update that people get wrong for years. This lesson covers three structures that reach the same by a different route. A treap lets a coin decide the shape of the tree. A splay tree keeps no balance information at all and instead moves every node it touches to the root, paying for occasional slow operations with many fast ones. A skip list is not a tree at all, but a sorted linked list with randomly chosen express lanes, and it is what Redis uses for sorted sets and what LevelDB and RocksDB use for their in-memory write buffers.
You will implement each, prove why each is fast (a random-BST argument, a potential function, a backward analysis), and choose between them. Balanced BSTs: AVL & Red-Black Trees is the deterministic baseline; the short skip-list section in Advanced Data Structures is a good warm-up.
Why this exists
A balanced BST defends against the worst input an adversary can construct, with bookkeeping and a rotation case analysis that runs to a dozen cases once deletion is included. In the 1980s three groups asked whether the defence could be cheaper.
Raimund Seidel and Cecilia Aragon (FOCS 1989, journal version Algorithmica 1996) observed that a binary search tree built by inserting keys in random order is already balanced in expectation, with expected depth about . You cannot control the order in which users insert keys, but you can attach a random priority to every key and maintain the tree as if the keys had arrived in priority order. The result is the treap (tree + heap). Jean Vuillemin had described the same shape in 1980 as a Cartesian tree; Seidel and Aragon's contribution was using random priorities to get a dynamic, balanced search tree with fewer than two rotations per update on average.
Daniel Sleator and Robert Tarjan (Journal of the ACM, 1985) went the other way: store nothing, and after every access rotate the accessed node all the way to the root with a specific two-level rotation rule. Individual operations can take linear time, but any sequence of operations costs , and on skewed or local access patterns the splay tree does provably better than any fixed balanced tree.
William Pugh (Communications of the ACM 33(6), 1990) dropped trees entirely. A skip list is a sorted linked list where each node also appears, with probability , in a sparser list above it, and so on up. Searching starts in the sparsest list and drops down. Pugh's selling point was simplicity: insert and delete are local pointer splices with no rebalancing, which is also why skip lists became the standard building block for concurrent ordered maps (Java's ConcurrentSkipListMap) and for memtables in log-structured storage engines.
For interviews and contests there is a practical reason too: the treap's split and merge make it the easiest structure for problems that cut, paste and reverse ranges of a sequence, which standard-library trees do not support.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "ordered set with k-th smallest / rank", and your language has no order-statistic tree | Treap with subtree sizes (or __gnu_pbds in C++) |
| "cut a substring and paste it elsewhere", "move a block to the end", "rotate a range" | Implicit treap with split/merge |
| "reverse the subarray l..r", many times, then output | Implicit treap with a lazy reverse flag |
| "range sum / min over positions while the sequence is being rearranged" | Implicit treap with an aggregate field |
| "merge two ordered sets", "split a set at key x" | Treap split/merge (or join-based trees) |
| "design a skiplist" / "implement a sorted set without a tree" | Skip list |
| "concurrent sorted map", "many threads insert while others scan" | Lock-free skip list (ConcurrentSkipListMap) |
| "leaderboard with rank and range by score" | Skip list with spans (Redis ZRANK, ZRANGE) or treap with sizes |
| "recently accessed items are accessed again", "access pattern is skewed or sequential" | Splay tree (working-set and sequential-access theorems) |
| "dynamic trees: link, cut, path aggregate" | Link-cut trees, which are built from splay trees |
| "must be simple to code under time pressure, no worst-case requirement" | Treap: about 40 lines with split/merge |
The tell-tale sign of a treap problem is split: "cut at a key or position, do something, glue back".
Intuition & first principles
The random-BST insight
Insert 1 to 1000 into a plain BST in increasing order and you get a path of height 1000; in random order, the height is almost always in the 20s. A treap removes the dependence on arrival order by pretending the keys arrived in a random order of its own choosing. Every node stores a key and a priority drawn uniformly at random when the node is created. The tree satisfies two orders at once:
- BST order on keys: left subtree keys < node key < right subtree keys.
- Heap order on priorities: every node's priority is at least its children's (this lesson uses a max-heap; some texts use a min-heap, which is equivalent).
Uniqueness lemma. For distinct keys and distinct priorities there is exactly one treap. The root must be the node with the highest priority (heap order). That splits the remaining keys into those smaller than the root's key (which must form the left subtree, by BST order) and those larger (the right subtree), and the same argument applies recursively to each side.
The treap is therefore exactly the BST you would get by inserting the keys in decreasing order of priority. If priorities are independent and uniformly random, that is a uniformly random insertion order, and the treap is distributed exactly like a random BST, no matter in which order the user actually inserted or deleted keys. Everything known about random BSTs (expected depth , expected height ) applies.
Split and merge: the two primitives
A treap can be maintained with rotations, but the more useful implementation uses two primitives:
split(t, k)returns two treaps: all keys< k, and all keys>= k.merge(a, b)joins two treaps when every key inais smaller than every key inb.
merge is a two-way decision: the root of the result must be whichever of the two roots has the higher priority. If it is a's root, its left subtree stays and its right subtree becomes merge(a.right, b); otherwise symmetrically. split walks one root-to-leaf path: if the root key is < k, the root and its whole left subtree go to the left result, and we recurse into the right subtree to find where to cut.
With these two, every operation is a short composition:
| Operation | As split/merge |
|---|---|
insert(x) | a, b = split(t, x); t = merge(merge(a, node(x)), b) |
erase(x) | a, b = split(t, x); mid, c = split(b, x + 1); t = merge(a, c) |
| union of two sets | recursive split/merge, expected |
| cut positions l..r and paste at end | (implicit treap) split twice, merge in a new order |
Implicit keys: a treap as a sequence
Drop the keys and store subtree sizes. A node's position is the number of nodes before it in inorder, computable from sizes while descending, and split(t, k) means "first k elements left". The tree is now a sequence (a rope) with insert, delete, concatenate and cut at any position in expected. A lazy flag meaning "swap the children of this subtree" gives range reversal: split out l..r, flip the flag, merge back.
Splaying: move to root, but carefully
A splay tree's only rule is: after accessing node x, rotate x to the root. The naive version (rotate x with its parent repeatedly) is not good enough: on a path it can leave a path behind, and a sequence of accesses can cost each. Sleator and Tarjan's insight was to look two levels up and treat the zig-zig case (x and its parent are both left children, or both right children) specially: rotate the parent first, then x. That single change roughly halves the depth of every node on the access path, and is exactly what makes the amortized bound work.
The analogy is a move-to-front list; the precise statement is the access lemma below.
Skip lists: express lanes on a linked list
A sorted linked list costs to search. Add a list of every other node and you skip two at a time, dropping down when you would overshoot; add every fourth node above that, and so on: with levels this is binary search on a linked list. Keeping "exactly every other node" under inserts is as hard as balancing, so Pugh made it probabilistic: on insert, flip coins to decide how many levels the node joins. On average a fraction of each level appears in the next, which is all the analysis needs.
Mechanics
Treap insertion, by hand
The diagram is the treap after inserting seven keys with these (key : priority) pairs, in this order: 40:62, 20:91, 70:35, 10:17, 30:74, 60:88, 80:50. Priorities are written small for readability; in a real implementation they are 32- or 64-bit random numbers.
flowchart TD
N20["20 : 91"] -->|"L"| N10["10 : 17"]
N20 -->|"R"| N60["60 : 88"]
N60 -->|"L"| N30["30 : 74"]
N60 -->|"R"| N80["80 : 50"]
N30 -->|"R"| N40["40 : 62"]
N80 -->|"L"| N70["70 : 35"]
Inorder gives the sorted keys, and every parent's priority beats its children's. It is the BST you get by inserting in priority order 20, 60, 30, 40, 80, 10, 70.
The trace uses the "descend, then split" insertion: walk down as in a BST insert; at the first node whose priority is lower than the new node's, split that subtree at the new key and hang the halves under the new node. Computed by script; the tree column is preorder k(left,right), - for an empty child.
| Step | Insert | Path / action | Tree after (preorder) | Height |
|---|---|---|---|---|
| 1 | 40 : 62 | empty tree, becomes root | 40 | 1 |
| 2 | 20 : 91 | 91 beats root 40:62, split old tree at 20 | 20(-,40) | 2 |
| 3 | 70 : 35 | 20:91 → 40:62 → empty slot | 20(-,40(-,70)) | 3 |
| 4 | 10 : 17 | 20:91 → empty slot | 20(10,40(-,70)) | 3 |
| 5 | 30 : 74 | 20:91 → 74 beats 40:62, split 40(-,70) at 30 | 20(10,30(-,40(-,70))) | 4 |
| 6 | 60 : 88 | 20:91 → 88 beats 30:74, split 30(-,40(-,70)) at 60 | 20(10,60(30(-,40),70)) | 4 |
| 7 | 80 : 50 | 20:91 → 60:88 → 50 beats 70:35, split 70 at 80 | 20(10,60(30(-,40),80(70,-))) | 4 |
In step 6 one split at 60 sends 30 and 40 left and 70 right in a single pass. A rotation-based insert reaches the same tree (uniqueness lemma).
The split/merge decomposition of erase(x):
flowchart LR
T["treap t"] -->|"split at x"| A["a: keys below x"]
T -->|"split at x"| B["b: keys from x up"]
B -->|"split at x+1"| M["mid: just x, or empty"]
B -->|"split at x+1"| C["c: keys above x"]
A --> J["merge a and c"]
C --> J
M -->|"discard"| G["garbage"]
J --> R["new treap"]
Splaying, by hand
There are three cases, depending on where x sits relative to its parent p and grandparent g:
- Zig:
pis the root. Rotatexonce. - Zig-zig:
xandpare both left children (or both right children). Rotatepovergfirst, thenxoverp. - Zig-zag:
xis a right child andpa left child, or vice versa. Rotatexoverp, thenxoverg(the standard double rotation from AVL trees).
flowchart TD
subgraph ZZB["zig-zig, before"]
g1["g"] --> p1["p"]
g1 --> D1["D"]
p1 --> x1["x"]
p1 --> C1["C"]
x1 --> A1["A"]
x1 --> B1["B"]
end
subgraph ZZA["zig-zig, after: rotate p, then x"]
x2["x"] --> A2["A"]
x2 --> p2["p"]
p2 --> B2["B"]
p2 --> g2["g"]
g2 --> C2["C"]
g2 --> D2["D"]
end
flowchart TD
subgraph ZGB["zig-zag, before"]
g3["g"] --> p3["p"]
g3 --> D3["D"]
p3 --> A3["A"]
p3 --> x3["x"]
x3 --> B3["B"]
x3 --> C3["C"]
end
subgraph ZGA["zig-zag, after: rotate x twice"]
x4["x"] --> p4["p"]
x4 --> g4["g"]
p4 --> A4["A"]
p4 --> B4["B"]
g4 --> C4["C"]
g4 --> D4["D"]
end
In every diagram the inorder sequence (A, x, B, p, C, g, D for zig-zig; A, p, B, x, C, g, D for zig-zag) is unchanged, which is why rotations preserve BST order.
Trace: splay the deepest node of a path. Start with the worst possible shape for 7 keys, a left path with 7 at the root and 1 at depth 6, and access key 1. The potential column is , the sum over all nodes of the log of their subtree size; the proof section explains why it is the right measure. Computed by script; height is in edges.
| Step | Case | Tree after (preorder) | Height | |
|---|---|---|---|---|
| start | – | 7(6(5(4(3(2(1,-),-),-),-),-),-) | 6 | 12.30 |
| 1 | zig-zig (x=1, p=2, g=3) | 7(6(5(4(1(-,2(-,3)),-),-),-),-) | 6 | 12.30 |
| 2 | zig-zig (x=1, p=4, g=5) | 7(6(1(-,4(2(-,3),5)),-),-) | 5 | 10.71 |
| 3 | zig-zig (x=1, p=6, g=7) | 1(-,6(4(2(-,3),5),7)) | 4 | 8.39 |
Six rotations brought 1 to the root and the nodes on the access path now sit at roughly half their old depth. The potential dropped by 3.91, so the amortized cost was , under the access-lemma bound . Now access key 3 (depth 3):
| Step | Case | Tree after (preorder) | Height | |
|---|---|---|---|---|
| 1 | zig-zag (x=3, p=2, g=4) | 1(-,6(3(2,4(-,5)),7)) | 4 | 8.39 |
| 2 | zig-zag (x=3, p=6, g=1) | 3(1(-,2),6(4(-,5),7)) | 3 | 6.81 |
Four rotations, potential down 1.58, amortized 2.42, and the tree is nearly balanced. Naive single-rotation "move to root" would have left a path of length 5 under the new root after the first access.
Skip list search, by hand
A fixed skip list with keys 3, 7, 12, 19, 25, 31, 40, 48 and node heights 1, 3, 1, 2, 1, 4, 1, 2 (in a real list the heights are random):
flowchart LR
subgraph L4["level 4"]
h4["head"] --> a31["31"]
end
subgraph L3["level 3"]
h3["head"] --> b7["7"] --> b31["31"]
end
subgraph L2["level 2"]
h2["head"] --> c7["7"] --> c19["19"] --> c31["31"] --> c48["48"]
end
subgraph L1["level 1"]
h1["head"] --> d3["3"] --> d7["7"] --> d12["12"] --> d19["19"] --> d25["25"] --> d31["31"] --> d40["40"] --> d48["48"]
end
Search for 25. Start at the head on the top level. At each level, move right while the next key is smaller than the target; when the next key is not smaller (or there is none), drop one level. On level 1, the next node is the answer if its key equals the target. Computed by script:
| Step | Level | At | Next key | Decision |
|---|---|---|---|---|
| 1 | 4 | head | 31 | 31 ≥ 25: drop down |
| 2 | 3 | head | 7 | 7 < 25: move right |
| 3 | 3 | 7 | 31 | 31 ≥ 25: drop down |
| 4 | 2 | 7 | 19 | 19 < 25: move right |
| 5 | 2 | 19 | 31 | 31 ≥ 25: drop down |
| 6 | 1 | 19 | 25 | 25 ≥ 25: stop, next key equals target, found |
Six comparisons, no better than a level-1 scan at this size; the gain shows at scale (about 40 comparisons instead of 500,000 for a million keys, measured below).
Insert remembers the last node visited on each level (the predecessors), draws a random height h, and splices the node in after the predecessor on levels 1..h. Delete unlinks the node after each predecessor. Neither touches anything else, which is why skip lists suit fine-grained locking and lock-free updates.
The ladder: brute force → better → optimal
Two problems drive this lesson. The first: maintain a dynamic set of keys under insert, delete, membership and "k-th smallest", with up to to operations. The second: maintain a sequence under "reverse positions l..r" and "move block l..r to the end".
Rung 1: sorted array
Membership is and k-th is , but insert and delete shift elements, each. memmove is fast, so this survives up to around elements; Python's sortedcontainers.SortedList (a list of sorted sublists) refines the idea and competes with trees thanks to cache behaviour. For sequences, reversals of length cost .
Rung 2: plain BST
per operation: on random input, on sorted input (timestamps, auto-increment ids), which is common.
Rung 3: randomized or self-adjusting balance
- Treap: expected whatever the input order, since the shape depends only on the priorities. The implicit version does each reversal or block move with a constant number of splits and merges.
- Splay tree: amortized , better on skewed access; also supports split/join, but needs parent pointers.
- Skip list: expected ; rank and k-th need span counters (Redis does this); no natural range reversal.
| Approach | Insert/delete | Search | k-th / rank | Range reverse | Guarantee |
|---|---|---|---|---|---|
| Sorted array | / | worst case | |||
| Plain BST | , up to | with sizes | no | none | |
| AVL / red-black | with sizes | no (split/join possible but rarely implemented) | worst case | ||
| Treap (keyed / implicit) | implicit | expected, any input | |||
| Splay tree | amortized | ||||
| Skip list | with spans | no | expected, any input |
The step from rung 2 to rung 3 is the same in all three: cost no longer depends on input order. Treaps and skip lists hide behind coin flips; the splay tree lets the adversary choose and proves every choice is paid for.
Correctness
Split and merge preserve both invariants
Claim. If t is a treap, split(t, k) returns two treaps a and b with every key of a below k, every key of b at least k, and together the same node set.
Proof by induction on the height of t. Empty t: both outputs empty. Otherwise suppose t.key < k (the other case is symmetric). Then t and its whole left subtree belong in a. By induction split(t.right, k) returns valid treaps r1 (keys < k) and r2 (keys ≥ k). We set t.right = r1. BST order holds at t because every key in r1 came from t's right subtree, so it exceeds t.key. Heap order holds because r1's root was a descendant of t, so its priority is at most t's. r2 is returned unchanged as b. ∎
Claim. If a and b are treaps and every key in a is below every key in b, merge(a, b) is a treap on the union.
Proof by induction on height(a) + height(b). If either is empty, return the other. Otherwise the root of the result must have the maximum priority, which is the larger of the two roots' priorities; say it is a's. Keep a.left, and set a.right = merge(a.right, b), valid by induction. Every key of the new right subtree exceeds a.key (those from a.right by a's BST order, those from b by the precondition), and its root is either a.right's root or b's root, each with priority at most a's. ∎
insert and erase are compositions of these, so they are correct as long as their preconditions on key ranges hold, which the split boundaries guarantee.
Expected depth of a treap node
Number the keys in sorted order. Key is a proper ancestor of key if and only if has the highest priority among the keys between and inclusive.
Why: the keys between and stay in one subtree until one of them becomes a subtree root (a root outside the range sends the whole range to one side). That first root is the range's highest-priority key. If it is , is an ancestor of ; if it is or anything strictly between, is not an ancestor of .
With i.i.d. random priorities, each of the keys in the range is equally likely to hold the maximum, so
By linearity of expectation, the expected depth (number of proper ancestors) of key is
where . Every operation walks one or two root-to-node paths, so it is expected. The expected number of rotations in a rotation-based insertion (the right spine of the new node's left subtree plus the left spine of its right subtree) is less than 2 (Seidel and Aragon); five runs of 100,000 random insertions averaged 1.986 to 2.006, consistent with a mean just below 2.
The argument ignores the order of operations, deletions included: after any update sequence the treap is distributed like a fresh random BST on the current keys. A plain BST with Hibbard deletion (replace by successor) lacks this; Eppinger (1983) observed it drifting toward worse balance under random insert/delete pairs.
Measured shape (one random treap per size, computed by script; depth in edges):
| Average depth | (exact expectation) | Height | |||
|---|---|---|---|---|---|
| 1,000 | 10.15 | 10.99 | 19 | 29.8 | 10.0 |
| 10,000 | 15.04 | 15.58 | 30 | 39.7 | 13.3 |
| 100,000 | 19.54 | 20.18 | 36 | 49.6 | 16.6 |
| 1,000,000 | 25.37 | 24.79 | 55 | 59.6 | 19.9 |
The constant 4.311 is Devroye's (1986) asymptotic height of random BSTs; Reed (2003) refined it to , which is why measured heights sit below . The average depth, about , is what typical operations pay: roughly 39% more comparisons than a perfectly balanced tree.
The access lemma for splay trees
Give each node a size , the number of nodes in its subtree, and a rank . Define the potential of the tree as . The amortized cost of an operation is its actual cost (rotations) plus the change in potential, . Summed over a sequence, the potential terms telescope, so total actual cost = total amortized cost + .
Access lemma (Sleator & Tarjan). Splaying node in a tree with root has amortized cost at most .
The proof bounds each step. Write and for ranks before and after a step. Only , , change rank, and equals the old rank of the subtree root (, or for zig). One fact does all the work: for positive , with , (by concavity, ).
Zig-zig (cost 2). . Use and : . 's old subtree and 's new subtree are disjoint parts of 's new subtree, so , giving . Substituting, : the 2 rotations are paid for entirely by the potential drop, which is why zig-zig, not two plain rotations of x, is essential.
Zig-zag (cost 2). . After the step and are the two children of , so , giving . Hence .
Zig (cost 1, happens at most once, at the end). since . So .
Summing over the steps, the terms telescope from 's original rank up to the rank of the whole tree, and the appears at most once: total amortized cost . ∎
Consequences. accesses cost at most amortized plus the initial potential (at most ): total, the balance theorem. Insert and delete change the potential by only more. The lemma holds for any positive weights in place of unit weights, and clever weights give stronger theorems for the same algorithm:
- Static optimality: weight each key by its access frequency . The total cost becomes , which is within a constant factor of the best fixed BST for that access distribution, even though the splay tree never learned the distribution.
- Working set: accessing an item that was last accessed distinct items ago costs amortized.
- Sequential access (Tarjan 1985): accessing all keys in order costs total. Measured with the implementation below, a full in-order scan cost 4.37 to 4.41 rotations per key for from to , under the bound proved by Elmasry (2004).
- Dynamic finger (Cole, 2000, a long and difficult proof): accessing key right after key costs amortized.
The dynamic optimality conjecture, that splay trees are within a constant factor of the best possible dynamic BST algorithm on every access sequence, has been open since 1985.
Expected search cost of a skip list
Pugh's analysis traces the search path backwards, from the found node up and to the left to the head. At each node on the way back, either the node has another level above it (probability , and we move up) or it does not (probability , and the path came from the left, so we move left). Let be the expected number of steps to climb levels in an unbounded list:
Let . Climbing to level costs at most ; leftward moves above it are bounded by the number of nodes at level or higher, expected at most ; and the expected number of levels above is at most . Pugh's bound on the expected search cost is
The leading term is . The factor is for and for , identical (the minimum, at , is ). Pointers per node are : 2 versus 1.33. So gives the same expected cost with a third fewer pointers, at the price of more variance; Pugh recommended it unless variability matters, and Redis and LevelDB use it.
Measured (one random list per row, 2,000 random searches each, steps = comparisons including the "drop down" comparisons; computed by script):
| Levels used | Pointers per node | Average steps | Pugh's bound | ||
|---|---|---|---|---|---|
| 100,000 | 1/2 | 18 | 2.003 | 33.8 | 35.2 |
| 100,000 | 1/4 | 9 | 1.333 | 28.5 | 34.6 |
| 1,000,000 | 1/2 | 20 | 2.003 | 39.7 | 41.9 |
| 1,000,000 | 1/4 | 11 | 1.335 | 38.5 | 41.2 |
Smaller lists do not always land under the bound. At the same script measured 29.0 steps against a bound of 28.6. The bound is on the expected cost, and one random list can be unlucky. The search here also starts from the list's actual top level, which can sit above , so it counts a few climbing steps the analysis charges differently.
About 40 comparisons at a million keys, versus about 20 for a perfectly balanced BST and 26 for a treap; since each step dereferences a different node, cache misses decide real performance.
Complexity
| Structure | Search | Insert | Delete | Split / merge | Extra space per node | Kind of bound |
|---|---|---|---|---|---|---|
| Treap | , < 2 rotations | priority (+ size) | expected, over the structure's own coins | |||
| Splay tree | none (parent pointer if bottom-up) | amortized; a single op can be | ||||
| Skip list | by cutting each level | pointers on average | expected; high probability with max level | |||
| AVL / red-black | with join-based code | balance bit(s) | worst case |
A few points the table hides:
- "Expected" is over the structure's coins, not the input. No input is bad for a treap or skip list if the adversary cannot predict the priorities or levels, and the probability of height above falls off polynomially for large enough .
- Splay trees mutate on reads: memory writes on every lookup, cache-line invalidation across cores, no lock-free readers, and a single access can cost .
- Space. Treap: key, two pointers, priority (plus size for order statistics). Skip list at : 1.33 forward pointers on average. Splay: nothing extra, but bottom-up splaying needs parent pointers.
- Cache behaviour. All three chase pointers to scattered nodes; many-keys-per-node layouts (B-trees,
sortedcontainers) win on read-heavy workloads. LevelDB and RocksDB allocate skip-list nodes from an arena to improve locality.
Implementation
Treap with split/merge (canonical)
An ordered set of integers with insert, erase, contains, kth (0-indexed), rank (number of keys below a value), and an invariant checker. Priorities come from a 32-bit xorshift generator with the same seed in all four languages, so the four implementations build the identical tree; the test asserts its height (21 nodes on the longest path after inserting 1 to 1000 in sorted order, the input that would make a plain BST 1000 deep).
from __future__ import annotations
class XorShift32:
"""Deterministic 32-bit xorshift generator, identical in all four languages."""
def __init__(self, seed: int = 2463534242) -> None:
self.state = seed
def next(self) -> int:
x = self.state
x ^= (x << 13) & 0xFFFFFFFF
x ^= x >> 17
x ^= (x << 5) & 0xFFFFFFFF
self.state = x
return x
class Node:
__slots__ = ("key", "prio", "size", "left", "right")
def __init__(self, key: int, prio: int) -> None:
self.key = key
self.prio = prio
self.size = 1
self.left: Node | None = None
self.right: Node | None = None
def size(t: Node | None) -> int:
return t.size if t else 0
def pull(t: Node) -> None:
t.size = 1 + size(t.left) + size(t.right)
def split(t: Node | None, key: int) -> tuple[Node | None, Node | None]:
"""Split into (keys < key, keys >= key)."""
if t is None:
return None, None
if t.key < key:
a, b = split(t.right, key)
t.right = a
pull(t)
return t, b
a, b = split(t.left, key)
t.left = b
pull(t)
return a, t
def merge(a: Node | None, b: Node | None) -> Node | None:
"""Every key in a must be smaller than every key in b."""
if a is None:
return b
if b is None:
return a
if a.prio > b.prio:
a.right = merge(a.right, b)
pull(a)
return a
b.left = merge(a, b.left)
pull(b)
return b
class Treap:
def __init__(self, seed: int = 2463534242) -> None:
self.root: Node | None = None
self.rng = XorShift32(seed)
def __len__(self) -> int:
return size(self.root)
def contains(self, key: int) -> bool:
t = self.root
while t:
if key == t.key:
return True
t = t.left if key < t.key else t.right
return False
def insert(self, key: int) -> bool:
if self.contains(key):
return False
a, b = split(self.root, key)
self.root = merge(merge(a, Node(key, self.rng.next())), b)
return True
def erase(self, key: int) -> bool:
a, b = split(self.root, key) # a < key <= b
mid, c = split(b, key + 1) # mid == key, c > key
self.root = merge(a, c)
return mid is not None
def kth(self, k: int) -> int:
"""0-indexed k-th smallest key."""
if not 0 <= k < len(self):
raise IndexError(k)
t = self.root
while t:
ls = size(t.left)
if k < ls:
t = t.left
elif k == ls:
return t.key
else:
k -= ls + 1
t = t.right
raise AssertionError("unreachable")
def rank(self, key: int) -> int:
"""Number of keys strictly smaller than key."""
r, t = 0, self.root
while t:
if t.key < key:
r += size(t.left) + 1
t = t.right
else:
t = t.left
return r
def inorder(self) -> list[int]:
out: list[int] = []
stack: list[Node] = []
t = self.root
while stack or t:
while t:
stack.append(t)
t = t.left
t = stack.pop()
out.append(t.key)
t = t.right
return out
def height(self) -> int:
def h(t: Node | None) -> int:
return 0 if t is None else 1 + max(h(t.left), h(t.right))
return h(self.root)
def check(self) -> None:
"""Assert BST order, heap order on priorities and correct sizes."""
def go(t: Node | None, lo: int | None, hi: int | None) -> int:
if t is None:
return 0
assert lo is None or t.key > lo, "BST order broken"
assert hi is None or t.key < hi, "BST order broken"
for c in (t.left, t.right):
assert c is None or c.prio <= t.prio, "heap order broken"
s = 1 + go(t.left, lo, t.key) + go(t.right, t.key, hi)
assert s == t.size, "size field wrong"
return s
go(self.root, None, None)
if __name__ == "__main__":
t = Treap()
added = [t.insert(k) for k in [50, 30, 70, 20, 40, 60, 80, 30]]
assert added == [True] * 7 + [False]
assert len(t) == 7 and t.inorder() == [20, 30, 40, 50, 60, 70, 80]
assert (t.kth(0), t.kth(3), t.kth(6)) == (20, 50, 80)
assert t.rank(55) == 4 and t.rank(20) == 0 and t.rank(100) == 7
assert t.contains(40) and not t.contains(45)
assert t.erase(30) and not t.erase(35)
assert t.inorder() == [20, 40, 50, 60, 70, 80]
t.check()
big = Treap()
for k in range(1, 1001): # sorted input: the worst case for a plain BST
big.insert(k)
big.check()
assert big.height() == 21, big.height()
for k in range(2, 1001, 2):
assert big.erase(k)
big.check()
assert len(big) == 500 and big.kth(0) == 1 and big.kth(499) == 999
assert big.rank(500) == 250
print("treap OK")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
public class Treap {
private static final class Node {
final int key;
final long prio;
int size = 1;
Node left, right;
Node(int key, long prio) { this.key = key; this.prio = prio; }
}
private Node root;
private int state = (int) 2463534242L; // xorshift32 state, same seed as the other languages
private long nextPrio() {
int x = state;
x ^= x << 13;
x ^= x >>> 17;
x ^= x << 5;
state = x;
return Integer.toUnsignedLong(x);
}
private static int size(Node t) { return t == null ? 0 : t.size; }
private static void pull(Node t) { t.size = 1 + size(t.left) + size(t.right); }
// Returns {keys < key, keys >= key}.
private static Node[] split(Node t, int key) {
if (t == null) return new Node[] {null, null};
if (t.key < key) {
Node[] p = split(t.right, key);
t.right = p[0];
pull(t);
return new Node[] {t, p[1]};
}
Node[] p = split(t.left, key);
t.left = p[1];
pull(t);
return new Node[] {p[0], t};
}
private static Node merge(Node a, Node b) {
if (a == null) return b;
if (b == null) return a;
if (a.prio > b.prio) {
a.right = merge(a.right, b);
pull(a);
return a;
}
b.left = merge(a, b.left);
pull(b);
return b;
}
public int size() { return size(root); }
public boolean contains(int key) {
Node t = root;
while (t != null) {
if (key == t.key) return true;
t = key < t.key ? t.left : t.right;
}
return false;
}
public boolean insert(int key) {
if (contains(key)) return false;
Node[] p = split(root, key);
root = merge(merge(p[0], new Node(key, nextPrio())), p[1]);
return true;
}
public boolean erase(int key) {
Node[] ab = split(root, key);
Node[] mc = split(ab[1], key + 1);
root = merge(ab[0], mc[1]);
return mc[0] != null;
}
public int kth(int k) {
if (k < 0 || k >= size()) throw new IndexOutOfBoundsException(k);
Node t = root;
while (true) {
int ls = size(t.left);
if (k < ls) t = t.left;
else if (k == ls) return t.key;
else { k -= ls + 1; t = t.right; }
}
}
public int rank(int key) {
int r = 0;
Node t = root;
while (t != null) {
if (t.key < key) { r += size(t.left) + 1; t = t.right; }
else t = t.left;
}
return r;
}
public List<Integer> inorder() {
List<Integer> out = new ArrayList<>();
ArrayDeque<Node> stack = new ArrayDeque<>();
Node t = root;
while (!stack.isEmpty() || t != null) {
while (t != null) { stack.push(t); t = t.left; }
t = stack.pop();
out.add(t.key);
t = t.right;
}
return out;
}
private static int height(Node t) { return t == null ? 0 : 1 + Math.max(height(t.left), height(t.right)); }
public int height() { return height(root); }
private static int check(Node t, Integer lo, Integer hi) {
if (t == null) return 0;
require(lo == null || t.key > lo, "BST order broken");
require(hi == null || t.key < hi, "BST order broken");
require(t.left == null || t.left.prio <= t.prio, "heap order broken");
require(t.right == null || t.right.prio <= t.prio, "heap order broken");
int s = 1 + check(t.left, lo, t.key) + check(t.right, t.key, hi);
require(s == t.size, "size field wrong");
return s;
}
public void check() { check(root, null, null); }
static void require(boolean ok, String msg) {
if (!ok) throw new AssertionError(msg);
}
public static void main(String[] args) {
Treap t = new Treap();
int[] keys = {50, 30, 70, 20, 40, 60, 80, 30};
for (int i = 0; i < keys.length; i++) require(t.insert(keys[i]) == (i < 7), "insert result");
require(t.size() == 7, "size");
require(t.inorder().equals(List.of(20, 30, 40, 50, 60, 70, 80)), "inorder");
require(t.kth(0) == 20 && t.kth(3) == 50 && t.kth(6) == 80, "kth");
require(t.rank(55) == 4 && t.rank(20) == 0 && t.rank(100) == 7, "rank");
require(t.contains(40) && !t.contains(45), "contains");
require(t.erase(30) && !t.erase(35), "erase");
require(t.inorder().equals(List.of(20, 40, 50, 60, 70, 80)), "inorder after erase");
t.check();
Treap big = new Treap();
for (int k = 1; k <= 1000; k++) big.insert(k);
big.check();
require(big.height() == 21, "height " + big.height());
for (int k = 2; k <= 1000; k += 2) require(big.erase(k), "erase even");
big.check();
require(big.size() == 500 && big.kth(0) == 1 && big.kth(499) == 999, "after erase");
require(big.rank(500) == 250, "rank 500");
System.out.println("treap OK");
}
}
#include <algorithm>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <stdexcept>
#include <utility>
#include <vector>
static void require(bool ok, const char* msg) {
if (!ok) { std::fprintf(stderr, "check failed: %s\n", msg); std::exit(1); }
}
class Treap {
struct Node {
int key;
std::uint32_t prio;
int size = 1;
Node* left = nullptr;
Node* right = nullptr;
Node(int k, std::uint32_t p) : key(k), prio(p) {}
};
Node* root = nullptr;
std::uint32_t state = 2463534242u; // xorshift32, same seed everywhere
std::vector<std::unique_ptr<Node>> pool; // owns every node ever allocated
std::uint32_t nextPrio() {
std::uint32_t x = state;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return state = x;
}
static int sz(Node* t) { return t ? t->size : 0; }
static void pull(Node* t) { t->size = 1 + sz(t->left) + sz(t->right); }
// (keys < key, keys >= key)
static std::pair<Node*, Node*> split(Node* t, int key) {
if (!t) return {nullptr, nullptr};
if (t->key < key) {
auto [a, b] = split(t->right, key);
t->right = a;
pull(t);
return {t, b};
}
auto [a, b] = split(t->left, key);
t->left = b;
pull(t);
return {a, t};
}
static Node* merge(Node* a, Node* b) {
if (!a) return b;
if (!b) return a;
if (a->prio > b->prio) { a->right = merge(a->right, b); pull(a); return a; }
b->left = merge(a, b->left);
pull(b);
return b;
}
static int height(Node* t) { return t ? 1 + std::max(height(t->left), height(t->right)) : 0; }
static int check(Node* t, const int* lo, const int* hi) {
if (!t) return 0;
require(!lo || t->key > *lo, "BST order broken");
require(!hi || t->key < *hi, "BST order broken");
require(!t->left || t->left->prio <= t->prio, "heap order broken");
require(!t->right || t->right->prio <= t->prio, "heap order broken");
int s = 1 + check(t->left, lo, &t->key) + check(t->right, &t->key, hi);
require(s == t->size, "size field wrong");
return s;
}
static void inorder(Node* t, std::vector<int>& out) {
if (!t) return;
inorder(t->left, out);
out.push_back(t->key);
inorder(t->right, out);
}
public:
int size() const { return sz(root); }
bool contains(int key) const {
for (Node* t = root; t; t = key < t->key ? t->left : t->right)
if (key == t->key) return true;
return false;
}
bool insert(int key) {
if (contains(key)) return false;
pool.push_back(std::make_unique<Node>(key, nextPrio()));
auto [a, b] = split(root, key);
root = merge(merge(a, pool.back().get()), b);
return true;
}
bool erase(int key) { // the detached node stays in the pool and is freed with the treap
auto [a, b] = split(root, key);
auto [mid, c] = split(b, key + 1);
root = merge(a, c);
return mid != nullptr;
}
int kth(int k) const {
if (k < 0 || k >= size()) throw std::out_of_range("kth");
Node* t = root;
while (true) {
int ls = sz(t->left);
if (k < ls) t = t->left;
else if (k == ls) return t->key;
else { k -= ls + 1; t = t->right; }
}
}
int rank(int key) const {
int r = 0;
for (Node* t = root; t;) {
if (t->key < key) { r += sz(t->left) + 1; t = t->right; }
else t = t->left;
}
return r;
}
std::vector<int> inorder() const { std::vector<int> v; inorder(root, v); return v; }
int height() const { return height(root); }
void check() const { check(root, nullptr, nullptr); }
};
int main() {
Treap t;
int keys[] = {50, 30, 70, 20, 40, 60, 80, 30};
for (int i = 0; i < 8; i++) require(t.insert(keys[i]) == (i < 7), "insert result");
require(t.size() == 7, "size");
require(t.inorder() == std::vector<int>{20, 30, 40, 50, 60, 70, 80}, "inorder");
require(t.kth(0) == 20 && t.kth(3) == 50 && t.kth(6) == 80, "kth");
require(t.rank(55) == 4 && t.rank(20) == 0 && t.rank(100) == 7, "rank");
require(t.contains(40) && !t.contains(45), "contains");
require(t.erase(30) && !t.erase(35), "erase");
require(t.inorder() == std::vector<int>{20, 40, 50, 60, 70, 80}, "inorder after erase");
t.check();
Treap big;
for (int k = 1; k <= 1000; k++) big.insert(k);
big.check();
require(big.height() == 21, "height");
for (int k = 2; k <= 1000; k += 2) require(big.erase(k), "erase even");
big.check();
require(big.size() == 500 && big.kth(0) == 1 && big.kth(499) == 999, "after erase");
require(big.rank(500) == 250, "rank 500");
std::puts("treap OK");
}
type TNode = { key: number; prio: number; size: number; left: TNode | null; right: TNode | null };
function require(ok: boolean, msg: string): void {
if (!ok) throw new Error("check failed: " + msg);
}
const sz = (t: TNode | null): number => (t ? t.size : 0);
const pull = (t: TNode): void => {
t.size = 1 + sz(t.left) + sz(t.right);
};
// [keys < key, keys >= key]
function split(t: TNode | null, key: number): [TNode | null, TNode | null] {
if (!t) return [null, null];
if (t.key < key) {
const [a, b] = split(t.right, key);
t.right = a;
pull(t);
return [t, b];
}
const [a, b] = split(t.left, key);
t.left = b;
pull(t);
return [a, t];
}
function merge(a: TNode | null, b: TNode | null): TNode | null {
if (!a) return b;
if (!b) return a;
if (a.prio > b.prio) {
a.right = merge(a.right, b);
pull(a);
return a;
}
b.left = merge(a, b.left);
pull(b);
return b;
}
class Treap {
root: TNode | null = null;
private state = 2463534242; // xorshift32 seed shared with the other languages
private nextPrio(): number {
let x = this.state;
x = (x ^ (x << 13)) >>> 0;
x = (x ^ (x >>> 17)) >>> 0;
x = (x ^ (x << 5)) >>> 0;
this.state = x;
return x;
}
get size(): number {
return sz(this.root);
}
contains(key: number): boolean {
let t = this.root;
while (t) {
if (key === t.key) return true;
t = key < t.key ? t.left : t.right;
}
return false;
}
insert(key: number): boolean {
if (this.contains(key)) return false;
const node: TNode = { key, prio: this.nextPrio(), size: 1, left: null, right: null };
const [a, b] = split(this.root, key);
this.root = merge(merge(a, node), b);
return true;
}
erase(key: number): boolean {
const [a, b] = split(this.root, key);
const [mid, c] = split(b, key + 1);
this.root = merge(a, c);
return mid !== null;
}
kth(k: number): number {
if (k < 0 || k >= this.size) throw new RangeError("kth");
let t = this.root!;
for (;;) {
const ls = sz(t.left);
if (k < ls) t = t.left!;
else if (k === ls) return t.key;
else {
k -= ls + 1;
t = t.right!;
}
}
}
rank(key: number): number {
let r = 0;
let t = this.root;
while (t) {
if (t.key < key) {
r += sz(t.left) + 1;
t = t.right;
} else t = t.left;
}
return r;
}
inorder(): number[] {
const out: number[] = [];
const stack: TNode[] = [];
let t = this.root;
while (stack.length || t) {
while (t) {
stack.push(t);
t = t.left;
}
t = stack.pop()!;
out.push(t.key);
t = t.right;
}
return out;
}
height(t: TNode | null = this.root): number {
return t ? 1 + Math.max(this.height(t.left), this.height(t.right)) : 0;
}
check(t: TNode | null = this.root, lo = -Infinity, hi = Infinity): number {
if (!t) return 0;
require(t.key > lo && t.key < hi, "BST order broken");
require(!t.left || t.left.prio <= t.prio, "heap order broken");
require(!t.right || t.right.prio <= t.prio, "heap order broken");
const s = 1 + this.check(t.left, lo, t.key) + this.check(t.right, t.key, hi);
require(s === t.size, "size field wrong");
return s;
}
}
const same = (a: number[], b: number[]) => a.length === b.length && a.every((v, i) => v === b[i]);
const t = new Treap();
const added = [50, 30, 70, 20, 40, 60, 80, 30].map((k) => t.insert(k));
require(same(added.map(Number), [1, 1, 1, 1, 1, 1, 1, 0]), "insert result");
require(t.size === 7 && same(t.inorder(), [20, 30, 40, 50, 60, 70, 80]), "inorder");
require(t.kth(0) === 20 && t.kth(3) === 50 && t.kth(6) === 80, "kth");
require(t.rank(55) === 4 && t.rank(20) === 0 && t.rank(100) === 7, "rank");
require(t.contains(40) && !t.contains(45), "contains");
require(t.erase(30) && !t.erase(35), "erase");
require(same(t.inorder(), [20, 40, 50, 60, 70, 80]), "inorder after erase");
t.check();
const big = new Treap();
for (let k = 1; k <= 1000; k++) big.insert(k);
big.check();
require(big.height() === 21, "height " + big.height());
for (let k = 2; k <= 1000; k += 2) require(big.erase(k), "erase even");
big.check();
require(big.size === 500 && big.kth(0) === 1 && big.kth(499) === 999, "after erase");
require(big.rank(500) === 250, "rank 500");
console.log("treap OK");
Note that erase never searches: two splits isolate the key, and "absent" needs no special case. Java widens the priority to a non-negative long so all four languages build the same tree. Recursion depth is the height, expected, so recursion is safe here.
Skip list (canonical)
A sorted set of integers with and at most 16 levels (enough for about keys), the parameters Redis and LevelDB use in spirit. The checker verifies that every level is strictly sorted and is a subset of the level below. The same xorshift seed makes all four versions draw the same heights; the test asserts that exactly 7 levels are in use after the run.
from __future__ import annotations
MAX_LEVEL = 16
class XorShift32:
def __init__(self, seed: int = 2463534242) -> None:
self.state = seed
def next(self) -> int:
x = self.state
x ^= (x << 13) & 0xFFFFFFFF
x ^= x >> 17
x ^= (x << 5) & 0xFFFFFFFF
self.state = x
return x
class SkipNode:
__slots__ = ("key", "next")
def __init__(self, key: int, level: int) -> None:
self.key = key
self.next: list[SkipNode | None] = [None] * level
class SkipList:
"""Sorted set of ints. Each node is promoted one more level with probability 1/4."""
def __init__(self, seed: int = 2463534242) -> None:
self.head = SkipNode(-1, MAX_LEVEL) # sentinel; its key is never compared
self.level = 1 # number of levels currently in use
self.size = 0
self.rng = XorShift32(seed)
def _random_level(self) -> int:
lvl = 1
while lvl < MAX_LEVEL and (self.rng.next() & 3) == 0: # probability 1/4
lvl += 1
return lvl
def _find_preds(self, key: int) -> list[SkipNode]:
"""preds[i] = last node on level i whose key is < key."""
preds = [self.head] * MAX_LEVEL
x = self.head
for i in range(self.level - 1, -1, -1):
while (nxt := x.next[i]) is not None and nxt.key < key:
x = nxt
preds[i] = x
return preds
def contains(self, key: int) -> bool:
x = self._find_preds(key)[0].next[0]
return x is not None and x.key == key
def insert(self, key: int) -> bool:
preds = self._find_preds(key)
nxt = preds[0].next[0]
if nxt is not None and nxt.key == key:
return False
lvl = self._random_level()
self.level = max(self.level, lvl) # preds above the old level are already head
node = SkipNode(key, lvl)
for i in range(lvl):
node.next[i] = preds[i].next[i]
preds[i].next[i] = node
self.size += 1
return True
def erase(self, key: int) -> bool:
preds = self._find_preds(key)
x = preds[0].next[0]
if x is None or x.key != key:
return False
for i in range(len(x.next)):
preds[i].next[i] = x.next[i]
while self.level > 1 and self.head.next[self.level - 1] is None:
self.level -= 1
self.size -= 1
return True
def to_list(self) -> list[int]:
out, x = [], self.head.next[0]
while x is not None:
out.append(x.key)
x = x.next[0]
return out
def check(self) -> None:
"""Every level is sorted and is a sub-list of the level below."""
below = None
for i in range(MAX_LEVEL):
keys, x = [], self.head.next[i]
while x is not None:
keys.append(x.key)
x = x.next[i]
assert keys == sorted(set(keys)), "level not strictly sorted"
assert below is None or set(keys) <= below, "level not a subset of the one below"
assert i < self.level or not keys, "level above self.level in use"
below = set(keys)
if __name__ == "__main__":
s = SkipList()
added = [s.insert(k) for k in [50, 30, 70, 20, 40, 60, 80, 30]]
assert added == [True] * 7 + [False]
assert s.to_list() == [20, 30, 40, 50, 60, 70, 80] and s.size == 7
assert s.contains(40) and not s.contains(45)
assert s.erase(30) and not s.erase(35)
assert s.to_list() == [20, 40, 50, 60, 70, 80]
s.check()
big = SkipList()
for i in range(1000):
assert big.insert(i * 7919 % 1000) # every key 0..999 once, in scrambled order
assert big.to_list() == list(range(1000))
big.check()
for k in range(0, 1000, 3):
assert big.erase(k)
assert big.size == 666 and big.to_list()[:4] == [1, 2, 4, 5]
assert not big.contains(999) and big.contains(998)
big.check()
assert big.level == 7, big.level
print("skip list OK")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeSet;
public class SkipList {
static final int MAX_LEVEL = 16;
private static final class Node {
final int key;
final Node[] next;
Node(int key, int level) { this.key = key; this.next = new Node[level]; }
}
private final Node head = new Node(Integer.MIN_VALUE, MAX_LEVEL); // sentinel
private int level = 1;
private int size = 0;
private int state = (int) 2463534242L;
private int nextRand() {
int x = state;
x ^= x << 13;
x ^= x >>> 17;
x ^= x << 5;
return state = x;
}
private int randomLevel() {
int lvl = 1;
while (lvl < MAX_LEVEL && (nextRand() & 3) == 0) lvl++; // probability 1/4
return lvl;
}
private Node[] findPreds(int key) {
Node[] preds = new Node[MAX_LEVEL];
Arrays.fill(preds, head);
Node x = head;
for (int i = level - 1; i >= 0; i--) {
while (x.next[i] != null && x.next[i].key < key) x = x.next[i];
preds[i] = x;
}
return preds;
}
public int size() { return size; }
public int levels() { return level; }
public boolean contains(int key) {
Node x = findPreds(key)[0].next[0];
return x != null && x.key == key;
}
public boolean insert(int key) {
Node[] preds = findPreds(key);
Node nxt = preds[0].next[0];
if (nxt != null && nxt.key == key) return false;
int lvl = randomLevel();
level = Math.max(level, lvl);
Node node = new Node(key, lvl);
for (int i = 0; i < lvl; i++) {
node.next[i] = preds[i].next[i];
preds[i].next[i] = node;
}
size++;
return true;
}
public boolean erase(int key) {
Node[] preds = findPreds(key);
Node x = preds[0].next[0];
if (x == null || x.key != key) return false;
for (int i = 0; i < x.next.length; i++) preds[i].next[i] = x.next[i];
while (level > 1 && head.next[level - 1] == null) level--;
size--;
return true;
}
public List<Integer> toList() {
List<Integer> out = new ArrayList<>();
for (Node x = head.next[0]; x != null; x = x.next[0]) out.add(x.key);
return out;
}
public void check() {
TreeSet<Integer> below = null;
for (int i = 0; i < MAX_LEVEL; i++) {
TreeSet<Integer> keys = new TreeSet<>();
int prev = Integer.MIN_VALUE;
boolean first = true;
for (Node x = head.next[i]; x != null; x = x.next[i]) {
require(first || x.key > prev, "level not strictly sorted");
prev = x.key;
first = false;
keys.add(x.key);
}
require(below == null || below.containsAll(keys), "level not a subset of the one below");
require(i < level || keys.isEmpty(), "level above level-in-use");
below = keys;
}
}
static void require(boolean ok, String msg) {
if (!ok) throw new AssertionError(msg);
}
public static void main(String[] args) {
SkipList s = new SkipList();
int[] keys = {50, 30, 70, 20, 40, 60, 80, 30};
for (int i = 0; i < keys.length; i++) require(s.insert(keys[i]) == (i < 7), "insert result");
require(s.toList().equals(List.of(20, 30, 40, 50, 60, 70, 80)) && s.size() == 7, "toList");
require(s.contains(40) && !s.contains(45), "contains");
require(s.erase(30) && !s.erase(35), "erase");
require(s.toList().equals(List.of(20, 40, 50, 60, 70, 80)), "after erase");
s.check();
SkipList big = new SkipList();
for (int i = 0; i < 1000; i++) require(big.insert(i * 7919 % 1000), "insert big");
List<Integer> all = big.toList();
for (int i = 0; i < 1000; i++) require(all.get(i) == i, "sorted");
big.check();
for (int k = 0; k < 1000; k += 3) require(big.erase(k), "erase big");
require(big.size() == 666 && big.toList().subList(0, 4).equals(List.of(1, 2, 4, 5)), "after erase big");
require(!big.contains(999) && big.contains(998), "contains big");
big.check();
require(big.levels() == 7, "levels " + big.levels());
System.out.println("skip list OK");
}
}
#include <algorithm>
#include <array>
#include <climits>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <memory>
#include <set>
#include <vector>
static void require(bool ok, const char* msg) {
if (!ok) { std::fprintf(stderr, "check failed: %s\n", msg); std::exit(1); }
}
class SkipList {
static constexpr int MAX_LEVEL = 16;
struct Node {
int key;
std::vector<Node*> next;
Node(int k, int level) : key(k), next(level, nullptr) {}
};
std::unique_ptr<Node> head = std::make_unique<Node>(INT_MIN, MAX_LEVEL); // sentinel
int level = 1;
int count = 0;
std::uint32_t state = 2463534242u;
std::uint32_t nextRand() {
std::uint32_t x = state;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
return state = x;
}
int randomLevel() {
int lvl = 1;
while (lvl < MAX_LEVEL && (nextRand() & 3u) == 0) lvl++; // probability 1/4
return lvl;
}
std::array<Node*, MAX_LEVEL> findPreds(int key) const {
std::array<Node*, MAX_LEVEL> preds;
preds.fill(head.get());
Node* x = head.get();
for (int i = level - 1; i >= 0; i--) {
while (x->next[i] && x->next[i]->key < key) x = x->next[i];
preds[i] = x;
}
return preds;
}
public:
SkipList() = default;
SkipList(const SkipList&) = delete;
SkipList& operator=(const SkipList&) = delete;
~SkipList() {
Node* x = head->next[0];
while (x) { Node* n = x->next[0]; delete x; x = n; }
}
int size() const { return count; }
int levels() const { return level; }
bool contains(int key) const {
Node* x = findPreds(key)[0]->next[0];
return x && x->key == key;
}
bool insert(int key) {
auto preds = findPreds(key);
Node* nxt = preds[0]->next[0];
if (nxt && nxt->key == key) return false;
int lvl = randomLevel();
level = std::max(level, lvl);
Node* node = new Node(key, lvl);
for (int i = 0; i < lvl; i++) {
node->next[i] = preds[i]->next[i];
preds[i]->next[i] = node;
}
count++;
return true;
}
bool erase(int key) {
auto preds = findPreds(key);
Node* x = preds[0]->next[0];
if (!x || x->key != key) return false;
for (int i = 0; i < static_cast<int>(x->next.size()); i++) preds[i]->next[i] = x->next[i];
delete x;
while (level > 1 && !head->next[level - 1]) level--;
count--;
return true;
}
std::vector<int> toList() const {
std::vector<int> out;
for (Node* x = head->next[0]; x; x = x->next[0]) out.push_back(x->key);
return out;
}
void check() const {
std::set<int> below;
for (int i = 0; i < MAX_LEVEL; i++) {
std::set<int> keys;
Node* prev = nullptr;
for (Node* x = head->next[i]; x; x = x->next[i]) {
require(!prev || x->key > prev->key, "level not strictly sorted");
prev = x;
keys.insert(x->key);
}
if (i > 0) require(std::includes(below.begin(), below.end(), keys.begin(), keys.end()), "level not a subset");
require(i < level || keys.empty(), "level above level-in-use");
below = keys;
}
}
};
int main() {
SkipList s;
int keys[] = {50, 30, 70, 20, 40, 60, 80, 30};
for (int i = 0; i < 8; i++) require(s.insert(keys[i]) == (i < 7), "insert result");
require(s.toList() == std::vector<int>{20, 30, 40, 50, 60, 70, 80} && s.size() == 7, "toList");
require(s.contains(40) && !s.contains(45), "contains");
require(s.erase(30) && !s.erase(35), "erase");
require(s.toList() == std::vector<int>{20, 40, 50, 60, 70, 80}, "after erase");
s.check();
SkipList big;
for (int i = 0; i < 1000; i++) require(big.insert(i * 7919 % 1000), "insert big");
auto all = big.toList();
for (int i = 0; i < 1000; i++) require(all[i] == i, "sorted");
big.check();
for (int k = 0; k < 1000; k += 3) require(big.erase(k), "erase big");
auto rest = big.toList();
require(big.size() == 666 && rest[0] == 1 && rest[1] == 2 && rest[2] == 4 && rest[3] == 5, "after erase big");
require(!big.contains(999) && big.contains(998), "contains big");
big.check();
require(big.levels() == 7, "levels");
std::puts("skip list OK");
}
const MAX_LEVEL = 16;
type SNode = { key: number; next: (SNode | null)[] };
function require(ok: boolean, msg: string): void {
if (!ok) throw new Error("check failed: " + msg);
}
class SkipList {
private head: SNode = { key: -Infinity, next: new Array(MAX_LEVEL).fill(null) };
level = 1;
size = 0;
private state = 2463534242;
private nextRand(): number {
let x = this.state;
x = (x ^ (x << 13)) >>> 0;
x = (x ^ (x >>> 17)) >>> 0;
x = (x ^ (x << 5)) >>> 0;
this.state = x;
return x;
}
private randomLevel(): number {
let lvl = 1;
while (lvl < MAX_LEVEL && (this.nextRand() & 3) === 0) lvl++; // probability 1/4
return lvl;
}
private findPreds(key: number): SNode[] {
const preds: SNode[] = new Array(MAX_LEVEL).fill(this.head);
let x = this.head;
for (let i = this.level - 1; i >= 0; i--) {
let nxt = x.next[i];
while (nxt !== null && nxt.key < key) {
x = nxt;
nxt = x.next[i];
}
preds[i] = x;
}
return preds;
}
contains(key: number): boolean {
const x = this.findPreds(key)[0].next[0];
return x !== null && x.key === key;
}
insert(key: number): boolean {
const preds = this.findPreds(key);
const nxt = preds[0].next[0];
if (nxt !== null && nxt.key === key) return false;
const lvl = this.randomLevel();
this.level = Math.max(this.level, lvl);
const node: SNode = { key, next: new Array(lvl).fill(null) };
for (let i = 0; i < lvl; i++) {
node.next[i] = preds[i].next[i];
preds[i].next[i] = node;
}
this.size++;
return true;
}
erase(key: number): boolean {
const preds = this.findPreds(key);
const x = preds[0].next[0];
if (x === null || x.key !== key) return false;
for (let i = 0; i < x.next.length; i++) preds[i].next[i] = x.next[i];
while (this.level > 1 && this.head.next[this.level - 1] === null) this.level--;
this.size--;
return true;
}
toList(): number[] {
const out: number[] = [];
for (let x = this.head.next[0]; x !== null; x = x.next[0]) out.push(x.key);
return out;
}
check(): void {
let below: Set<number> | null = null;
for (let i = 0; i < MAX_LEVEL; i++) {
const keys: number[] = [];
for (let x = this.head.next[i]; x !== null; x = x.next[i]) keys.push(x.key);
for (let j = 1; j < keys.length; j++) require(keys[j - 1] < keys[j], "level not strictly sorted");
if (below !== null) {
const b: Set<number> = below;
require(keys.every((k) => b.has(k)), "level not a subset of the one below");
}
require(i < this.level || keys.length === 0, "level above level-in-use");
below = new Set(keys);
}
}
}
const same = (a: number[], b: number[]) => a.length === b.length && a.every((v, i) => v === b[i]);
const s = new SkipList();
const added = [50, 30, 70, 20, 40, 60, 80, 30].map((k) => s.insert(k));
require(same(added.map(Number), [1, 1, 1, 1, 1, 1, 1, 0]), "insert result");
require(same(s.toList(), [20, 30, 40, 50, 60, 70, 80]) && s.size === 7, "toList");
require(s.contains(40) && !s.contains(45), "contains");
require(s.erase(30) && !s.erase(35), "erase");
require(same(s.toList(), [20, 40, 50, 60, 70, 80]), "after erase");
s.check();
const big = new SkipList();
for (let i = 0; i < 1000; i++) require(big.insert((i * 7919) % 1000), "insert big");
require(same(big.toList(), Array.from({ length: 1000 }, (_, i) => i)), "sorted");
big.check();
for (let k = 0; k < 1000; k += 3) require(big.erase(k), "erase big");
require(big.size === 666 && same(big.toList().slice(0, 4), [1, 2, 4, 5]), "after erase big");
require(!big.contains(999) && big.contains(998), "contains big");
big.check();
require(big.level === 7, "levels " + big.level);
console.log("skip list OK");
level tracks the levels in use so searches do not start 16 levels up; a node taller than level gets the head as predecessor on the new levels, which findPreds pre-fills.
Variant: implicit treap with range reversal
The sequence version. Positions replace keys, a rev flag reverses a subtree lazily, and total is an example aggregate (range sum) maintained by pull. The randomized test cross-checks 2,000 random reversals, sums and block moves against a plain Python list.
from __future__ import annotations
import random
class INode:
__slots__ = ("val", "prio", "size", "total", "rev", "left", "right")
def __init__(self, val: int, prio: float) -> None:
self.val = val
self.prio = prio
self.size = 1
self.total = val # sum of the subtree, an example aggregate
self.rev = False # lazy flag: "this subtree's children must be swapped"
self.left: INode | None = None
self.right: INode | None = None
def size(t: INode | None) -> int:
return t.size if t else 0
def total(t: INode | None) -> int:
return t.total if t else 0
def push(t: INode | None) -> None:
"""Apply a pending reversal one level down before looking inside t."""
if t is not None and t.rev:
t.left, t.right = t.right, t.left
for c in (t.left, t.right):
if c is not None:
c.rev = not c.rev
t.rev = False
def pull(t: INode) -> None:
t.size = 1 + size(t.left) + size(t.right)
t.total = t.val + total(t.left) + total(t.right)
def split(t: INode | None, k: int) -> tuple[INode | None, INode | None]:
"""First k elements go left, the rest go right. No keys: position is the key."""
if t is None:
return None, None
push(t)
if size(t.left) < k:
a, b = split(t.right, k - size(t.left) - 1)
t.right = a
pull(t)
return t, b
a, b = split(t.left, k)
t.left = b
pull(t)
return a, t
def merge(a: INode | None, b: INode | None) -> INode | None:
if a is None or b is None:
return a or b
if a.prio > b.prio:
push(a)
a.right = merge(a.right, b)
pull(a)
return a
push(b)
b.left = merge(a, b.left)
pull(b)
return b
class Rope:
def __init__(self, values: list[int], seed: int = 1) -> None:
rng = random.Random(seed)
self.root: INode | None = None
for v in values:
self.root = merge(self.root, INode(v, rng.random()))
def reverse(self, l: int, r: int) -> None:
"""Reverse positions l..r inclusive (0-indexed) in O(log n) expected."""
a, b = split(self.root, l)
mid, c = split(b, r - l + 1)
if mid is not None:
mid.rev = not mid.rev
self.root = merge(merge(a, mid), c)
def range_sum(self, l: int, r: int) -> int:
a, b = split(self.root, l)
mid, c = split(b, r - l + 1)
s = total(mid)
self.root = merge(merge(a, mid), c)
return s
def move_to_front(self, l: int, r: int) -> None:
a, b = split(self.root, l)
mid, c = split(b, r - l + 1)
self.root = merge(merge(mid, a), c)
def to_list(self) -> list[int]:
out: list[int] = []
def go(t: INode | None) -> None:
if t is None:
return
push(t)
go(t.left)
out.append(t.val)
go(t.right)
go(self.root)
return out
if __name__ == "__main__":
r = Rope([1, 2, 3, 4, 5, 6, 7, 8])
r.reverse(2, 5)
assert r.to_list() == [1, 2, 6, 5, 4, 3, 7, 8]
assert r.range_sum(1, 3) == 2 + 6 + 5
r.move_to_front(5, 7)
assert r.to_list() == [3, 7, 8, 1, 2, 6, 5, 4]
r.reverse(0, 7)
assert r.to_list() == [4, 5, 6, 2, 1, 8, 7, 3]
rng = random.Random(42) # randomized cross-check against a Python list
ref = list(range(300))
rope = Rope(ref)
for _ in range(2000):
l = rng.randrange(300)
rr = rng.randrange(l, 300)
op = rng.randrange(3)
if op == 0:
rope.reverse(l, rr)
ref[l:rr + 1] = ref[l:rr + 1][::-1]
elif op == 1:
assert rope.range_sum(l, rr) == sum(ref[l:rr + 1])
else:
rope.move_to_front(l, rr)
ref = ref[l:rr + 1] + ref[:l] + ref[rr + 1:]
assert rope.to_list() == ref
print("implicit treap OK")
The rule: push before reading a node's children (in split, merge and traversals), pull after changing them. Aggregates not symmetric under reversal (maximum prefix sum) need forward and backward versions swapped by push.
Variant: bottom-up splay tree
With parent pointers. contains splays the last node on the path even on a miss; otherwise failed searches could walk the same long path forever without paying it down. The last block measures the sequential access theorem.
from __future__ import annotations
import random
class SNode:
__slots__ = ("key", "left", "right", "parent")
def __init__(self, key: int) -> None:
self.key = key
self.left: SNode | None = None
self.right: SNode | None = None
self.parent: SNode | None = None
class SplayTree:
"""Bottom-up splay tree (set of ints). Every operation splays the last node it touched."""
def __init__(self) -> None:
self.root: SNode | None = None
self.rotations = 0
def _rotate(self, x: SNode) -> None:
p = x.parent
assert p is not None
g = p.parent
if p.left is x:
p.left = x.right
if x.right:
x.right.parent = p
x.right = p
else:
p.right = x.left
if x.left:
x.left.parent = p
x.left = p
p.parent = x
x.parent = g
if g is None:
self.root = x
elif g.left is p:
g.left = x
else:
g.right = x
self.rotations += 1
def _splay(self, x: SNode) -> None:
while x.parent is not None:
p = x.parent
g = p.parent
if g is None:
self._rotate(x) # zig
elif (g.left is p) == (p.left is x):
self._rotate(p) # zig-zig: rotate the parent first
self._rotate(x)
else:
self._rotate(x) # zig-zag: rotate x twice
self._rotate(x)
def _find_last(self, key: int) -> SNode | None:
"""The node with key, or the last node on the search path."""
t, last = self.root, None
while t is not None:
last = t
if key == t.key:
break
t = t.left if key < t.key else t.right
return last
def contains(self, key: int) -> bool:
x = self._find_last(key)
if x is None:
return False
self._splay(x) # splay even on a miss
return x.key == key
def insert(self, key: int) -> bool:
x = self._find_last(key)
if x is not None and x.key == key:
self._splay(x)
return False
n = SNode(key)
n.parent = x
if x is None:
self.root = n
elif key < x.key:
x.left = n
else:
x.right = n
self._splay(n)
return True
def erase(self, key: int) -> bool:
if not self.contains(key): # brings key (or a neighbour) to the root
return False
root = self.root
assert root is not None
left, right = root.left, root.right
if left:
left.parent = None
if right:
right.parent = None
if left is None:
self.root = right
return True
m = left # splay the max of the left tree to its root
while m.right:
m = m.right
self.root = left
self._splay(m)
m.right = right # m has no right child now
if right:
right.parent = m
return True
def inorder(self) -> list[int]:
out: list[int] = []
stack: list[SNode] = []
t = self.root
while stack or t:
while t:
stack.append(t)
t = t.left
t = stack.pop()
out.append(t.key)
t = t.right
return out
if __name__ == "__main__":
s = SplayTree()
for k in [50, 30, 70, 20, 40, 60, 80]:
assert s.insert(k)
assert not s.insert(30)
assert s.root is not None and s.root.key == 30 # the last access is at the root
assert s.contains(60) and s.root.key == 60
assert not s.contains(45)
assert s.erase(30) and not s.erase(35)
assert s.inorder() == [20, 40, 50, 60, 70, 80]
rng = random.Random(3) # cross-check against a Python set
ref: set[int] = set()
t = SplayTree()
for _ in range(5000):
k = rng.randrange(500)
op = rng.randrange(3)
if op == 0:
assert t.insert(k) == (k not in ref)
ref.add(k)
elif op == 1:
assert t.erase(k) == (k in ref)
ref.discard(k)
else:
assert t.contains(k) == (k in ref)
assert t.inorder() == sorted(ref)
seq = SplayTree() # sequential access: O(n) total
n = 10_000
for k in range(n):
seq.insert(k)
seq.rotations = 0
for k in range(n):
assert seq.contains(k)
assert seq.rotations < 4.5 * n, seq.rotations
print("splay OK, rotations for sequential scan of", n, "keys:", seq.rotations)
Inserting 0 to 9,999 in order builds a left path, the worst starting shape; the scan still takes only 44,112 rotations.
Real-world uses
- Redis sorted sets. A sorted set (
ZADD,ZRANGE,ZRANK,ZRANGEBYSCORE) that grows beyond a small threshold is stored as a skip list plus a hash table: the hash maps member → score forZSCORE, and the skip list orders (score, member) pairs for range queries. Small sets use a compact listpack (ziplist before Redis 7.0), up tozset-max-listpack-entries(128) andzset-max-listpack-value(64 bytes). Redis's skip list (int_zset.c) uses promotion probability and a level cap of 32 in current releases, stores a span (number of level-1 nodes skipped) with each forward pointer soZRANKis , and keeps a backward pointer on level 1 for reverse iteration. Antirez cited memory, easy range operations and simplicity. See Redis Internals. - LevelDB and RocksDB memtables. LSM-tree engines buffer writes in a sorted in-memory memtable, later flushed as a sorted file. LevelDB's memtable is a skip list (
db/skiplist.h) with branching factor 4 (so ) and a maximum height of 12; readers run lock-free alongside one externally serialized writer, and nodes are never deleted (the memtable is discarded whole). RocksDB's default memtable is also a skip list, and itsInlineSkipListadditionally supports concurrent inserts from several writers. See Storage Engines. - Java
ConcurrentSkipListMap(Java 6, Doug Lea): the JDK's concurrent sorted map, lock-free via compare-and-swap on forward pointers, expected operations, weakly consistent iterators, and asize()that traverses the map. HBase's in-memory store has been built on it. There is no concurrent red-black tree in the JDK: rebalancing touches too many nodes for practical lock-free updates. See Lock-Free Programming. - Splay trees in systems code. GCC's
libibertyshipssplay-tree.h; FreeBSD's virtual memory system has used a splay tree to find the map entry for an address, exploiting fault locality. Link-cut trees are built from splay trees, and__gnu_pbds::treeoffers asplay_tree_tag. - Treaps are rarer in production than in contests, but the split/join style they popularized underlies parallel ordered sets: Blelloch and Reid-Miller (1998) gave parallel set operations on treaps, later generalized to AVL and red-black trees.
- Order statistics in C++.
__gnu_pbds::tree<..., rb_tree_tag, tree_order_statistics_node_update>givesfind_by_orderandorder_of_key, the usual contest shortcut on GCC.
Background: Probability for Engineers, Indexing Deep Dive.
Pitfalls & edge cases
- Predictable randomness. If the adversary knows your generator and seed, they can choose an insertion order that builds a path. Seed from real entropy in production, deterministically only in tests.
- Duplicate priorities. Ties do not break correctness but skew the distribution. With 32-bit priorities a million keys give about 116 tied pairs on average (), harmless; 16-bit priorities would not be.
- Duplicate keys. The canonical treap is a set. For a multiset, store a count per node, or let equal keys go right and insert freely (the "count of smaller numbers" solution does this);
erasemust then remove one copy, by splitting out the== xpart and merging its root's children. erase(x)withsplit(b, x + 1)overflows whenxis the maximum integer. Use a split variant that puts== xon the left (split_le) instead ofx + 1, or use 64-bit keys.- Forgetting
pullorpush. Missing one shows up as wrong k-th answers only after a specific operation sequence; an invariant checker likecheck()finds it in seconds. - Off-by-one in implicit split. To isolate 0-indexed
l..r, split atl, then the right part atr - l + 1; for 1-indexeda..b, ata - 1thenb - a + 1. - Not splaying on every path, including failed searches and the "already present" branch of insert. It passes small tests and loses the amortized bound.
- Recursion depth. Treap recursion is deep. Splay trees can be deep at times, so write splay and traversals iteratively.
- Skip list level cap too low. levels at suit about keys; LevelDB's 12 fits a memtable, a general library should use 32. Too low a cap degrades toward linear scans on the top level.
- Splay trees and concurrency. Reads restructure the tree, so lookups behind a read-write lock must take the write lock.
Variations
- Rotation-based treap. Insert as a leaf and rotate up while the priority beats the parent's; delete by rotating down to a leaf. Same trees, no temporary pairs.
- Randomized BSTs (Martínez & Roura, 1998). No stored priorities: insert at the root of a size- subtree with probability ; the result is again a random BST.
- Zip trees (Tarjan, Levy & Timmel, 2019). Treaps with geometric "rank" priorities (like skip-list levels), updated by unzipping and zipping paths; they make the treap/skip-list correspondence exact.
- Persistent treaps. Copy nodes on the few paths split and merge touch: a fully persistent set or sequence with extra space per operation.
- Top-down splaying needs no parent pointers; semi-splaying rotates less with the same amortized bound.
- Tango trees (Demaine, Harmon, Iacono & Pătraşcu, 2004) are -competitive with the optimal dynamic BST, the best proven ratio.
- Link-cut trees (Sleator & Tarjan, 1983) store a forest's preferred paths in splay trees:
link,cut, path aggregates in amortized. - Deterministic skip lists (Munro, Papadakis & Sedgewick, 1992) keep gaps of 1 to 3 nodes per level, isomorphic to 2-3-4 trees, worst-case .
- Indexable skip lists store spans (Redis) for rank and k-th.
- Concurrent skip lists: Fraser's lock-free design (2004) and the optimistic skiplist of Herlihy, Lev, Luchangco & Shavit (2007).
- Cartesian trees as a static tool. Keys = indices, priorities = values, built in with a stack; range minimum becomes lowest common ancestor (see Sparse Tables, Sqrt Decomposition & Mo's Algorithm and LCA, Binary Lifting & Euler Tour).
Comparison
| Property | Treap | Splay tree | Skip list | AVL | Red-black |
|---|---|---|---|---|---|
| Guarantee | expected | amortized | expected | worst case, height ≤ 1.44 log₂ n | worst case, height ≤ 2 log₂(n+1) |
| Typical depth/cost | ≈ 1.39 log₂ n | adapts to access pattern | ≈ 2 log₂ n comparisons | ≈ log₂ n | ≈ log₂ n |
| Per-node overhead | priority | none (parent if bottom-up) | 1/(1−p) pointers | height or balance | colour bit |
| Rotations per update | < 2 expected | O(log n) amortized | none | ≤ 2 insert, O(log n) delete | ≤ 2 insert, ≤ 3 delete |
| Split / merge | natural, O(log n) | natural, O(log n) | cut each level, O(log n) | possible (join-based) | possible (join-based) |
| Reads modify structure | no | yes | no | no | no |
| Concurrency | hard | very hard | good (lock-free designs exist) | hard | hard |
| Lines of code (set) | ≈ 40 | ≈ 80 | ≈ 60 | ≈ 120 | ≈ 200 |
| Best at | sequence ops, contests, set algebra | skewed / local access, link-cut trees | concurrent maps, memtables, Redis zsets | read-heavy ordered maps | general-purpose libraries |
Practice ladder
Problems in my own words; Python solutions run with this page's checks.
1. Design Skiplist (LeetCode 1206) — Hard. Implement search, add and erase on a skip list that allows duplicate values. Teaches the predecessor array and why duplicates need care in erase.
Hint
Collect the predecessor on every level (last node with value < target). The first node after preds[0] on level 0 is the first copy of the target. When erasing, unlink that exact node from each level where it is the successor of preds[i].
Solution
import random
class Skiplist:
MAX = 16
class Node:
__slots__ = ("val", "next")
def __init__(self, val: int, lvl: int) -> None:
self.val = val
self.next = [None] * lvl
def __init__(self) -> None:
self.head = self.Node(-1, self.MAX)
self.rng = random.Random(0)
def _preds(self, target: int) -> list:
preds, x = [None] * self.MAX, self.head
for i in range(self.MAX - 1, -1, -1):
while x.next[i] and x.next[i].val < target:
x = x.next[i]
preds[i] = x
return preds
def search(self, target: int) -> bool:
x = self._preds(target)[0].next[0]
return x is not None and x.val == target
def add(self, num: int) -> None: # duplicates allowed: new copy goes first
preds = self._preds(num)
lvl = 1
while lvl < self.MAX and self.rng.random() < 0.5:
lvl += 1
node = self.Node(num, lvl)
for i in range(lvl):
node.next[i] = preds[i].next[i]
preds[i].next[i] = node
def erase(self, num: int) -> bool: # removes one copy
preds = self._preds(num)
x = preds[0].next[0]
if x is None or x.val != num:
return False
for i in range(len(x.next)):
if preds[i].next[i] is x:
preds[i].next[i] = x.next[i]
return True
sk = Skiplist()
for v in [5, 1, 5, 9]:
sk.add(v)
assert sk.search(5) and not sk.search(4)
assert sk.erase(5) and sk.search(5) # one copy of 5 remains
assert sk.erase(5) and not sk.search(5)
assert not sk.erase(5) and sk.search(9) and sk.search(1)
Expected per operation, expected space. The is x check is defensive: since x is the first copy on level 0, on every level it occupies it is also the first node at or after the target.
2. My Calendar I (LeetCode 729) — Medium. Accept a booking [start, end) only if it overlaps no earlier accepted booking. Teaches floor/ceiling queries on an ordered set.
Hint
Only two existing bookings can conflict: the one with the largest start at or before the new start, and the one with the smallest start at or after it.
Solution
import random
class Node:
__slots__ = ("start", "end", "prio", "left", "right")
def __init__(self, start: int, end: int, prio: float) -> None:
self.start, self.end, self.prio = start, end, prio
self.left = self.right = None
def split(t, key): # (starts < key, starts >= key)
if t is None:
return None, None
if t.start < key:
a, b = split(t.right, key)
t.right = a
return t, b
a, b = split(t.left, key)
t.left = b
return a, t
def merge(a, b):
if a is None or b is None:
return a or b
if a.prio > b.prio:
a.right = merge(a.right, b)
return a
b.left = merge(a, b.left)
return b
class MyCalendar:
def __init__(self) -> None:
self.root = None
self.rng = random.Random(1)
def _floor(self, x): # booking with the largest start <= x
t, best = self.root, None
while t:
if t.start <= x:
best, t = t, t.right
else:
t = t.left
return best
def _ceil(self, x): # booking with the smallest start >= x
t, best = self.root, None
while t:
if t.start >= x:
best, t = t, t.left
else:
t = t.right
return best
def book(self, start: int, end: int) -> bool:
before, after = self._floor(start), self._ceil(start)
if before is not None and before.end > start:
return False
if after is not None and after.start < end:
return False
a, b = split(self.root, start)
self.root = merge(merge(a, Node(start, end, self.rng.random())), b)
return True
cal = MyCalendar()
assert [cal.book(s, e) for s, e in [(10, 20), (15, 25), (20, 30), (5, 10), (5, 11), (30, 31)]] == \
[True, False, True, True, False, True]
expected per booking. Half-open intervals mean [10, 20) and [20, 30) touch but do not overlap, hence the strict comparisons.
3. Contains Duplicate III (LeetCode 220) — Hard. Decide whether two indices at most k apart hold values at most t apart. Teaches a sliding window over an ordered set with ceiling queries.
Hint
Keep the last k values in an ordered set. For each new value x, find the smallest stored value ≥ x − t; if it is ≤ x + t, answer yes. (A bucket-hashing solution is , but the ordered-set one is the general pattern.)
4. Count of Smaller Numbers After Self (LeetCode 315) — Hard. For each element, count later elements that are strictly smaller. Teaches rank queries in a multiset treap.
Hint
Scan from the right. Before inserting x, the number of stored values smaller than x is the answer for that position. Split at x gives exactly that set as the left part.
Solution
import random
class Node:
__slots__ = ("key", "prio", "size", "left", "right")
def __init__(self, key: int, prio: float) -> None:
self.key, self.prio, self.size = key, prio, 1
self.left = self.right = None
def sz(t):
return t.size if t else 0
def pull(t):
t.size = 1 + sz(t.left) + sz(t.right)
def split(t, key): # (keys < key, keys >= key)
if t is None:
return None, None
if t.key < key:
a, b = split(t.right, key)
t.right = a
pull(t)
return t, b
a, b = split(t.left, key)
t.left = b
pull(t)
return a, t
def merge(a, b):
if a is None or b is None:
return a or b
if a.prio > b.prio:
a.right = merge(a.right, b)
pull(a)
return a
b.left = merge(a, b.left)
pull(b)
return b
def count_smaller(nums: list[int]) -> list[int]:
rng = random.Random(7)
root, out = None, []
for x in reversed(nums):
a, b = split(root, x) # a holds every later value < x
out.append(sz(a))
root = merge(merge(a, Node(x, rng.random())), b) # duplicates are fine
return out[::-1]
assert count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller([-1, -1]) == [0, 0]
assert count_smaller([3, 3, 1, 2, 3, 0]) == [3, 3, 1, 1, 1, 0]
data = random.Random(5).choices(range(-50, 50), k=300)
assert count_smaller(data) == [sum(y < x for y in data[i + 1:]) for i, x in enumerate(data)]
expected, space, no coordinate compression needed.
5. Order statistic set (SPOJ ORDERSET) — Medium. Insert, delete, k-th smallest and "how many below x" on up to operations. Teaches the full size-augmented treap API, exactly the canonical implementation above.
Hint
Insert and delete must ignore duplicates and absent keys. Reply "invalid" when k exceeds the set size. Use kth and rank from the canonical code.
6. Sliding Window Median (LeetCode 480) — Hard. Report the median of every window of size k. Teaches k-th queries on a sliding multiset.
Hint
A multiset treap with sizes: insert the incoming value, erase one copy of the outgoing value, and read the k // 2-th (and (k − 1) // 2-th) elements. Two heaps with lazy deletion also work.
7. Finding MK Average (LeetCode 1825) — Hard. Over the last m stream elements, average what remains after dropping the k smallest and k largest. Teaches sum-augmented order statistics.
Hint
Augment each node with the subtree sum as well as the size. The sum of the j smallest elements is a descent like kth. The answer is (sum of the smallest m − k) minus (sum of the smallest k), divided by m − 2k.
8. List Removals (CSES 1749) — Easy/Medium. Repeatedly remove and print the element at a given position of a list. Teaches implicit split by position.
Hint
Implicit treap: split at p − 1, split the right part at 1, print the single node, merge the outer parts. A Fenwick tree with binary-lifting descent is the other standard solution.
9. Salary Queries (CSES 1144) — Medium. Point updates to employee salaries and queries for how many salaries lie in a range. Teaches rank differences, rank(b + 1) − rank(a), on a multiset.
Hint
Maintain a multiset of current salaries: an update erases one copy of the old value and inserts the new one. Offline coordinate compression plus a Fenwick tree is faster in practice.
10. Cut and Paste (CSES 2072) — Medium. A string undergoes operations that cut a substring and append it at the end; print the final string. Teaches implicit treap split/merge in its purest form.
Hint
Three pieces: before a, the block a..b, after b. Merge them back in the order before, after, block.
Solution
import random
class Node:
__slots__ = ("ch", "prio", "size", "left", "right")
def __init__(self, ch: str, prio: float) -> None:
self.ch, self.prio, self.size = ch, prio, 1
self.left = self.right = None
def sz(t):
return t.size if t else 0
def pull(t):
t.size = 1 + sz(t.left) + sz(t.right)
def split(t, k): # first k characters left, rest right
if t is None:
return None, None
if sz(t.left) < k:
a, b = split(t.right, k - sz(t.left) - 1)
t.right = a
pull(t)
return t, b
a, b = split(t.left, k)
t.left = b
pull(t)
return a, t
def merge(a, b):
if a is None or b is None:
return a or b
if a.prio > b.prio:
a.right = merge(a.right, b)
pull(a)
return a
b.left = merge(a, b.left)
pull(b)
return b
def cut_and_paste(s: str, ops: list[tuple[int, int]]) -> str:
rng = random.Random(11)
root = None
for ch in s:
root = merge(root, Node(ch, rng.random()))
for a, b in ops: # 1-indexed inclusive range moves to the end
left, rest = split(root, a - 1)
mid, right = split(rest, b - a + 1)
root = merge(merge(left, right), mid)
out, stack, t = [], [], root
while stack or t:
while t:
stack.append(t)
t = t.left
t = stack.pop()
out.append(t.ch)
t = t.right
return "".join(out)
assert cut_and_paste("AYBABTU", [(3, 5), (3, 5)]) == "AYABTUB"
rng = random.Random(2)
s = "".join(rng.choice("ABCD") for _ in range(200))
ops, ref = [], list(s)
for _ in range(300):
a = rng.randrange(1, 201)
b = rng.randrange(a, 201)
ops.append((a, b))
ref = ref[:a - 1] + ref[b:] + ref[a - 1:b]
assert cut_and_paste(s, ops) == "".join(ref)
expected. CPython is too slow for the full limits; a C++ port of the same code passes.
11. Substring Reversals (CSES 2073) — Medium/Hard. Reverse many substrings of a string and print the result. Teaches the lazy reverse flag.
Hint
Same three-piece split; flip rev on the middle piece. Remember to push before descending in split, in merge, and in the final traversal.
Solution
import random
class Node:
__slots__ = ("ch", "prio", "size", "rev", "left", "right")
def __init__(self, ch: str, prio: float) -> None:
self.ch, self.prio, self.size, self.rev = ch, prio, 1, False
self.left = self.right = None
def sz(t):
return t.size if t else 0
def push(t):
if t and t.rev:
t.left, t.right = t.right, t.left
if t.left:
t.left.rev ^= True
if t.right:
t.right.rev ^= True
t.rev = False
def pull(t):
t.size = 1 + sz(t.left) + sz(t.right)
def split(t, k):
if t is None:
return None, None
push(t)
if sz(t.left) < k:
a, b = split(t.right, k - sz(t.left) - 1)
t.right = a
pull(t)
return t, b
a, b = split(t.left, k)
t.left = b
pull(t)
return a, t
def merge(a, b):
if a is None or b is None:
return a or b
if a.prio > b.prio:
push(a)
a.right = merge(a.right, b)
pull(a)
return a
push(b)
b.left = merge(a, b.left)
pull(b)
return b
def substring_reversals(s: str, ops: list[tuple[int, int]]) -> str:
rng = random.Random(13)
root = None
for ch in s:
root = merge(root, Node(ch, rng.random()))
for a, b in ops: # reverse 1-indexed inclusive range
left, rest = split(root, a - 1)
mid, right = split(rest, b - a + 1)
mid.rev ^= True
root = merge(merge(left, mid), right)
out = []
def walk(t):
while t: # iterative on the right spine, recursive on the left
push(t)
walk(t.left)
out.append(t.ch)
t = t.right
walk(root)
return "".join(out)
assert substring_reversals("AYBABTU", [(3, 4), (4, 7)]) == "AYAUTBB"
rng = random.Random(4)
s = "".join(rng.choice("XYZ") for _ in range(150))
ops, ref = [], list(s)
for _ in range(400):
a = rng.randrange(1, 151)
b = rng.randrange(a, 151)
ops.append((a, b))
ref[a - 1:b] = ref[a - 1:b][::-1]
assert substring_reversals(s, ops) == "".join(ref)
expected. Note the order: the lazy flag on mid is set after the split, so nothing outside the range is affected.
12. Array and Simple Queries (HackerRank) — Medium. Move blocks of an array to the front or the back, then report the result and the difference between the first and last elements. Teaches combining several cut/paste operations.
Hint
Identical to Cut and Paste with two kinds of moves. Merge block, before, after for "to front" and before, after, block for "to back".
13. Reversals and Sums (CSES 2074) — Hard. Interleave range reversals with range-sum queries. Teaches maintaining an aggregate alongside a lazy tag.
Hint
Add a total field updated in pull. A sum is symmetric under reversal, so push does not need to change it. This is exactly the Rope variant above.
14. Count of Range Sum (LeetCode 327) — Hard. Count subarrays whose sum lies in [lower, upper]. Teaches prefix sums plus rank queries on a growing multiset.
Hint
For each prefix sum P[j], count earlier prefix sums in [P[j] − upper, P[j] − lower] as rank(P[j] − lower + 1) − rank(P[j] − upper) on a multiset treap, then insert P[j]. Merge-sort counting is the classical alternative; see Prefix Sums & Difference Arrays.
Common mistakes & interview follow-ups
Why does Redis use a skip list rather than a red-black tree for sorted sets? A range query is a search plus a level-1 walk, rank is a sum of spans, the code is short, and memory is tunable through . A size-augmented tree could do the same; the choice was about simplicity, not asymptotics.
What if the attacker knows your random seed? They can simulate it and insert keys in an order that builds a path: per operation. Use unpredictable priorities (OS entropy, or a keyed hash of the key). The same applies to skip-list levels.
Can a single splay operation be slow? Yes, . If you need per-operation latency bounds, a splay tree is the wrong choice.
Why do concurrent maps use skip lists? An insert modifies only the predecessors, and each link can be published with one compare-and-swap, bottom level first; readers see a valid list on every level. A tree insert can rotate nodes far from the key, which is hard to make atomic.
k-th element in a skip list? Store spans on forward pointers; follow a pointer only if the running total plus its span is at most k. Updates fix the predecessors' spans.
Treap or library tree in an interview? Use the library (TreeMap, std::set, sortedcontainers) unless you need what it lacks: k-th/rank in Java or Python, split/merge, sequence operations. Then write a treap, the shortest correct option.
What if the data does not fit in memory? Each step here is a random dereference, a seek on disk. Use a B-tree or LSM tree (see Balanced BSTs); skip lists appear in LSM engines only as the in-memory buffer.
Common mistakes. A min-heap in merge but a max-heap in the checker; splitting at x when the problem needs ≤ x; forgetting push in merge; not splaying on a failed search; levels from rand() % 2 of a weak generator; and calling treaps "O(log n) worst case" (they are expected, with high probability).
Quick quiz
- Keys 1 to 5 get priorities 3, 9, 1, 7, 5 (max-heap). What is the root, and what is the depth of key 3?
Answer
The root is the key with the highest priority, key 2 (priority 9). Inserting in priority order 2, 4, 5, 1, 3 gives: 2 at the root, 1 to its left, 4 to its right, then 5 right of 4, then 3 left of 4. Key 3 has ancestors 4 and 2, so depth 2. Check with the ancestor rule: 2 is an ancestor of 3 because priority 9 is the maximum over keys 2..3; 4 is an ancestor because priority 7 is the maximum over keys 3..4; 1 is not, because the maximum over 1..3 is key 2.
- In the zig-zig case, what goes wrong if you rotate
xtwice (as in zig-zag) instead of rotating the parent first?
Answer
The tree stays a valid BST, but on a long path single rotations leave the path essentially intact, so an adversary can access the deepest node at each time. Rotating the parent first folds the path, halving depths and producing the potential drop that pays for the rotations.
- Why are and equally fast for skip-list search in expectation, and why does Redis pick 1/4?
Answer
The expected search cost is about , and equals for both. Expected pointers per node are : 2 for , 1.33 for . So saves a third of the pointer memory at the same expected speed, at the cost of more variance.
- You delete a key from a treap with
split(t, x)thensplit(b, x + 1). What breaks if keys areintandx = INT_MAX, and how do you fix it?
Answer
x + 1 overflows (undefined behaviour in C++, wraps to INT_MIN in Java), so the second split puts everything on the right and the key is never removed (or worse). Fix: use a second split that puts keys <= x on the left (compare with <= instead of <), or widen keys to 64 bits.
- A teammate wraps a splay tree in a read-write lock and lets lookups take the read lock. What is the bug?
Answer
Splay lookups rotate nodes, so they are writes; two concurrent "readers" can corrupt the tree. They need the write lock, which kills the concurrency; use a skip list or balanced tree instead.
Further reading / sources
- R. Seidel & C. R. Aragon, "Randomized search trees", Algorithmica 16(4/5):464–497, 1996 (conference version FOCS 1989). The treap, the expected-depth and rotation bounds.
- J. Vuillemin, "A unifying look at data structures", Communications of the ACM 23(4):229–239, 1980. Cartesian trees.
- D. D. Sleator & R. E. Tarjan, "Self-adjusting binary search trees", Journal of the ACM 32(3):652–686, 1985. Splay trees, the access lemma, balance, static optimality and working-set theorems, top-down splaying.
- R. E. Tarjan, "Sequential access in splay trees takes linear time", Combinatorica 5(4):367–378, 1985. A. Elmasry, "On the sequential access theorem and deque conjecture for splay trees", Theoretical Computer Science 314(3), 2004 (the 4.5n bound).
- R. Cole, "On the dynamic finger conjecture for splay trees, Part II: The proof", SIAM Journal on Computing 30(1):44–85, 2000.
- W. Pugh, "Skip lists: a probabilistic alternative to balanced trees", Communications of the ACM 33(6):668–676, 1990. The backward analysis and the case for .
- L. Devroye, "A note on the height of binary search trees", Journal of the ACM 33(3):489–498, 1986; B. Reed, "The height of a random binary search tree", Journal of the ACM 50(3):306–332, 2003.
- C. Martínez & S. Roura, "Randomized binary search trees", Journal of the ACM 45(2):288–323, 1998.
- R. E. Tarjan, C. C. Levy & S. Timmel, "Zip trees", WADS 2019; G. E. Blelloch & M. Reid-Miller, "Fast set operations using treaps", SPAA 1998; J. I. Munro, T. Papadakis & R. Sedgewick, "Deterministic skip lists", SODA 1992.
- M. Herlihy & N. Shavit, The Art of Multiprocessor Programming, 2nd ed., chapter on skip lists and balanced search (lock-based and lock-free concurrent skip lists).
- CLRS, Introduction to Algorithms, 3rd ed., Problem 13-4 "Treaps" and §12.4 "Randomly built binary search trees"; Chapter 17 for the potential method.
- cp-algorithms: Treap (Cartesian tree), including implicit treaps.
- Redis source,
src/t_zset.candsrc/server.h(ZSKIPLIST_P,ZSKIPLIST_MAXLEVEL); Redis documentation on sorted sets and memory optimization (listpack thresholds). - LevelDB source,
db/skiplist.h; RocksDB wiki, "MemTable" (skip-list memtable, concurrent inserts). - Java SE API documentation,
java.util.concurrent.ConcurrentSkipListMap.
Prev: Balanced BSTs: AVL & Red-Black Trees · Next: Heaps & Priority Queues
Related: Module 3 — Trees · Trees (Overview) · Binary Search Trees · Advanced Data Structures · Complexity Analysis · Probability for Engineers · Redis Internals · Storage Engines · Lock-Free Programming · DSA: Zero to Mastery