After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.

The treap was first described by Raimund Seidel and Cecilia R. Aragon in 1989;[1][2] its name is a portmanteau of tree and heap.

An equivalent way of describing the treap is that it could be formed by inserting the nodes highest priority-first into a binary search tree without doing any rebalancing.

Therefore, if the priorities are independent random numbers (from a distribution over a large enough space of possible priorities to ensure that two nodes are very unlikely to have the same priority) then the shape of a treap has the same probability distribution as the shape of a random binary search tree, a search tree formed by inserting the nodes without rebalancing in a randomly chosen insertion order.

Because random binary search trees are known to have logarithmic height with high probability, the same is true for treaps.

This mirrors the binary search tree argument that quicksort runs in expected

Naor and Nissim[3] describe an application in maintaining authorization certificates in public-key cryptosystems.

This technique can be used to enhance the merge algorithms to perform fast also when the difference between two sets is small.

Rather than storing random priorities on each node, the randomized binary search tree stores a small integer at each node, the number of its descendants (counting itself as one); these numbers may be maintained during tree rotation operations at only a constant additional amount of time per rotation.

The numbers of descendants are used by the algorithm to calculate the necessary probabilities for the random choices at each step.

Placing x at the root of a subtree may be performed either as in the treap by inserting it at a leaf and then rotating it upwards, or by an alternative algorithm described by Martínez and Roura that splits the subtree into two pieces to be used as the left and right children of the new node.

If the left or right subtree of the node to be deleted is empty, the join operation is trivial; otherwise, the left or right child of the deleted node is selected as the new subtree root with probability proportional to its number of descendants, and the join proceeds recursively.

A minor technical difference is that, in a treap, there is a small probability of a collision (two keys getting the same priority), and in both cases, there will be statistical differences between a true random number generator and the pseudo-random number generator typically used on digital computers.

is a simple variation of an ordinary treap which can be viewed as a dynamic array that supports the following operations in

: The idea behind an implicit treap is to use the array index as a key, but to not store it explicitly.

The join algorithm for an implicit treap is as follows:[8] The split algorithm for an implicit treap is as follows:[8] To insert an element at position pos we divide the array into two subsections [0...pos-1] and [pos..sz] by calling the split function and we get two trees