Treap Data Structure

A Treap data structure is basically a combination of a binary search tree and a heap.

Binary Search Trees

Deletions and additions of nodes can make the tree unbalanced (heavier on sides; therefore, the property we value about BSTs, the ability to distribute data by equal divisions, goes out of whack). Therefore, we need to rebalance that tree (which takes O(n) time for a tree containing n elements).

For a while, computer scientists used balanced search trees, which incorporated rotation algorithms to keep it balanced after adding and removing nodes – like red–black trees, splay trees, AVL trees, etc.

These were combined with some optimizations – e.g., the splay trees move the more accessed elements closer to the top and rebalances – B–trees store more information per node than just one element. All these add complexity to the algorithm at the pretext of offering the advantages of a normal BST.

Heaps

Heaps are basically just a binary tree with a “heap” property. (A max-heap is basically when all parents in the tree have keys of greater values than or equal to its children’s keys). This property is why it makes a nice data structure to implement priority queues (if we remove one element, we need to choose from 2 children to find out who takes the removed elements’ place). Heaps can be logically stored in arrays, which is a bonus (random access times).

Treap Data Structure

A treap data structure combines the best of both heaps and binary search trees. When we construct a heap, we basically build an ordered binary tree AND make it satisfy the “heap” property. However, if done with a single element, it will look like a line (because in the BST, the left child must be less than its parent and the right child must be greater than or equal to its parent, but for a heap, each parent should either be all bigger than its children or all smaller than its children). Therefore, we introduce another key (See picture).

The numbers indicate the heap arrangement of the data structure (arranged in max-heap order), and the alphabets indicate the tree part of things (left child < parent <= right child). So now we have a tree and a heap.

Now, here’s the magical property about treap data structure. There is only one arrangement for this treap regardless of the order by which elements were picked to construct the tree (try it!).

To make that second key a little more useful for us, use a random heap weight. So now, the tree’s structure (shape) will depend entirely on the randomized weight we gave the heap values. We get randomized heap priorities by making sure we assign these randomly (one way is by hashing the keys themselves).

To insert a new key, generate the priority and do a regular BST insertion, and then rotate it up the tree (to maintain the heap). To delete a key, make its weight infinite and rotate it down the tree (again, in heap order) until it becomes a leaf, and then remove it.

So, it is a tree with regard to the keys and a heap with regard to the priorities. The idea behind that is, there is a high probability that re-heapifying the tree will keep it balanced (height will be c.log(n)) since a random binary search tree has logarithmic height.

A treap is, therefore, an excellent data structure to build a randomized binary search tree.

Why is it remarkable?

1. It is a self-organizing data structure, as explained above. They look after themselves, without the need to be managed. Unlike other self-balancing trees, they don’t need complex algorithms (simple tree rotations will suffice, although simpler algorithms involving arrays can do the job too).
2. It is also a randomized data structure.
3. It is a binary search tree essentially, so to print a sorted order of keys, traverse it in order like we would regular BSTs. Searching a treap is like searching a tree.
4. Regardless of the order of how we add, delete, etc., because of the randomized weights, there is a high probability that the tree will be balanced (a random binary search tree has logarithmic height).
5. A treap basically combines probability, randomization, two popular CS data structures, etc., to make a beneficial data structure. From a CS student’s point of view, try to learn about treaps first, and we get to learn BSTs, traversals, hashing, tree rotations, heaps, recursion, sorting, etc., all in one go.

Author: KK Nair