Treaps

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 \(n\) nodes, each of which is a pair \((H_i, B_i)\), called the priority and the key, respectively, where for every node \(i\)

• \(H_{\text{left}(i)} \leq H_i \geq H_{\text{right}(i)}\) and
• \(B_{\text{left}(i)} \leq B_i \leq B_{\text{right}(i)}.\)

A Cartesian tree with numbers as priorities and characters as keys

Given a set of \((H_i, B_i)\) 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. \(_\square\)

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 \(O(\log n).\)

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.