vault

Treap

23 min read

Treap

A treap (a portmanteau of tree + heap) is a randomized binary search tree introduced by Aragon and Seidel at FOCS 1989 (later expanded in Algorithmica 1996). Each node holds two values: a key (chosen by the user, BST-ordered) and a priority (chosen randomly at insertion time, max-heap-ordered). The combined invariants are node.left.key < node.key < node.right.key (BST property) AND node.priority > node.left.priority and node.priority > node.right.priority (max-heap property). Together, the two invariants determine the tree’s shape uniquely given the keys and priorities — and because priorities are random, the tree shape is a random binary search tree whose expected height is Θ(log n). Treaps thus provide the same expected-time guarantees as AVL Trees and Red-Black Trees but with a much simpler implementation: there is no explicit balance condition to maintain, no balance factor to compute, no case analysis on insert and delete. Just BST insert, then rotate up while priorities violate the heap. The trade-off is that bounds are expected (over random priority choices), not worst-case — a treap can in principle degenerate, but only with probability vanishingly small. Treaps are the data structure of choice in competitive programming for problems requiring “balanced BST with custom augmentation,” and the implicit treap variant (key replaced by subtree-size-based position) supports O(log n) array operations including reverse-a-subarray, which neither AVL nor RB provides.

1. Intuition — Random Priorities Make a BST Self-Balance

A standard Binary Search Tree has a problem: its shape depends on insertion order. Insert keys in sorted order and you get a degenerate chain of height n. The classical fix is to add an explicit balancing scheme — AVL Trees use height balance with rotations on each modification, Red-Black Trees use color invariants. These work but require careful case analysis: each modification can trigger one of a fixed set of structural fix-ups, each implemented as a small dance of rotations and bookkeeping updates.

The treap takes a fundamentally different approach: make the tree’s shape depend only on the keys and on randomly assigned priorities. The shape is then a deterministic function of (key, priority) pairs, so by controlling the priority distribution we control the expected shape — and a random priority assignment yields, in expectation, a balanced tree. The data structure is just a Binary Search Tree keyed by key and a Binary Heap ordered by priority, simultaneously, on the same node set. Both invariants happen to be jointly satisfiable for any choice of (key, priority) pairs (proof: §3.4), and the satisfying tree is unique.

The key insight is that the resulting tree is the same as the tree you would get from inserting items into a plain BST in priority-decreasing order. The highest-priority item becomes the root (it must, since the heap property says priority decreases downward). The second-highest priority becomes the root of either the left or right subtree, depending on whether its key is smaller or larger than the root’s. And so on. Because we are inserting in priority order, and priorities are assigned uniformly at random, this is equivalent to inserting items in a uniformly random order — and a binary search tree built by uniformly-random insertion order is well understood: the expected depth of any individual node is ≤ 2·ln n + O(1) ≈ 1.39·log₂ n, and the expected height (the longest root-to-leaf path) is ≈ 4.311·ln n ≈ 2.99·log₂ n (per Wikipedia’s Random binary search tree article, citing Devroye 1986 and Reed 2003). Both are Θ(log n); the distinction between typical node depth and worst-leaf height matters when quoting a constant, and the two are routinely conflated (see §6.2). The constant 4.311 = 1/β where β is the unique root of 2βe^(1−β) = 1.

So the treap’s O(log n) expected guarantee is not magic. It is the standard random-BST bound, made constructive: instead of requiring the user to insert in random order (which most users do not control), we assign a random priority on insertion, which has the same effect.

The real-world analogy: imagine ranking employees both alphabetically by name (BST) and by hire date (heap). The org chart that simultaneously satisfies “names sorted left-to-right” and “earlier hires above later” is uniquely determined, and if hire dates are random, the chart is roughly balanced regardless of the alphabetical distribution of names.

The treap was introduced by Aragon and Seidel in their 1989 FOCS paper “Randomized Search Trees” — the first construction of a self-balancing BST achieving expected-time guarantees without explicit structural invariants. The 1996 Algorithmica journal paper expands the analysis (proving the O(log n) expected bounds rigorously and analyzing variants like finger search).

2. The Two Invariants

A treap is a binary tree of nodes, each with a key and a priority. The two invariants are:

  1. BST property on keys. For every node v, every key in v.left is < v.key, and every key in v.right is > v.key.
  2. Max-heap property on priorities. For every node v, v.priority ≥ v.left.priority and v.priority ≥ v.right.priority. (Some implementations use a min-heap; the choice is arbitrary as long as it is consistent.)

Together: keys are BST-ordered (in-order traversal yields sorted keys), priorities are heap-ordered (root has the highest priority, decreasing as you descend).

2.1 Existence and uniqueness of the satisfying tree

Claim. Given any set of n distinct (key, priority) pairs, there is exactly one binary tree satisfying both invariants.

Proof sketch. Take the pair with the highest priority. By the heap invariant, it must be the root. By the BST invariant, all keys smaller than it go in the left subtree, all keys larger go in the right. Recursively, the left subtree is the unique treap for the left-subset, and the right subtree is the unique treap for the right-subset. Induction on n completes the argument. ∎

This existence-uniqueness lemma is what makes treaps “tame”: there is no choice in the structure once priorities are assigned. All operations just need to maintain the structure consistently.

2.2 Why “random” priorities

If priorities are chosen uniformly at random from a large enough range (e.g., 32-bit or 64-bit unsigned ints), then:

  • All priorities are distinct with high probability (collision probability ≈ n²/2^32 for 32-bit, ≈ n²/2^64 for 64-bit; for n = 10^6 and 64-bit priorities, the probability is ≈ 5 × 10^{-8}).
  • The ranking of priorities is a uniformly random permutation of the keys, equivalent to inserting keys in a uniformly random order into a plain BST.
  • The shape is therefore a random BST: expected per-node depth ≈ 1.39·log₂ n and expected height ≈ 3·log₂ n, with the height sharply concentrated (exponentially decaying tail; Reed 2003). See §6.2 for the depth-versus-height distinction.

The randomness only needs to be cryptographically irrelevant — a Mersenne Twister or even rand() is sufficient. Adversarial inputs (a malicious user picking keys to defeat the data structure) cannot defeat a treap because the priorities, not the keys, control the shape; the user does not see the priorities.

3. Tiny Worked Example — Insertion via Rotation-Up

Insert keys 10, 20, 30, 5, 15 into an initially empty treap. Suppose priorities (assigned at insertion time) are 45, 70, 30, 90, 60 respectively.

3.1 Insert (10, 45)

Empty tree. Place at root.

(10, 45)

3.2 Insert (20, 70)

BST insert: 20 > 10, place as right child of root.

(10, 45)
   \
   (20, 70)

Heap check: 20’s priority 70 > 10’s priority 45. Heap invariant violated (parent should have higher priority than child).

Fix: rotate 20 up over 10. A left rotation at 10 brings 20 to the root.

   (20, 70)
   /
(10, 45)

Now check the heap invariant for 20 and its children. (10, 45): 45 < 70 ✓. Right is null. ✓

3.3 Insert (30, 30)

BST insert: 30 > 20 > 10, so place as right child of 20.

   (20, 70)
   /     \
(10,45) (30, 30)

Heap check at 30: priority 30 < 20’s priority 70. ✓ No rotation needed.

3.4 Insert (5, 90)

BST insert: 5 < 20, descend left; 5 < 10, place as left child of 10.

        (20, 70)
       /        \
   (10, 45)   (30, 30)
   /
(5, 90)

Heap check at 5: priority 90 > 10’s priority 45. Violation.

Fix: rotate 5 up over 10. A right rotation at 10 brings 5 up.

        (20, 70)
       /        \
   (5, 90)    (30, 30)
       \
       (10, 45)

Now check at 5’s new position: parent is 20, priority 70 < 90. Violation again.

Fix: rotate 5 up over 20. Another right rotation, this time at 20.

   (5, 90)
       \
       (20, 70)
       /     \
   (10,45) (30, 30)

All heap invariants now hold: 90 > 70, 70 > 45, 70 > 30. ✓ All BST invariants hold (in-order: 5, 10, 20, 30). ✓

This is the bubble-up pattern that defines treap insertion. After standard BST insert, rotate the new node up while its priority exceeds its parent’s. The number of rotations is at most equal to the depth of the inserted node, which is Θ(log n) in expectation.

3.5 Insert (15, 60)

BST insert: 15 < 20, descend left to 10 (5’s right child)… wait, the tree is now:

   (5, 90)
       \
       (20, 70)
       /     \
   (10,45) (30, 30)

15 < 20, descend left to (10, 45). 15 > 10, descend right (no node there). Place as right child of 10:

   (5, 90)
       \
       (20, 70)
       /     \
   (10,45) (30, 30)
       \
       (15, 60)

Heap check at 15: priority 60 > 10’s priority 45. Violation.

Rotate 15 up over 10. A left rotation at 10 (15 was right child, so left rotation):

   (5, 90)
       \
       (20, 70)
       /     \
   (15, 60) (30, 30)
   /
(10, 45)

Heap check at 15’s new position: parent 20, priority 70 > 60. ✓ Done.

In-order traversal: 5, 10, 15, 20, 30. ✓ All heap invariants hold. ✓

4. Algorithm — BST Operations + Bubble-Up / Bubble-Down

4.1 Insert (rotation-based)

TreapInsert(node, key, priority):
    if node is null:
        return new Node(key, priority)
    if key < node.key:
        node.left = TreapInsert(node.left, key, priority)
        if node.left.priority > node.priority:
            node = RotateRight(node)
    elif key > node.key:
        node.right = TreapInsert(node.right, key, priority)
        if node.right.priority > node.priority:
            node = RotateLeft(node)
    return node

The recursion descends to insert (BST-style), then on the way back up, rotates the child up if its priority is larger. Each rotation is O(1).

4.2 Delete (rotation-based)

The trick: rotate the node-to-delete down until it becomes a leaf, then snip it off. The rotation direction at each step is chosen to keep the heap invariant: rotate the higher-priority child up.

TreapDelete(node, key):
    if node is null:
        return null
    if key < node.key:
        node.left = TreapDelete(node.left, key)
    elif key > node.key:
        node.right = TreapDelete(node.right, key)
    else:
        # Found the node to delete.
        if node.left is null and node.right is null:
            return null
        if node.left is null:
            node = RotateLeft(node)
            node.left = TreapDelete(node.left, key)
        elif node.right is null:
            node = RotateRight(node)
            node.right = TreapDelete(node.right, key)
        elif node.left.priority > node.right.priority:
            node = RotateRight(node)
            node.right = TreapDelete(node.right, key)
        else:
            node = RotateLeft(node)
            node.left = TreapDelete(node.left, key)
    return node

4.3 Split and Merge (the other canonical interface)

A second equivalent implementation philosophy uses split and merge as the primitives, and implements insert/delete on top of them. This is the form preferred by competitive programmers because it generalizes cleanly to implicit treaps (§7.1).

Split(tree, K) returns (L, R) where L contains all nodes with key ≤ K, R all nodes with key > K:

Split(t, K):
    if t is null: return (null, null)
    if t.key <= K:
        (L, R) = Split(t.right, K)
        t.right = L
        return (t, R)
    else:
        (L, R) = Split(t.left, K)
        t.left = R
        return (L, t)

Merge(L, R) returns the treap of L ∪ R (assuming all keys in L < all keys in R):

Merge(L, R):
    if L is null: return R
    if R is null: return L
    if L.priority > R.priority:
        L.right = Merge(L.right, R)
        return L
    else:
        R.left = Merge(L, R.left)
        return R

Insert via split + merge: split the tree at the new key, create a single-node treap for the new entry, merge them in order.

Insert(t, k, p):
    new_node = Node(k, p)
    (L, R) = Split(t, k)
    return Merge(Merge(L, new_node), R)

Delete via split-on-key-twice:

Delete(t, k):
    (L, mid) = Split(t, k - 1)
    (target, R) = Split(mid, k)   # target is single node or null
    return Merge(L, R)             # discard target

Each split and merge is O(log n) expected. The split-merge interface is more flexible than rotation-based insert/delete because it allows arbitrary set operations (union, intersection, difference) and the implicit-treap extension for arrays.

5. Python Implementation

import random
from typing import Optional
 
class TreapNode:
    __slots__ = ("key", "priority", "left", "right")
    def __init__(self, key, priority):
        self.key = key
        self.priority = priority
        self.left: Optional[TreapNode] = None
        self.right: Optional[TreapNode] = None
 
# -------- Rotations --------
def rotate_right(y: TreapNode) -> TreapNode:
    """      y                x
            / \\             / \\
           x  T3   →        T1  y
          / \\                 / \\
         T1 T2               T2 T3
    """
    x = y.left
    assert x is not None
    y.left = x.right
    x.right = y
    return x
 
def rotate_left(x: TreapNode) -> TreapNode:
    """Symmetric to rotate_right."""
    y = x.right
    assert y is not None
    x.right = y.left
    y.left = x
    return y
 
# -------- Insert (rotation-based) --------
def insert(node: Optional[TreapNode], key, priority=None) -> TreapNode:
    if priority is None:
        priority = random.random()
    if node is None:
        return TreapNode(key, priority)
    if key < node.key:
        node.left = insert(node.left, key, priority)
        if node.left.priority > node.priority:
            node = rotate_right(node)
    elif key > node.key:
        node.right = insert(node.right, key, priority)
        if node.right.priority > node.priority:
            node = rotate_left(node)
    # Equal keys: silently no-op
    return node
 
# -------- Delete (rotate-down to leaf) --------
def delete(node: Optional[TreapNode], key) -> Optional[TreapNode]:
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        # Found node. Rotate it down until leaf, then cut.
        if node.left is None and node.right is None:
            return None
        if node.right is None or (node.left is not None and node.left.priority > node.right.priority):
            node = rotate_right(node)
            node.right = delete(node.right, key)
        else:
            node = rotate_left(node)
            node.left = delete(node.left, key)
    return node
 
# -------- Search (standard BST descent) --------
def search(node: Optional[TreapNode], key) -> bool:
    while node is not None:
        if key == node.key:
            return True
        node = node.left if key < node.key else node.right
    return False
 
# -------- Split + Merge interface --------
def split(node: Optional[TreapNode], key) -> tuple[Optional[TreapNode], Optional[TreapNode]]:
    """Returns (L, R) with L's keys <= key, R's keys > key."""
    if node is None:
        return (None, None)
    if node.key <= key:
        L, R = split(node.right, key)
        node.right = L
        return (node, R)
    else:
        L, R = split(node.left, key)
        node.left = R
        return (L, node)
 
def merge(L: Optional[TreapNode], R: Optional[TreapNode]) -> Optional[TreapNode]:
    """Merge two treaps where every key in L < every key in R."""
    if L is None: return R
    if R is None: return L
    if L.priority > R.priority:
        L.right = merge(L.right, R)
        return L
    else:
        R.left = merge(L, R.left)
        return R
 
# -------- In-order (sanity check) --------
def in_order(node: Optional[TreapNode]) -> list:
    if node is None: return []
    return in_order(node.left) + [node.key] + in_order(node.right)
 
# Demo
random.seed(42)
root = None
for k in [10, 20, 30, 5, 15]:
    root = insert(root, k)
assert in_order(root) == [5, 10, 15, 20, 30]
assert search(root, 15) is True
assert search(root, 99) is False
 
root = delete(root, 20)
assert in_order(root) == [5, 10, 15, 30]

Three notes on the implementation choices:

  1. Priorities are floats from random.random() here for simplicity. Production code uses integer priorities from random.randrange(2**63) to avoid floating-point comparison issues and to make priority equality vanishingly unlikely.

  2. Equal keys are silently no-op. This matches Python set semantics. To support a multiset, attach a count field to each node, or use (key, insertion_id) lex ordering as the BST key.

  3. Rotation-based and split-merge insert/delete are mathematically equivalent. The split-merge form is more flexible (supports implicit treaps, union/intersection); the rotation form is slightly faster on simple workloads because it does fewer pointer reassignments.

6. Complexity — Expected O(log n) from the Random-BST Analysis

6.1 Per-operation expected costs

OperationExpectedWorst case
SearchO(log n)O(n) (with vanishing probability)
InsertO(log n)O(n)
DeleteO(log n)O(n)
SplitO(log n)O(n)
MergeO(log n)O(n)

The “vanishing probability” of worst case: for a treap with n keys and 64-bit priorities, the probability of height exceeding c · log n for c = 5 is less than 2^{-n} for moderate n. Practically, the worst case never occurs.

6.2 Why expected height is Θ(log n) — proof sketch

The treap’s structure is determined by the priority order: insert items in priority-decreasing order into a plain BST and you get the same tree. Random priorities = random insertion order. So treap height = expected height of a random BST.

Claim: A random binary search tree built by uniformly random insertion of n distinct keys has two distinct logarithmic measures, both Θ(log n), that are easy to confuse:

  • Expected depth of a single node ≤ 2·ln n + O(1). This is the typical root-to-node path length. The derivation is a clean linearity-of-expectation argument: key j is an ancestor of key i in a random BST iff j is the first of the keys between i and j (inclusive, in sorted order) to be inserted, which happens with probability 1/(|i − j| + 1). Summing these ancestor probabilities over all j gives two copies of the harmonic series fanning out from i, yielding 2·H_n − O(1) ≈ 2·ln n (per Wikipedia’s Random binary search tree article). Converting to base-2: 2·ln n = 2·log₂ n·ln 2 ≈ 1.386·log₂ n.
  • Expected height (the longest root-to-leaf path) ≈ (1/β)·ln n ≈ 4.311·ln n, with high probability, where β is the unique number in (0,1) satisfying 2βe^(1−β) = 1 (Devroye 1986; refined by Reed 2003, “The Height of a Random Binary Search Tree”). Converting to base-2: 4.311·ln n = 4.311·log₂ n·ln 2 ≈ 2.99·log₂ n, i.e. roughly 3·log₂ n.

So the often-quoted “1.39 log₂ n” is the average node depth, while the height is about 3·log₂ n — a factor of ~2.15 larger because the longest path substantially exceeds the average. Treap insertion does at most depth(new node) rotations, so the typical insert touches ≈ 2 ln n ≈ 1.39 log₂ n levels, while the deepest possible path is bounded by the height ≈ 3 log₂ n. Both are Θ(log n); only the leading constant differs.

6.3 Why bounds are expected over priorities, not over inputs

A subtle but important point: the O(log n) bound is over the random choice of priorities, not over the choice of input keys. An adversary who picks keys adversarially still gets O(log n) expected operations, because the priorities (which control the shape) are independent of the keys. This is the adversarial robustness property — treaps are an instance of randomization defeats adversaries in algorithm design.

6.4 Variance and concentration

The height of a random BST is sharply concentrated around its mean. Reed (2003) shows the height H_n satisfies Pr(|H_n − α ln n| > t) ≤ 2 exp(−c t²/log n) for constants α, c. The probability of degeneracy (height much larger than O(log n)) is exponentially small.

6.5 Space

Each node stores: key, priority, two child pointers. For 64-bit pointers and 64-bit priorities, that is ~32 bytes per node, slightly less than Red-Black Tree’s 33+ bytes (no color bit and no parent pointer in the basic form). Total O(n).

Some implementations omit the priority field by using a hash of the key as the “priority” (deterministic). This works for sets but loses the random-input-defeating property if the adversary knows the hash function.

7. Variants and Use Cases

7.1 Implicit Treap (Indexed Treap)

The most powerful treap variant. Replace the explicit key with the node’s position in the in-order traversal — call it the “implicit key.” Then the treap behaves as an array indexed by position, with O(log n) operations including:

  • insert(i, value) — insert value at position i (shifts later elements right by 1).
  • delete(i) — remove element at position i.
  • reverse(l, r) — reverse the subarray [l..r] in O(log n). Each node has a “reverse flag” lazy bit; reverse(l, r) splits out the [l..r] subtree, flips its reverse flag, and merges back. The flag is propagated lazily on traversal — the elegance is that an entire subarray-reversal is a constant-cost flag flip plus the split/merge work.
  • range_sum(l, r), range_min(l, r), etc. with augmentation.
  • concatenate(A, B), split_at(i) — array surgery.

Implicit treaps support array operations that neither AVL nor RB trees support directly — particularly reverse in O(log n). This is why implicit treaps appear in competitive programming as “the persistent rope of choice.”

Use case: typing a text editor where users can undo, paste, rearrange paragraphs — array operations that go beyond the standard map interface. Implicit treaps give every operation O(log n) amortized.

7.2 Persistent Treap

Path-copying makes treaps persistent — each modification produces a new tree sharing structure with the old. This needs O(log n) new nodes per operation. Used in functional languages and in algorithms requiring “snapshot” semantics. The split-merge implementation is naturally persistent because split and merge each only touch the spine of the tree.

7.3 Finger Treaps

Add side pointers to support O(log d) access where d is the distance from the most recently accessed key. Useful for workloads with locality.

7.4 Treap with Custom Augmentation

Each node can carry summary information about its subtree — sum, min, max, count, GCD — and the tree supports O(log n) range queries and updates. The augmentation must be a monoidal aggregation (associative, with an identity) for the lazy-propagation approach to work cleanly.

7.5 Comparison with Other Balanced BSTs

Data structureWorst caseImplementation linesAugmentation friendlinessReverse-subarray support
AVL TreeO(log n)~150AwkwardNo
Red-Black TreeO(log n)~250AwkwardNo
Splay TreeO(log n) amortized~120FriendlyNo
Treap (explicit key)O(log n) expected~80FriendlyNo
Implicit treapO(log n) expected~120Very friendlyYes
Skip ListO(log n) expected~80MediocreNo

Treaps win on implementation simplicity (~80 lines for a complete treap, vs ~150–250 for AVL/RB) and augmentation friendliness (split-merge interface composes naturally). They lose on worst-case guarantees (only expected, not worst-case) and cache locality on huge in-memory workloads (the random shape defeats sequential prefetching).

8. Pitfalls

8.1 Forgetting to update priorities on insert

A treap node’s priority is set once at insertion. Re-randomizing on every operation defeats the analysis (the structure starts to depend on the operation history rather than just the priorities).

8.2 Using a poor random source

The expected-O(log n) bound assumes priorities are uniformly random and independent. A weak PRNG with short period (e.g., srand(0); rand() % small_max) can produce non-uniform priorities and, in the worst case, degenerate the tree. Production code uses Mersenne Twister or secrets/os.urandom-seeded RNG for safety.

8.3 Equal priorities

Two nodes with equal priorities create ambiguity in the heap invariant (which becomes the parent?). This violates the existence-uniqueness guarantee (§2.1). Mitigation: 64-bit priorities make collisions vanishingly unlikely (n²/2^64 ≈ 5×10⁻⁸ for n = 10⁶); for paranoid safety, attach a tiebreaker like (priority, insertion_id).

8.4 Mixing rotation-based and split-merge implementations

Don’t use rotations and split/merge in the same code base unless you understand both interfaces. They are equivalent but the split/merge form encourages a recursive style that interacts differently with augmentation lazy-propagation than the rotation-based form.

8.5 Not handling Python recursion depth

A treap’s expected height is ~3 log₂ n, so for n = 10^7 the recursion depth is ~70 — well within Python’s default 1000. But for worst-case paths (a tail event), recursion could exceed limit. sys.setrecursionlimit(10**6) for safety, or rewrite iteratively.

8.6 Treating treap as worst-case O(log n)

Don’t quote “treap is O(log n)” without specifying “expected.” Some interviewers will ding the candidate who confuses expected-time and worst-case-time. The correct phrasing: “Treap is O(log n) expected, with vanishing-probability worst case.”

8.7 Implicit treap: forgetting to push lazy flags on traversal

Implicit treaps with lazy operations (reverse, range-add) need a push_down step before any access to children — otherwise stale lazy flags corrupt the answer. This is the implicit-treap analog of the “forgot to push lazy in segment tree” bug. Easy to miss; hard to debug.

8.8 Using a deterministic priority function for security-sensitive workloads

If priorities are a hash of the key (priority = hash(key)), an adversary who knows the hash function can construct keys whose hashed priorities form an adversarial sequence, defeating the random-BST analysis. For internet-facing applications (e.g., a server using treaps for an in-memory cache), priorities should be from secrets/os.urandom, not from a deterministic hash.

9. Diagram — Treap with Random Priorities

flowchart TD
    A["(key=5, prio=90)"]
    B["(key=20, prio=70)"]
    C["(key=15, prio=60)"]
    D["(key=30, prio=30)"]
    E["(key=10, prio=45)"]
    A -->|right| B
    B -->|left| C
    B -->|right| D
    C -->|left| E

What this diagram shows. The final 5-node treap from the §3 worked example, with pairs (10,45), (20,70), (30,30), (5,90), (15,60). The tree simultaneously satisfies BST order on keys (in-order traversal 5, 10, 15, 20, 30 is sorted) and max-heap order on priorities (root has priority 90, the maximum; every parent priority exceeds its children’s: 90 > 70, 70 > 60, 70 > 30, 60 > 45). The root is the highest-priority node — key=5 — not the median key, which is why the tree leans right. The shape is a deterministic function of the (key, priority) pairs — given these five pairs, no other binary tree satisfies both invariants. The randomness in priorities is what makes the expected shape balanced; if priorities had instead been assigned in BST-insertion order, the tree could have degenerated into a chain. Notice that key=10 ends up the deepest node despite being neither the smallest nor largest key: its low priority (45) sinks it, illustrating that BST structure is set by keys but depth is governed by each node’s priority rank.

10. Common Interview Problems

SourceProblemTreap usage
Codeforces / IOI”Find the k-th smallest element”Augmented treap with subtree-size counts
Codeforces 702F”T-shirts” — order-statistic operationsTreap with sum-of-prices augmentation
Codeforces 863D”Range reversals”Implicit treap with reverse flag
Codeforces / ICPC”Persistent ordered set”Path-copying treap
LC 1825Finding MK AverageOrder-statistic data structure (treap or Skip List)
LC 220Contains Duplicate IIISliding-window sorted set
Generic”Implement a self-balancing BST in 50 lines”Treap

For interview coding problems, treaps are rarely the expected solution at FAANG-style interviews — those usually expect AVL Tree, Red-Black Tree, or simply TreeMap/std::set. Treaps shine in competitive programming contests where the implementation budget is tight and the augmentations are unusual (reverse subarrays, persistent versions). Knowing the structure exists and what its trade-offs are (simpler than AVL/RB, expected-time only, supports implicit form for arrays) is enough for most interviews.

11. Open Questions

  • How does cache locality of treaps compare to AVL/RB on modern memory hierarchies? The random shape should be worse for sequential prefetching, but micro-benchmarks rarely show large differences in practice.
  • The expected-height constant is settled (resolved in §6.2): height ≈ 4.311·ln n ≈ 3·log₂ n (Devroye 1986, Reed 2003), where 4.311 = 1/β with 2βe^(1−β) = 1; average node depth is ≈ 2·ln n ≈ 1.39·log₂ n. Open: whether finer second-order terms / variance constants have been tightened beyond Reed (2003).
  • Are there hybrid treap-skip-list structures that combine the simplicity of both? Some experimental work on “biased skip lists” and “fingered treaps” suggests yes; production adoption is limited.

12. See Also

Graph View

Backlinks