On this page

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 treeTreap 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 outputImplicit 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 in a is smaller than every key in b.

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:

OperationAs 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 setsrecursive 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.

StepInsertPath / actionTree after (preorder)Height
140 : 62empty tree, becomes root401
220 : 9191 beats root 40:62, split old tree at 2020(-,40)2
370 : 3520:91 → 40:62 → empty slot20(-,40(-,70))3
410 : 1720:91 → empty slot20(10,40(-,70))3
530 : 7420:91 → 74 beats 40:62, split 40(-,70) at 3020(10,30(-,40(-,70)))4
660 : 8820:91 → 88 beats 30:74, split 30(-,40(-,70)) at 6020(10,60(30(-,40),70))4
780 : 5020:91 → 60:88 → 50 beats 70:35, split 70 at 8020(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: p is the root. Rotate x once.
  • Zig-zig: x and p are both left children (or both right children). Rotate p over g first, then x over p.
  • Zig-zag: x is a right child and p a left child, or vice versa. Rotate x over p, then x over g (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.

StepCaseTree after (preorder)Height
start–7(6(5(4(3(2(1,-),-),-),-),-),-)612.30
1zig-zig (x=1, p=2, g=3)7(6(5(4(1(-,2(-,3)),-),-),-),-)612.30
2zig-zig (x=1, p=4, g=5)7(6(1(-,4(2(-,3),5)),-),-)510.71
3zig-zig (x=1, p=6, g=7)1(-,6(4(2(-,3),5),7))48.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):

StepCaseTree after (preorder)Height
1zig-zag (x=3, p=2, g=4)1(-,6(3(2,4(-,5)),7))48.39
2zig-zag (x=3, p=6, g=1)3(1(-,2),6(4(-,5),7))36.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:

StepLevelAtNext keyDecision
14head3131 ≥ 25: drop down
23head77 < 25: move right
3373131 ≥ 25: drop down
4271919 < 25: move right
52193131 ≥ 25: drop down
61192525 ≥ 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.
ApproachInsert/deleteSearchk-th / rankRange reverseGuarantee
Sorted array / worst case
Plain BST, up to with sizesnonone
AVL / red-black with sizesno (split/join possible but rarely implemented)worst case
Treap (keyed / implicit) implicitexpected, any input
Splay treeamortized
Skip list with spansnoexpected, 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,00010.1510.991929.810.0
10,00015.0415.583039.713.3
100,00019.5420.183649.616.6
1,000,00025.3724.795559.619.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 usedPointers per nodeAverage stepsPugh's bound
100,0001/2182.00333.835.2
100,0001/491.33328.534.6
1,000,0001/2202.00339.741.9
1,000,0001/4111.33538.541.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

StructureSearchInsertDeleteSplit / mergeExtra space per nodeKind of bound
Treap, < 2 rotationspriority (+ size)expected, over the structure's own coins
Splay treenone (parent pointer if bottom-up)amortized; a single op can be
Skip list by cutting each level pointers on averageexpected; high probability with max level
AVL / red-black with join-based codebalance 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 for ZSCORE, and the skip list orders (score, member) pairs for range queries. Small sets use a compact listpack (ziplist before Redis 7.0), up to zset-max-listpack-entries (128) and zset-max-listpack-value (64 bytes). Redis's skip list (in t_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 so ZRANK is , 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 its InlineSkipList additionally 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 a size() 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 libiberty ships splay-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::tree offers a splay_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> gives find_by_order and order_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); erase must then remove one copy, by splitting out the == x part and merging its root's children.
  • erase(x) with split(b, x + 1) overflows when x is the maximum integer. Use a split variant that puts == x on the left (split_le) instead of x + 1, or use 64-bit keys.
  • Forgetting pull or push. Missing one shows up as wrong k-th answers only after a specific operation sequence; an invariant checker like check() finds it in seconds.
  • Off-by-one in implicit split. To isolate 0-indexed l..r, split at l, then the right part at r - l + 1; for 1-indexed a..b, at a - 1 then b - 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

PropertyTreapSplay treeSkip listAVLRed-black
Guaranteeexpected amortized expected worst case, height ≤ 1.44 log₂ nworst case, height ≤ 2 log₂(n+1)
Typical depth/cost≈ 1.39 log₂ nadapts to access pattern≈ 2 log₂ n comparisons≈ log₂ n≈ log₂ n
Per-node overheadprioritynone (parent if bottom-up)1/(1−p) pointersheight or balancecolour bit
Rotations per update< 2 expectedO(log n) amortizednone≤ 2 insert, O(log n) delete≤ 2 insert, ≤ 3 delete
Split / mergenatural, O(log n)natural, O(log n)cut each level, O(log n)possible (join-based)possible (join-based)
Reads modify structurenoyesnonono
Concurrencyhardvery hardgood (lock-free designs exist)hardhard
Lines of code (set)≈ 40≈ 80≈ 60≈ 120≈ 200
Best atsequence ops, contests, set algebraskewed / local access, link-cut treesconcurrent maps, memtables, Redis zsetsread-heavy ordered mapsgeneral-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

  1. 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.

  1. In the zig-zig case, what goes wrong if you rotate x twice (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.

  1. 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.

  1. You delete a key from a treap with split(t, x) then split(b, x + 1). What breaks if keys are int and x = 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.

  1. 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.c and src/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