You load yesterday’s order IDs from a CSV. They come out sorted. You insert them into a binary search tree because “search is O(log n).” After a million rows, every lookup walks a million nodes. The key order is honest. The height is a spine.

A treap keeps that same key order and adds a second number per node: a random priority. Search still walks left and right by key. Rotations then restore heap order on those priorities, so a sorted insert sequence does not get to pick the shape. The tree is a BST on keys and a heap on priorities. Height is O(log n) in expectation — not because you painted nodes red and black, but because a random heap order is a random binary tree.

Terms this series will not re-teach (height vs log n, expected vs worst-case, how to read a complexity table) live on the Data Structures Roadmap. This post is one layout: two invariants, a node with a priority, insert-and-rotate, and split/merge as the other face of the same machine.

Two laws on one node

A binary search tree says where keys sit. A heap says which node may be a parent. A treap enforces both at once:

BST (keys):       left subtree < node.key < right subtree
Heap (priority):  parent.priority >= child.priority   (max-heap)

The key law is the same walk you already know: smaller left, larger right. The priority law is not a complete array-heap. There is no “fill left to right.” Priorities only decide who sits above whom. Given a set of (key, priority) pairs, there is exactly one tree that satisfies both laws — a Cartesian tree. Randomize the priorities and that unique tree is a random BST.

A node is two child pointers, a key, and a priority. A value field can ride along; it does not change either walk:

final class Node {
    int key;
    int priority;
    Node left;
    Node right;

    Node(int key, int priority) {
        this.key = key;
        this.priority = priority;
    }
}

Pick the priority at construction, once, from a random source (ThreadLocalRandom.current().nextInt() is enough). Do not derive it from the key. If priority is a function of the key, sorted inserts can still force a spine.

Four keys with random priorities:

key        1    2    3    4
priority  40   90   20   70

      2 (90)
     / \
  1(40)  4(70)
        /
      3(20)

Key order is 1, 2, 3, 4 — inorder is still sorted. Heap order puts 2 at the root because 90 wins. A plain BST given the same keys in order 1, 2, 3, 4 would have been a right spine. The priorities, not the insert sequence, chose the shape.

Note: Duplicates need a policy, the same as any BST: reject, overwrite a value, or park equals on one side. The snippets below treat equals as “already present.”

Rotations restore heap order without breaking keys

A rotation is a local rewrite of three pointers. It preserves BST order: every key that was left of a node stays left of it. It changes who is the parent, which is exactly how you fix a heap violation.

Right rotate when the left child has a higher priority than the node. Left rotate is the mirror:

right rotate at y              left rotate at x

      y                              x
     / \                            / \
    x   C         <==>             A   y
   / \                                / \
  A   B                              B   C

In Java the rewrite is three assignments and a returned new subtree root:

Node rotateRight(Node y) {
    Node x = y.left;
    y.left = x.right;
    x.right = y;
    return x;
}

Node rotateLeft(Node x) {
    Node y = x.right;
    x.right = y.left;
    y.left = x;
    return y;
}

After rotateRight(y), x is the parent. BST order is unchanged (A < x < B < y < C). Heap order now has the higher priority on top — if that is why you rotated. There are no color bits, no height field, no “black-height.” The only extra word on the node is the priority you already stored.

Insert: hang by key, rotate by priority

Insert is BST insert, then a walk back toward the root that restores the heap. Recursion makes the reattachment obvious: the caller stores the returned child, and a rotation may change which node that child is.

Node insert(Node node, int key) {
    if (node == null) {
        return new Node(key, ThreadLocalRandom.current().nextInt());
    }
    if (key < node.key) {
        node.left = insert(node.left, key);
        if (node.left.priority > node.priority) {
            node = rotateRight(node);
        }
    } else if (key > node.key) {
        node.right = insert(node.right, key);
        if (node.right.priority > node.priority) {
            node = rotateLeft(node);
        }
    }
    return node;
}

Search is the BST walk and ignores priority: equal — found; smaller — left; larger — right. Priority never changes which branch is legal. It only changes how bushy that path is.

Delete is the inverse: rotate the target down toward the child with the larger priority until it is a leaf, then drop it. Each rotation preserves BST order; the heap law decides which child rises. You can also delete with split and merge, below — same tree, different API.

Expected cost is O(log n) because a random priority makes a random BST, and a random BST’s height is logarithmic with high probability. That is not a worst-case bound on the next call. It is a randomized one: a bad draw of priorities can still make a tall tree. The chance falls off fast as n grows. From the roadmap: expected is not a law of physics on this one lookup.

Split and merge: the other face

Insert-and-rotate is one interface. The other is two operations that treat the treap as a ordered bag you can cut and glue.

Split by a key k returns two treaps: every key < k, and every key ≥ k. Both remain valid treaps.

Merge takes two treaps where every key on the left is smaller than every key on the right, and glues them. Heap order at the two roots decides who becomes the parent; the other root hangs on the open side.

record Split(Node less, Node greaterOrEqual) {}

Split split(Node node, int key) {
    if (node == null) {
        return new Split(null, null);
    }
    if (node.key < key) {
        Split s = split(node.right, key);
        node.right = s.less();
        return new Split(node, s.greaterOrEqual());
    }
    Split s = split(node.left, key);
    node.left = s.greaterOrEqual();
    return new Split(s.less(), node);
}

Node merge(Node left, Node right) {
    if (left == null) {
        return right;
    }
    if (right == null) {
        return left;
    }
    if (left.priority > right.priority) {
        left.right = merge(left.right, right);
        return left;
    }
    right.left = merge(left, right.left);
    return right;
}

Insert of k is then: split on k, hang a new node in the gap, merge the three pieces. Delete of k is: split on k, split the right piece on k + 1 (or a strict upper bound), throw away the middle, merge the outer two. You did not invent a second structure. You named the cuts that rotations were already doing.

Note: merge is only legal when the key ranges do not overlap. Merging two arbitrary treaps would break the BST law. Split is how you make two ranges that do not overlap.

An implicit treap uses position (the size of the left subtree) as the BST key so you can split a sequence at index i. Same rotations, different meaning of “key.” This post stays on explicit keys.

Java has no java.util.Treap

There is no treap in the JDK. TreeMap and TreeSet are red-black trees: they keep the BST invariant and rebalance with color bits so height stays Θ(log n) even if you insert sorted keys, with a deterministic worst case. If you needed an ordered map in production Java, you already had one, and it is not the class above.

NavigableMap<Integer, String> orders = new TreeMap<>();
orders.put(42, "paid");
orders.put(7, "pending");
orders.put(19, "packed");
// iteration is 7, 19, 42 — sorted keys, guaranteed log n per mutate

Reach for TreeMap when you need ordered keys (range views, firstKey / lastKey, successor). Reach for HashMap when you need a key and do not care about order. Rolling your own treap is for learning the two-invariant trick, for a split/merge API a red-black tree does not expose as primitives, or for an implicit sequence you cannot buy off the shelf. It is not the default sorted map.

When not to use a treap

Skip a treap when:

  • You needed a JDK sorted map. TreeMap / TreeSet are red-black, tested, and already on the classpath. A hand-rolled Node is not a substitute for that type.
  • You need a deterministic worst-case log n. Red-black (and AVL) guarantee height on every call, not in expectation. Real-time bounds, adversarial keys plus a visible RNG, or a codebase that will not accept “almost surely log n” all want a balancer with an explicit invariant, not a random priority.
  • You do not need order. Lookup-only uniqueness is a hash table’s job. Two extra words per node (left, right) plus comparisons are a tax you are not spending.
  • n is tiny. A list and a linear scan will beat a tree of twenty objects. Measure before you celebrate expected log n.

Use a treap when you want BST order and a balancer that is “draw a priority, rotate” — or when split and merge are the API (cut a ordered set at k, glue two ordered ranges). If the sentence is “I need a sorted map in Java,” you wanted TreeMap. If the sentence is “I need a height cap that cannot depend on a random draw,” you wanted red-black.

How to read the bill

Same shopping-list reading as the roadmap: pick the structure for the operation on the hot path.

Structure: treap (randomized BST)
search     expected O(log n)  — BST walk; priority ignored
insert     expected O(log n)  — BST insert + rotations up
delete     expected O(log n)  — rotate down, or split + merge
split      expected O(log n)  — cut into < k and ≥ k
merge      expected O(log n)  — glue when ranges do not overlap
inorder    O(n)               — still sorted keys
space      O(n)               — two child pointers + a priority per key

Write expected until a deterministic balancer is in the picture. A treap quotes the same log n a random BST earns, not the Θ(log n) a red-black tree proves.

Cheat sheet

Invariants: BST on keys AND heap on priorities (one unique tree)
Priority:   random, assigned once; not a function of the key
Balance:    expected O(log n); no color bits, no height field
Insert:     BST hang, rotate up while child.priority > parent.priority
Delete:     rotate down to a leaf, or split + drop + merge
Split:      < k  |  ≥ k   (both valid treaps)
Merge:      glue only if all left keys < all right keys
JDK:        no java.util.Treap; TreeMap / TreeSet are red-black
Skip:       need TreeMap; need deterministic worst-case; no order (hash)

Do:

  • Name both laws: key order and heap order. One without the other is a different structure.
  • Assign priorities from a random source, once, at insert.
  • Use TreeMap when production Java needs sorted keys.

Don’t:

  • Quote worst-case O(log n) on a treap. The bound is expected.
  • Derive priority from the key and call the tree randomized.
  • Hand-roll a treap because the name is on a slide when TreeMap already does the job.

Wrap-up

A treap is two honest structures occupying one node: a BST on keys so search and inorder still work, and a heap on random priorities so the shape is a random tree instead of a function of insert order. Rotations restore the heap without touching key order. Insert-and-rotate and split/merge are the same machine with different verbs.

In Java, the production type with the sorted map job is TreeMap (red-black), not a hand-rolled treap. If you do not need order, you did not need a tree. If you need order and a height guarantee that does not depend on a random draw, you needed a deterministic balancer.

For the glossary behind height, expected vs worst-case, and “what operation is hot,” stay on the Data Structures Roadmap.

Next optional step in the series Split the plane so range queries skip whole regions. Quadtrees and k-d Trees