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
Example of a Treap
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
But what if we randomly permute the array, we have some random permutes as:
p1 : [1,5,6,3,9]
p2 : [5,6,3,1,9]
and many more, infact total 5! = 120 permutations are possible
Let us make BST if the order is p2, 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.
