Treap

A randomized balanced BST that couples binary-search-tree keys with heap-ordered random priorities for expected logarithmic height.

Tree plus heap

A treap gives each node a key and a random priority. It is a binary search tree with respect to keys and a heap with respect to priorities. Because the priorities are random, the tree's shape is the same as a random BST built by inserting keys in priority order, so its expected height is O(log n) with no explicit balancing rules.

Rotations keep both orders

Kronos motion — classical

On insertion the node is placed by key like an ordinary BST, then rotated upward while its priority violates the heap order; deletion rotates the node down to a leaf and removes it. Each operation performs O(log n) expected rotations. The randomness, not the input, controls balance, so adversarial key orders cannot degrade performance in expectation.

Split and merge

python

def split(t, key):
    if t is None:
        return (None, None)
    if t.key < key:
        l, r = split(t.right, key)
        t.right = l
        return (t, r)
    else:
        l, r = split(t.left, key)
        t.left = r
        return (l, t)

Implicit treaps

Keying a treap by subtree size instead of value gives an implicit treap, an array that supports insert, erase, reverse, and range operations at any position in O(log n). This makes it a flexible alternative to a balanced BST for sequence manipulation, similar in power to a rope.

Why use it

Split and merge are natural primitives, simplifying range and persistence operations.
Simpler code than red-black trees with comparable expected bounds.
Randomization, like in a skip list, sidesteps deterministic rebalancing cases.