Treaps and Skip Lists: When Randomness Beats Balance

9 min read · Last updated: October 24, 2026

Treaps and skip lists are randomized data structures that keep sorted data searchable in O(log n) expected time without strict rebalancing rules. A treap gives every key a random priority and keeps the tree heap-ordered on it. A skip list flips a coin to decide how many express lanes each element gets. Both are far simpler to write than red-black trees.

Came here from Instagram, LinkedIn, X or YouTube? Here is the full source list you came for. Everything below is built from these, nothing else.

The article that started this

• Swastik Raj, "When Randomness Beats Perfection: Treaps and Skip Lists", Part 6 of the Advanced Algorithms & Data Structures series, Medium, Oct 24 2026

The original papers

• William Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees", Communications of the ACM 33(6), 1990 (PDF)
• Seidel and Aragon, "Randomized Search Trees", FOCS 1989, summarised on Wikipedia's Treap page

The production receipts

• Redis docs: Sorted sets implementation note
• Redis source: server.h, ZSKIPLIST_MAXLEVEL and ZSKIPLIST_P
• RocksDB wiki: MemTable
• Java SE 21 docs: ConcurrentSkipListMap

Key takeaways

• Both structures give O(log n) expected time for search, insert and delete. The worst case is O(n), but it is extremely unlikely.
• Pugh's 1990 paper: in a skip list of more than 250 elements, the chance a search takes over 3x the expected time is less than one in a million.
• Redis builds every sorted set from a skip list plus a hash table, with p = 1/4 and a max level of 32.
• RocksDB's default memtable is a skip list, at roughly 1.33 pointers per entry.
• A treap needs just two operations, split and merge, to give you insert, delete, range cuts and joins.
• Pick a red-black tree when you need a guaranteed worst case, not an expected one.

What are treaps and skip lists, in one picture?

Treaps and skip lists solve the same problem as an AVL or red-black tree: keep data sorted and find anything in about log n steps. The difference is how they stay balanced. Balanced trees enforce strict rules after every change. These two let a random number generator do the balancing, and the math says it almost always works.

Here is the comparison that makes it click. Think of a city metro line with local and express trains.

The local train stops at every station. That is a plain sorted linked list: to reach station 9, you pass stations 1 through 8.

Now add an express train that stops at roughly every second station, and a super express that stops at roughly every fourth. To get to station 9, you ride the super express as far as you can without overshooting, drop to the express, then finish on the local. You touch a handful of stations instead of all of them.

The interesting part is how the express stops get picked. A careful planner would space them perfectly. Pugh's insight was that you do not need a planner. When a station opens, flip a coin. Heads, it also becomes an express stop. Flip again. Heads, it becomes a super express stop too. The spacing comes out close enough to perfect, and no station ever has to be renumbered when a new one opens.

That is a skip list. A treap uses the same idea on a tree: instead of a planner keeping the tree balanced, every key draws a random lottery number, and the tree arranges itself around those numbers.

Why use randomness instead of a balanced tree?

Randomness replaces complex rebalancing logic with a few lines of code, and you give up almost nothing in speed. Pugh's paper opens with the reason: skip list insertion and deletion are "much simpler and significantly faster than equivalent algorithms for balanced trees." The cost is that O(log n) becomes an expected bound, not a guarantee.

Pugh's argument starts from a fact about ordinary binary search trees. They work well when keys arrive in random order. They fall apart when keys arrive sorted, because the tree becomes one long chain. You usually cannot shuffle your input, since queries have to be answered as they come.

So instead of shuffling the input, both structures shuffle something internal:

• A skip list randomizes each node's height.
• A treap randomizes each node's priority.

The important detail: no input sequence is bad for these structures. As Pugh puts it, skip lists "have bad worst-case performance" but "no input sequence consistently produces the worst-case performance," much like quicksort with a random pivot. An attacker who sends you sorted keys gets the same expected performance as everyone else.

	Treap	Skip list	Red-black tree
Invented	Seidel and Aragon, 1989	William Pugh, 1989 report, CACM 1990	1970s, textbook standard
Balance method	Random priority per key	Random height per node	Colour rules and rotations
Search, insert, delete	O(log n) expected	O(log n) expected	O(log n) worst case
Worst case	O(n), very unlikely	O(n), very unlikely	O(log n)
Lines of code	Short	Short	Long, many cases
Split and merge	Natural, O(log n) expected	Possible	Possible but fiddly
Famous user	Competitive programming	Redis, RocksDB, Java	Many language standard libraries

How does a skip list work, step by step?

A skip list is a sorted linked list with extra forward pointers stacked on top. Each node gets a random level when it is inserted, and a level k node has k forward pointers. Search starts at the top level, moves right while the next key is smaller, and drops down a level when it cannot go further.

Pugh's paper lays out the mechanics:

1. Start with a header node that has room for MaxLevel pointers, all pointing to NIL.
2. Choose a level for each new node by flipping a biased coin. Start at level 1 and keep going up while random() < p. With p = 1/2, about 50% of nodes are level 1, 25% are level 2, 12.5% are level 3, and so on.
3. Search from the top. At each level, move forward while the next key is smaller than your target. When you cannot, drop one level.
4. At level 1, look one step right. That node is either your key or proof the key is not there.
5. To insert, run the search while recording the last node you visited on each level (Pugh calls this the update vector). Then splice the new node in after each of those nodes, up to its level.
6. To delete, run the same search and unlink the node from every level it appears on.

The level is chosen once and never changes. That is why an insert only touches the nodes right next to it, and it is the main reason skip lists are easy to make concurrent.

Pugh also covers the cap. He recommends MaxLevel = log base 1/p of N, where N is the most elements you expect. With p = 1/2, a MaxLevel of 16 covers up to 2^16 elements.

Why does Redis use p = 1/4 instead of 1/2?

Lower p means fewer pointers per node, at the cost of slightly longer searches. Pugh notes skip lists "can easily be configured to require an average of 1 1/3 pointers per element," which is what p = 1/4 gives you. Redis picks exactly that. In its server.h, ZSKIPLIST_P is 0.25 and ZSKIPLIST_MAXLEVEL is 32, with the comment "Should be enough for 2^64 elements."

RocksDB lands in the same place. Its wiki says the default memtable "is based on skiplist" and lists memory overhead at roughly 1.33 pointers per entry.

How does a treap work, step by step?

A treap is a binary search tree on keys and a heap on random priorities at the same time. Every key gets a random priority when inserted, and the node with the highest priority becomes the root. Because priorities are random, the tree has the same shape as a BST built from a random insertion order, which keeps its height logarithmic.

The name is tree plus heap. Raimund Seidel and Cecilia Aragon introduced it in "Randomized Search Trees" at FOCS 1989, the IEEE Symposium on Foundations of Computer Science, with a fuller version in the journal Algorithmica in 1996.

The classic operations:

1. Search like any BST. Ignore the priorities completely.
2. Insert the new key as a leaf with a random priority.
3. Rotate it up while its priority is higher than its parent's. Each rotation keeps BST order and fixes heap order one level at a time.
4. Delete by rotating the node down toward its higher-priority child until it becomes a leaf, then cut it off.

There is a cleaner way that most people use today: build everything from split and merge.

• Split(t, k) cuts a treap into two: all keys below k, and all keys from k up.
• Merge(a, b) joins two treaps where every key in a is smaller than every key in b. The root with the higher priority wins and the rest recurses.

Insert becomes split, then merge three pieces. Delete becomes two splits and one merge. The Medium article notes this is also what powers implicit treaps, where position replaces the key and you get a dynamic array with insert-at-index and range operations.

When should you use treaps or skip lists, and when not?

Use a skip list when you need an ordered map that many threads write to, or ordered range scans over in-memory data. Use a treap when you need to split and join sorted sequences quickly, or you are writing a balanced tree from scratch under time pressure. Avoid both when a guaranteed worst case matters more than a typical one.

Reach for a skip list when:

• Many threads write at once. Java ships ConcurrentSkipListMap, which the docs say provides "expected average log(n) time cost" for get, put and remove, and whose operations "safely execute concurrently by multiple threads." RocksDB notes that "only skiplist-based memtable supports" concurrent memtable inserts.
• You need rank and range queries. Redis sorted sets answer ZRANGE in O(log(N) + M) and ZRANK in O(log(N)), per the Redis command docs.
• You want sequential scans. The bottom level is just a sorted linked list.

Reach for a treap when:

• You split and merge sequences. Cutting a sorted set at a key and gluing two sets together are both one function call.
• You need a sequence with fast middle inserts. That is the implicit treap.
• You are in a contest or interview and need a balanced tree in 30 lines instead of 300.

Do not use either when:

• You need hard latency guarantees. "Very unlikely" is not "never." A real-time system wants an AVL or red-black tree.
• A standard library already gives you a sorted map. Do not hand-roll what your language ships.
• Your random source is predictable to an attacker. The "no bad input" promise assumes the attacker cannot guess your coin flips.
• The data does not change. A sorted array with binary search is smaller and faster.

If you are prepping for interviews, these tradeoffs come up more than the code does. We covered the thinking side in why most developers fail system design interviews.

What does the code look like?

Here is a skip list in Python, translated line for line from Pugh's pseudocode in Figures 2, 4 and 5 of the paper.

import random

class Node:
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * level

class SkipList:
    MAX_LEVEL = 16
    P = 0.5

    def __init__(self):
        self.head = Node(None, self.MAX_LEVEL)
        self.level = 1

    def _random_level(self):
        lvl = 1
        while random.random() < self.P and lvl < self.MAX_LEVEL:
            lvl += 1
        return lvl

    def search(self, key):
        x = self.head
        for i in reversed(range(self.level)):
            while x.forward[i] and x.forward[i].key < key:
                x = x.forward[i]
        x = x.forward[0]
        return x is not None and x.key == key

    def insert(self, key):
        update = [self.head] * self.MAX_LEVEL
        x = self.head
        for i in reversed(range(self.level)):
            while x.forward[i] and x.forward[i].key < key:
                x = x.forward[i]
            update[i] = x
        if x.forward[0] and x.forward[0].key == key:
            return
        lvl = self._random_level()
        self.level = max(self.level, lvl)
        node = Node(key, lvl)
        for i in range(lvl):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node

Notice what is missing: no rotations, no colours, no case analysis. The update list starts filled with the header, so a node taller than the current list automatically links from the header on its new levels.

And here is a treap built on split and merge, with integer keys:

import random

class TNode:
    def __init__(self, key):
        self.key = key
        self.prio = random.random()
        self.left = None
        self.right = None

def split(t, key):
    # returns (keys < key, keys >= key)
    if t is None:
        return None, None
    if t.key < key:
        l, r = split(t.right, key)
        t.right = l
        return t, r
    l, r = split(t.left, key)
    t.left = r
    return l, t

def merge(a, b):
    # every key in a is smaller than every key in 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

def insert(t, key):
    l, r = split(t, key)
    return merge(merge(l, TNode(key)), r)

def delete(t, key):
    l, r = split(t, key)
    _, r = split(r, key + 1)
    return merge(l, r)

Usage is one line per operation: root = insert(root, 5), root = delete(root, 5). Feed it keys 1, 2, 3 in order, the input that turns a plain BST into a linked list, and the random priorities still give you a tree of expected logarithmic height.

A diagram in words, for the skip list in Pugh's Figure 1 with keys 3, 6, 7, 9, 12, 17, 19, 21, 25, 26:

L4  head ---------------------------------------> 21 -------------> NIL
L3  head ---------------> 9 --------------------> 21 -------------> NIL
L2  head ------> 6 -----> 9 ------> 17 ---------> 21 ------> 26 --> NIL
L1  head -> 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25 -> 26 -> NIL

To find 19: on L4, 21 is too far, drop. On L3, go to 9, then 21 is too far, drop. On L2, go to 17, then 21 is too far, drop. On L1, step to 19. Found in four moves instead of seven. This shows the perfectly spaced version from the paper; a real skip list's levels are random, so the spacing is uneven, but the search works the same way.

If you are learning this material, it helps to have an AI explain your own broken version back to you. Here is how I approach that in using AI to learn programming faster.

FAQ

Are skip lists faster than balanced trees?

Pugh's 1990 paper claims skip list algorithms give "significant constant factor speed improvements" over balanced and self-adjusting trees, mainly because the code does less work per operation. Both have O(log n) search. The practical win is simpler code and easy concurrency, which is why Java and RocksDB use them.

What is the worst case for a treap or skip list?

Both degrade to O(n) in the worst case, if the random numbers come out badly. Pugh shows how unlikely that is: for more than 250 elements, the chance that a search takes over 3x the expected time is under one in a million. It gets less likely as the structure grows.

Why does Redis use a skip list for sorted sets?

Redis docs describe sorted sets as "a dual-ported data structure containing both a skip list and a hash table." The hash table finds a member's score directly, and the skip list keeps members in score order, so range and rank queries such as ZRANGE run in O(log(N) + M) without sorting at read time.

What is the difference between a treap and a Cartesian tree?

A treap is a Cartesian tree where the priorities are random. A Cartesian tree arranges (key, priority) pairs as a BST on keys and a heap on priorities. When the priorities are random and distinct, you get exactly one tree for a given set, with logarithmic expected height.

Write the skip list above from memory once, then break it by setting P to 0.9 and watch what happens. For everything else, the free tools on Art of Code are there, and if you want more on how languages themselves get built, read programming languages and the languages used to build them.

Written by Adithya Guttha, Founder of Art of Code.