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 do need to re-balance that tree (which takes O(n) time).
So for a while, computer scientists used to use 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 – for e.g, the splay trees moves the more accessed elements closer to the top and re-balances – 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 are basically just binary trees with a “heap” property. (A max heap is basically when all parents in the tree have keys of values that are greater than or equal to its children’s keys). This 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 an added 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 a 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). So 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!).
Now to make that second key a little more useful for us, we use a random heap weight. So now, the structure (shape) of the tree will depend entirely on the randomized weight we gave the heap values. By making sure we assign these randomly (one way is by hashing the keys themselves), we get randomized heap priorities.
To insert a new key, we generate the priority and do a regular BST insertion and then rotate it up the tree (to maintain the heap). To delete a key, we 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’s a tree with regards to the keys and a heap with regards 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 a good platform to build a randomized binary search tree.
Why is it remarkable?
- It’s a self-organizing data structure, as explained above. They look after themselves, without the need to be managed. Only, unlike other self balancing trees, they don’t need complex algorithms (simple tree rotations will suffice, although there are simpler algorithms involving arrays that can do the job too).
- It is also a randomized data structure.
- It’s a binary search tree essentially, so to print a sorted order of keys, just traverse it in order like we would regular BSTs. Searching a Treap is like searching a tree.
- 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).
- A Treap basically combines probability, randomization, two popular CS data structures, etc to make a highly useful 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
Thanks for reading.