Treaps - an introduction

So what are treaps?

Technically speaking, we can define Treaps at a surface level as :-

• Treap = Tree + Heap

• Tree , which one ? Binary Tree ? N-ary Tree ? any other 'special' kind of Tree?

• Here the tree is a special kind of Binary Tree, it is infact a Binary Search Tree

• Heap is the simple binary heap we study in basic data structures based on some sort of priority. Most likely, it is a min-heap or max-heap

Why are we even bothered about such a data structure, what is the intuition and motivation behind Treaps?

• The answer is 'Randomness' - the law or the nature, of nature .

• Consider an array A : [1,3,5,6,9]

• Lets construct a BST out of ths array, we have

Now, the question is which will be in majority, skewed BSTs or more balanced BSTs?

• The balanced ones will be in majority, i.e., out of all the 5! permutations, mojority will form a more balanced kind of BST

• So, we can say given an array, a random permute of the array is more likely to generate a BST of height O(logn) if we insert the nodes in the order of the permute.

• Whats the benefit? Random permute is easy, no complex stuff, high chances of resulting a balanced BST, which in turn gives search time complexity of O(logn) with very high probability

Now, where are the Treaps, this is not what we started with?Here's the answer to this :

What if the situation is online instead of offline?

This means if we get values to be inserted in the BST on the go, instead of all at begining, we cannot do random permute in such a scenario.

Here we will use the heap property we introduced earlier, so lets say we have a max heap.

• Our node has two values : key, priority

• Key is used to maintain BST, and priority is used to maintain max-heap

• We get only values, i.e., keys on the go, we randomnly generate a priority value for that node.

• Then we insert the node using key in our Treap such as to satisfy the BST property, i.e., we perform the normal BST insertion.

• Then we check if the heap property is satisfied or not, if the heap property is not satisfied, we perform rotations to make sure that the heap property is satisfied.

Such a thing has a high property that we maintain an almost balanced BST all the time, but remember its just a chance game, although the probability here is very high.

If you are curious how about high is the probabilty? 

• For a Treap with 10,000 nodes, the probability that the height of the tree will be greater than 100 is 1 in 2.5 billion

Note : There are other data structures such as Red Black Trees and AVL Trees for maintaining balanced BST. They do not use randomness and they guarantee that tree is a Balanced Binary Search Tree. They are more complex than Treaps.