Treaps are a non-deterministic data structure in the form of a Cartesian tree used to maintain a balanced binary search tree. As opposed to most other balanced binary search trees like scapegoat tree, red-black tree, avl tree, fenwick tree etc., the treap data structure does not guarantee balance per se, but it ensures so with a very high probability.
Treaps are Cartesian trees, which means that they are trees with an ordered pair and that the nodes follow the binary search tree property with respect to one of them and the heap property with respect to the other.
This means that the treap is composed of nodes, each of which is a pair , called the priority and the key, respectively, where for every node
Given a set of pairs, there exists a unique Cartesian tree made by them.
If the list of pairs is empty, then we construct the empty tree and we're done.
Otherwise, we pick the root node as the pair with the highest priority and recursively build the left subtree with all the pairs whose keys are less than (or equal to) that of the root and the right subtree with all the pairs whose keys are greater than that of the root.
Treaps are Cartesian trees where the priorities are chosen at random from a large range of integers.
We do not prove this here, but it is intuitively obvious that the expected height of the treap is in
Thus, each node of the treap consists of a value, a priority, and pointers towards its two children (which may be null).
We'll build the tree by inserting an element one by one. Let us look at our first strategy to do this.
Insert blindly only using the binary search tree property. Using a random value as the priority, rotate the node up to the appropriate location.
We do not define rotations formally here but illustrate with a graphic:
Notice that the BST invariant remains intact under this operation.