Treap, in depth: a binary search tree balanced by random priorities, with split, merge, order statistics and implicit keys

Two invariants, one tree

Every node holds a key and a priority. The tree must satisfy two rules at once. Keys follow the search-tree rule: everything in a node's left subtree has a smaller key, everything in its right subtree a larger one. Priorities follow the heap rule: a node's priority is larger than the priorities of its children (this page uses a max-heap; a min-heap works the same way with the comparisons flipped).

With distinct keys and distinct priorities there is exactly one tree that satisfies both. The node with the highest priority must be the root, because the heap rule forbids anything above it. Its key then splits the remaining keys into a left set and a right set, and the same argument applies recursively to each. That recursive definition is the Cartesian tree, described by Jean Vuillemin in 1980. It also shows that the treap's shape equals the BST you would get by inserting the keys in decreasing priority order. Random priorities therefore mean a random insertion order, and the treap inherits the shape of a random BST no matter what order the caller used.

Why random priorities keep it shallow

Number the keys 1 to n in sorted order. Key i is an ancestor of key j exactly when i has the highest priority among all keys from i to j inclusive. If any key strictly between them had a higher priority it would become the root of a subtree that separates i from j. That range holds |i - j| + 1 keys, each equally likely to have the largest priority, so the probability is 1 / (|i - j| + 1).

The expected depth of key j is the sum of those probabilities over all other keys: H(j) + H(n - j + 1) - 2, where H is the harmonic number. That is less than 2 ln n, about 1.39 log2 n, for every key. So a search, which walks one root-to-node path, costs O(log n) expected comparisons. The tallest path is longer than the average one. For random BSTs Luc Devroye showed in 1986 that height is asymptotically about 4.311 ln n, and that bound applies to treaps. Seidel and Aragon also showed that an insertion or deletion performs fewer than two rotations on average.

Note what the guarantee depends on: the priorities must be independent of the keys and unknown to whoever chooses the keys. An adversary who can predict your random number generator can choose keys that build a deep tree, the same way predictable hash seeds enable hash-flooding attacks.

Split and merge: the only two hard functions

split(t, key) cuts a treap into two treaps: L with keys below key and R with the rest. At each node it decides which side the node belongs to and recurses into the one child subtree that may straddle the cut. merge(a, b) does the inverse for two treaps where every key in a is below every key in b. The root with the higher priority becomes the root of the result, and the recursion merges the remaining inner pieces. Both walk a single path, so both take time proportional to depth: O(log n) expected.

import random

class Node:
    __slots__ = ("key", "pri", "left", "right", "size")
    def __init__(self, key, pri):
        self.key, self.pri = key, pri
        self.left = self.right = None
        self.size = 1

def size(t):
    return t.size if t else 0

def pull(t):                       # recompute augmented data after a child changes
    t.size = 1 + size(t.left) + size(t.right)
    return t

def split(t, key):
    """Return (L, R): L holds keys < key, R holds keys >= key."""
    if t is None:
        return None, None
    if t.key < key:
        l, r = split(t.right, key)
        t.right = l
        return pull(t), r
    l, r = split(t.left, key)
    t.left = r
    return l, pull(t)

def merge(a, b):
    """Precondition: 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.pri > b.pri:
        a.right = merge(a.right, b)
        return pull(a)
    b.left = merge(a, b.left)
    return pull(b)

The size field is an augmentation: each node stores the number of nodes in its subtree. pull recomputes it from the children and must run on every node whose children changed. Any other subtree aggregate (sum, minimum, maximum) is maintained the same way, in pull.

Everything else is a few lines

Insert splits at the new key and merges the pieces back around a fresh single-node treap. Erase finds the node and replaces it with the merge of its two children, which are already key-ordered relative to each other; this works for any comparable key type. Search is ordinary BST search and needs no priority. With sizes stored, kth-smallest and rank are a single walk down the tree.

def insert(t, key, pri=None):
    if contains(t, key):
        return t                   # set semantics; see "Duplicates" below
    l, r = split(t, key)
    node = Node(key, random.random() if pri is None else pri)
    return merge(merge(l, node), r)

def erase(t, key):
    if t is None:
        return None
    if key == t.key:
        return merge(t.left, t.right)   # children are already key-ordered
    if key < t.key:
        t.left = erase(t.left, key)
    else:
        t.right = erase(t.right, key)
    return pull(t)

def contains(t, key):
    while t:
        if key == t.key:
            return True
        t = t.left if key < t.key else t.right
    return False

def kth(t, k):
    """0-based: kth(t, 0) is the minimum."""
    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 IndexError(k)

def rank(t, key):
    """Number of keys strictly less than key."""
    r = 0
    while t:
        if key <= t.key:
            t = t.left
        else:
            r += size(t.left) + 1
            t = t.right
    return r

Worked example, traced

Insert the keys 50, 30, 70, 20, 40, 60, 80 with fixed priorities 0.31, 0.82, 0.47, 0.15, 0.93, 0.58, 0.26 so the result is reproducible. Running the code above prints the tree in the diagram. Key 40 has the largest priority, 0.93, so it is the root even though it arrived fifth. Keys 20 and 30 go left; 30 outranks 20 and sits above it. On the right, 60 (0.58) outranks 50, 70 and 80, so it is the subtree root, with 50 on its left and 70 above 80 on its right. The tree has four levels.

Now trace split(t, 55). At the root, 40 is below 55, so 40 and its left subtree belong to L and the recursion continues into the right subtree. At 60, 60 is at least 55, so 60 and its right subtree belong to R and the recursion goes left. At 50, 50 is below 55, so 50 goes to L. The results are L = 40 with children 30 (and 20 below it) and 50, and R = 60 with 70 and 80 on its right. Three nodes were visited, one per level of the path.

Size queries on the original tree: kth(t, 3) returns 50 (0-based, so it is the fourth smallest), and rank(t, 65) returns 5 because five keys (20, 30, 40, 50, 60) are below 65. Erasing 40 merges its two children: 30 (0.82) outranks 60 (0.58), so 30 becomes the root, keeps 20 on its left and takes the whole 60 subtree as its right child. The heap rule and the key order both still hold, and the code's own checker confirms it.

The rotation formulation

The original treap papers describe insertion with rotations instead of split and merge. Insert the new node as a leaf exactly as in a plain BST, then, while its priority exceeds its parent's, rotate it up one level. Deletion rotates the node down, each time promoting the child with the higher priority, until it is a leaf, then removes it. The final shapes are identical because the treap is unique. Rotations suit code that already has a rotation-based BST; split and merge suit range operations and persistence.

Implicit treaps: sequences instead of sets

Drop the stored key and treat a node's position in the in-order traversal as its key. The position is never stored; it is computed from subtree sizes while descending, exactly as kth does. The result is an array-like sequence with O(log n) expected insert at any index, delete at any index, concatenation and splitting. Add lazy flags and it supports range reversal, range add and range sum. That makes it a compact alternative to a rope for text buffers, or to a segment tree when elements must be inserted in the middle.

class INode:
    __slots__ = ("val", "pri", "left", "right", "size", "rev")
    def __init__(self, val):
        self.val, self.pri = val, random.random()
        self.left = self.right = None
        self.size, self.rev = 1, False

def push(t):                       # apply a pending reversal before looking inside
    if t and t.rev:
        t.left, t.right = t.right, t.left
        for ch in (t.left, t.right):
            if ch:
                ch.rev = not ch.rev
        t.rev = False

def split_at(t, k):
    """First k elements go left, the rest right."""
    if t is None:
        return None, None
    push(t)
    if size(t.left) < k:
        l, r = split_at(t.right, k - size(t.left) - 1)
        t.right = l
        return pull(t), r
    l, r = split_at(t.left, k)
    t.left = r
    return l, pull(t)

def merge_i(a, b):                 # merge that pushes before descending
    if a is None or b is None:
        return a or b
    if a.pri > b.pri:
        push(a)
        a.right = merge_i(a.right, b)
        return pull(a)
    push(b)
    b.left = merge_i(a, b.left)
    return pull(b)

def reverse(t, i, j):              # reverse positions i..j-1
    a, b = split_at(t, i)
    b, c = split_at(b, j - i)
    if b:
        b.rev = not b.rev
    return merge_i(merge_i(a, b), c)

The lazy reversal flag shows the general rule for lazy propagation: call push on a node before reading or changing its children, and call pull after. That is why reverse uses merge_i, a merge that pushes; a forgotten push gives wrong answers, not crashes.

What the measurements look like

Inserting the keys 0 to n - 1 in sorted order destroys a plain BST, whose height becomes n. Running the treap code above, calling random.seed(1) before each size, gave a height of 21 levels for n = 1,000 and 41 levels for n = 100,000. Each figure is a single seeded run. For comparison, the asymptotic height of a random BST, 4.311 ln n, is about 29.8 and 49.6 for those sizes; finite trees fall below that limit. A hundredfold increase in n added about 20 levels.

Constant factors still matter: every operation chases pointers with poor cache locality, so sorted arrays and B-trees are faster for read-heavy work. The treap's advantages are simplicity, split and merge, and order statistics, not raw speed.

Failure modes

• Stale augmentation. Changing a child pointer without calling pull leaves sizes wrong, and kth and rank fail silently. Assert the size invariant in tests.
• Violated merge precondition. Merging pieces in the wrong order yields a valid heap that is no longer a valid BST.
• Duplicates. Choose set or multiset semantics up front; for a multiset, store a count per node or use strict and inclusive splits consistently.
• Predictable priorities. A fixed seed or weak generator lets an attacker who controls keys build a deep tree. Seed from the operating system for untrusted input.
• Recursion depth. Unlucky or adversarial trees can exceed small recursion limits; iterative split and merge avoid this.
• Lazy flags not pushed. In implicit treaps, every function that descends must push first, including merge.

Trade-offs

What to do next

1. Type in split, merge and pull from this page and write a randomized test that compares a treap against a sorted Python list after every operation.
2. Add the in-order, heap-order and size checks as assertions that run after each test operation.
3. Re-run the worked example with the given priorities and confirm you get the same tree, kth and rank results.
4. Add a subtree sum to pull and answer range-sum queries by splitting out the range.
5. Build an implicit treap with range reversal and test it against list slicing and reversal.
6. Review the BST fundamentals in the BST operations deep dive and the Cartesian-tree view in Cartesian trees and range minimum.
7. Compare against the other probabilistic ordered structure in the skip list article, and see a size-augmented solution to one query type in kth smallest in a BST.