Treap, in depth: join-based set operations, canonical shapes from keyed priorities, and augmented queries

Two primitives: three-way split and join

The version of split used here takes a key k and returns three things: the tree of keys below k, the node holding k if it is present, and the tree of keys above it. Reporting the middle node is what lets intersection and difference know whether a key was shared. Join is the inverse: given two trees where every key on the left is smaller than every key on the right, and optionally a single node in between, it rebuilds one valid treap. It does this by walking down the right spine of one tree and the left spine of the other, guided by priority.

class Node:
    __slots__ = ("key", "pri", "left", "right", "size")
    def __init__(self, key):
        self.key, self.pri = key, priority(key)       # see the section on priorities
        self.left = self.right = None
        self.size = 1

def size(t): return t.size if t else 0
def pull(t):                                         # recompute augmented fields from children
    t.size = 1 + size(t.left) + size(t.right)
    return t

def split(t, k):
    """Destructive. Returns (keys < k, node holding k or None, keys > k)."""
    if t is None: return None, None, None
    if k < t.key:
        l, m, r = split(t.left, k);  t.left = r;  return l, m, pull(t)
    if t.key < k:
        l, m, r = split(t.right, k); t.right = l; return pull(t), m, r
    l, r = t.left, t.right
    t.left = t.right = None
    return l, pull(t), r

def join2(a, b):                                     # all keys in a below all keys in b
    if a is None or b is None: return a or b
    if a.pri > b.pri:
        a.right = join2(a.right, b); return pull(a)
    b.left = join2(a, b.left); return pull(b)

def join(a, m, b):                                   # a < m.key < b, m detached
    if m is None: return join2(a, b)
    if (a is None or m.pri > a.pri) and (b is None or m.pri > b.pri):
        m.left, m.right = a, b; return pull(m)
    if a is not None and (b is None or a.pri > b.pri):
        a.right = join(a.right, m, b); return pull(a)
    b.left = join(a, m, b.left); return pull(b)

def insert(t, k):
    l, m, r = split(t, k)
    return join(l, m or Node(k), r)

def delete(t, k):
    l, _, r = split(t, k)
    return join2(l, r)

Both primitives walk a single root-to-leaf path, so each costs expected O(log n). Every node they touch is passed through pull on the way back up. That is the only place augmented data is maintained, which matters later.

Set algebra on whole trees

Suppose you have two sets of sizes m and n, with m ≤ n. Merging two sorted arrays costs O(m + n). Inserting the smaller set into the larger one key at a time costs O(m log n). Blelloch and Reid-Miller showed in 1998 that treaps can do better than both: union, intersection and difference in expected O(m log(n/m + 1)) time. When m is much smaller than n this is close to m log n, and when the sizes are equal it is linear. The algorithm is a short recursion on the root with the higher priority.

def union(a, b):
    if a is None or b is None: return a or b
    if a.pri < b.pri: a, b = b, a            # the higher-priority root stays the root
    l, _, r = split(b, a.key)                # duplicate of a.key, if any, is dropped
    a.left, a.right = union(a.left, l), union(a.right, r)
    return pull(a)

def intersect(a, b):
    if a is None or b is None: return None
    if a.pri < b.pri: a, b = b, a
    l, hit, r = split(b, a.key)
    left, right = intersect(a.left, l), intersect(a.right, r)
    if hit is None: return join2(left, right)   # a.key not shared: drop the root
    a.left, a.right = left, right
    return pull(a)

def difference(a, b):                        # keys of a not in b; not symmetric, so no swap
    if a is None or b is None: return a
    l, hit, r = split(b, a.key)
    left, right = difference(a.left, l), difference(a.right, r)
    if hit is not None: return join2(left, right)
    a.left, a.right = left, right
    return pull(a)

The reason union is correct: the root a has the highest priority of any node in either tree, so it must be the root of the result. Every key of b below a.key belongs in the left subtree and every key above it belongs in the right, and the split separates them exactly. The recursion then has two independent sub-problems. They touch disjoint parts of memory, which is why the same algorithm parallelises well with fork-join. Intersection and difference have the same shape. The only difference is whether the root survives, and if it does not, join2 sews the two halves back together. One caveat: the bound is proved for the paper's formulations. The difference shown here always splits b at a's root. That is simpler and correct, and it is the version the tests ran, but measure it before relying on the bound.

These functions are destructive: they reuse the nodes of both inputs. After union(a, b), neither a nor b is a valid tree on its own. If you need the inputs afterwards, copy them first, or use a persistent variant that copies only the nodes on each path it changes.

Worked example: a union, step by step

Take A = {3, 8, 12} and B = {5, 8, 10}, with priorities derived from keys, so 8 has priority 90 in both trees. The others are 3 → 40, 5 → 70, 10 → 20 and 12 → 55.

1. Both roots are 8 with priority 90, so there is no swap and A's 8 is the root.
2. Split B at 8: left {5}, middle B's own 8 (dropped as a duplicate), right {10}.
3. union({3}, {5}): 5 outranks 3, so the arguments swap; the result is 5 with left child 3.
4. union({12}, {10}): 12 outranks 10; the result is 12 with left child 10.
5. Result: 8 at the root, 5 over 3 on the left, 12 over 10 on the right. Both invariants hold.

Priorities from keys: canonical shape and attack resistance

Given distinct keys and distinct priorities, there is exactly one treap that satisfies both invariants. The root must be the highest-priority key, and the same argument applies recursively to each side. With random priorities this is a curiosity. If the priority is a function of the key, it becomes a powerful property: the tree's shape depends only on the set of keys, not on the order of insertions and deletions that produced it.

Equal sets then have identical trees, so a Merkle-style hash per subtree lets you compare whole sets by their root hashes. Tests become deterministic. And the structure is history-independent: it reveals nothing about the order of operations.

The catch: an attacker who can predict priorities can choose keys whose priorities fall as the keys rise and build a chain of linear depth, the same shape as hash-flooding a hash table. The fix is the same too: a keyed hash with a secret.

import hashlib, os

SECRET = os.urandom(16)        # per process; persist it if trees must be reproducible across restarts

def priority(key) -> int:
    h = hashlib.blake2b(repr(key).encode(), key=SECRET, digest_size=8)
    return int.from_bytes(h.digest(), "big")

Two keys collide on a 64-bit priority with negligible probability. If you need certainty, break ties by key. The serialisation of the key (repr here) must be stable: two keys that compare equal must serialise to the same bytes, or the canonical-shape property is lost. Note that 1 and 1.0 compare equal in Python but have different repr output.

Building from sorted input in linear time

Building a treap from n sorted keys by repeated insertion costs O(n log n). Since the result is a Cartesian tree on (key, priority), the linear-time stack construction from Cartesian trees and range minimum applies. Keep the right spine on a stack. For each new key, pop every spine node with a lower priority. The last popped node becomes the new node's left child, and the new node becomes the right child of whatever remains on top of the stack.

def build(sorted_keys):
    stack = []
    for k in sorted_keys:                     # strictly increasing
        n, last = Node(k), None
        while stack and stack[-1].pri < n.pri:
            last = pull(stack.pop())          # a popped subtree is final, so its size is final
        n.left = last
        if stack: stack[-1].right = n
        stack.append(n)
    while len(stack) > 1: pull(stack.pop())
    return pull(stack[0]) if stack else None

Each node is pushed and popped once, so the build is O(n). It is the right way to load a snapshot. With keyed priorities it produces exactly the same tree that any sequence of inserts would have produced.

Augmentation: rank, kth and range aggregates

Any value that can be computed from a node and its two children can be kept in the node and maintained in pull. Subtree size, which every snippet above maintains, gives order statistics in expected O(log n) without changing the tree:

def rank(t, k):                 # number of keys strictly below k
    r = 0
    while t:
        if k <= t.key: t = t.left
        else: r += size(t.left) + 1; t = t.right
    return r

def kth(t, i):                  # 0-based i-th smallest
    while t:
        s = size(t.left)
        if i < s: t = t.left
        elif i == s: return t.key
        else: i -= s + 1; t = t.right
    raise IndexError(i)

Add a value field and a subtree sum, minimum or maximum, and you get range aggregates: count, sum or maximum over keys in a range, computed by descending from the root along the paths to the two ends of the range. A leaderboard is the classic case: keys are (score, user) pairs, rank gives a user's position, and kth gives the user at a given position. The rule that keeps augmentation correct is mechanical. Every function that changes a child pointer must call pull on that node before returning, bottom-up. Lazy tags such as range-add and range-reverse extend this with a push step before descending. That technique is covered for implicit treaps in the companion article. For a structure built purely around range aggregates over a fixed index space, a segment tree is simpler.

What it costs, and the alternatives

In the scratch test behind this article, build(range(100000)) produced a tree of height 40. A perfectly balanced tree would have height 17. The expected depth of a typical node is about 2 ln n, roughly 23 here, and the height of a random treap grows like 4.3 ln n. In other words, you get logarithmic depth with a constant factor between two and three over perfect balance, which is the price of having no balancing logic.

In Python, a node object costs on the order of a hundred bytes and recursion runs deeper than a balanced tree would need. Raise sys.setrecursionlimit modestly, or write split and join iteratively for production. In C++ or Rust, allocate nodes from an arena and store child indices rather than pointers, for both locality and cheap persistence.

Failure modes

• A missing pull. Sizes drift, and kth returns wrong answers long after the bug was introduced. Assert size consistency in tests after every operation.
• Aliasing after destructive operations. Holding a reference to an input after union and reading it later gives a corrupt view. Copy the inputs, or go persistent.
• Unstable key serialisation. With keyed priorities, keys that compare equal but hash differently break canonical shape, and can break deduplication too.
• Keys without a total order. NaN floats, or mixed types that compare inconsistently, produce silently invalid trees.
• Predictable priorities from untrusted keys. These open the door to a linear-depth attack. Use a keyed hash.
• Expecting canonical shape from random priorities. random.random() priorities give good balance but no shape guarantee, so tree-hash comparisons will report unequal for equal sets.

What to do next

1. Implement split, join, insert and delete from this page, and add an invariant checker for order, heap property and sizes.
2. Fuzz union, intersection and difference against your language's built-in set type for a few thousand random cases.
3. Switch priorities to a keyed hash and assert that equal sets produce identical shapes, whatever the insertion order.
4. Add rank and kth, then a subtree aggregate such as a sum, and test range queries against a sorted list.
5. Benchmark bulk union against repeated insertion for m much smaller than n, and for m equal to n.
6. Read the implicit treap section of the companion article to add lazy range updates on sequences.