Reading Time: 5 minutes

Pre-requisites: Binary Search Tree & Binary Heap.

What is a Treap?

Self Balancing BST(aka Randomized BST)

Why Treap?

  • Easy to code.
  • It can be extended to be used as other trees like interval trees (segment tree, Fenwick tree), etc.
  • You can use it as a dynamic array that supports all the operations like insert, search, delete, partition, etc in probabilistic O(log N) time complexity.

Brief

treap
  • Treap = Tree + Heap
  • A Treap is just a binary tree on a sequence of pairs that is heap-ordered on one of the elements of each pair and BST-ordered on the other element
  • If we assign random values to each heap-ordered element, then the expected height of the resulting tree is O(logN). This is the entire idea behind Treap.
  • As you can see above tree satisfy both properties:
    1) Key follows standard BST ordering
    2) Priority follows Max-Heap property.
  • I am not going to prove O(log N) time complexity, you can find it in the research paper here. Rather we directly jump to its implementation.

Till here, we just see jargon, here on you will see some real stuff.

Implementation

  • You may get thought about this is going to be a very complex data structure as we have to maintain both BST & Heap property at a time. But you are wrong this is easiest to code & understand(not at first cite), just stay with me.
  • Treap supports two basic, easy & powerful operations which are the backbone of the whole treap data structure: 1. Split & 2. Merge.

Split

split operation treap
  • split(T,X) : It splits a given treap T into two different treap L and R such that L contains all the nodes with Key < X and R contains all the nodes with Key > X. The original treap T is destroyed/doesn’t exist anymore after the split operation.
  • As you can see we have tree rooted with Key X having left subtree rooted with Y(with all value lesser than X) & right subtree rooted with Z(with all value greater than X).

if key >= X

  • Call the split function for Z & attach the root of L’ returned by this split as the right child of X such that Treap invariant of ‘L’ is maintained (How?).
  • L’ will still be heap ordered coz priority of all elements in Z is < X.
  • L’ will still be BST ordered coz all elements in Z > X.
  • And the recur same thing for R’ returned by a split of Z until one of subtree becomes NULL.

else if key < X

  • Call the split function for Y and attach the root of R’ returned by split as the left child of X such that treap invariant is maintained for ‘R’.
  • And the same thing will be done for L’ returned by a split of Y.
  • We the recur same thing for L’ until one of subtree becomes NULL.

Merge

merge operation treap
  • merge(L,R) : The merge operation merges two given treap L and R into a single treap T. And L & R are destroyed after the operation. A very important assumption of the merge operation is that the largest value of L is less than the smallest value of R (where value refers to the BST Key values of the particular node).
  • As you can see we have two trees rooted with Key Y & Z. We have to merge these trees to form a single tree that maintains BST & Heap invariant.

if priority(Y) > priority(Z)

  • We just simply merge Y’s right subtree with Z & attach it as a right subtree of Y.
  • We the recur same thing on this merge operation until one of the subtrees becomes NULL.

else if priority(Y) < priority(Z)

  • We just simply merge Z’s left subtree with Y & attach it as a left subtree of Z.
  • We the recur same thing on this merge operation until one of the subtrees becomes NULL.

Just take a look at following code snippet you will get the better picture of above operations

typedef struct node{
    int val,prior,size;
    struct node *l,*r;
}node;
typedef node* pnode;
int sz(pnode t){
    return t?t->size:0;
}
void upd_sz(pnode t){
    if(t) t->size = sz(t->l)+1+sz(t->r);
}
void split(pnode t,pnode &l,pnode &r,int key){
    if(!t) l=r=NULL;
    else if(t->val<=key) split(t->r,t->r,r,key),l=t;
    else split(t->l,l,t->l,key),r=t;    
    upd_sz(t);
}
void merge(pnode &t,pnode l,pnode r){
    if(!l || !r) t=l?l:r;
    else if(l->prior > r->prior)merge(l->r,l->r,r),t=l;
    else merge(r->l,l,r->l),t=r;
    upd_sz(t);
}

At first cite this code looks complex, but  don’t give up, its yet simple. Just go through an imagination picture of treap & simulate the code.

insert(X)

  • To insert a value X into our BST, we first chose a Y = rand() , such that (X,Y) represents the new node to be inserted in the treap.
  • Then, keep on going down the tree like a simple BST searching for the correct pos where X should be inserted unless either the correct position is found OR we encounter the first node E such that priority(E) < Y.
  • Here, call split(E, X) and attach L and R as left and right subtrees of node (X, Y).

erase(X)

  • Go down the tree like a BST unless node to be deleted is found. If the node is found, call merge function for it’s left and right subtrees and attach the resulting tree to the parent of the node to be deleted.

find(X)

  • Same as simple BST.

See the following code for a clear understanding.

void insert(pnode &t,pnode it){
    if(!t) t=it;    
    else if(it->prior>t->prior) split(t,it->l,it->r,it->val),t=it;
    else insert(t->val<=it->val?t->r:t->l,it);
    upd_sz(t);
}
void erase(pnode &t,int key){
    if(!t)return;
    else if(t->val==key){pnode temp=t;merge(t,t->l,t->r);free(temp);}    
    else erase(t->val<key?t->r:t->l,key);
    upd_sz(t);
}
pnode init(int val){
    pnode ret = (pnode)malloc(sizeof(node));
    ret->val=val;ret->size=1;ret->prior=rand();ret->l=ret->r=NULL;
    return ret;
}

This covers the basic introduction to treaps & their implementation as  Balanced Binary Search Trees. But there’s far more to treaps than just Balanced Binary Search Trees. For eg :

  • A variant of treaps called Implicit Treaps can be used to perform all the operations which interval trees like segment tree and Fenwick tree can (including lazy propagation :D).
  • The idea of sparse segment tree & sparse Fenwick tree to handle very large ranges and limited queries can also be extended to treap resulting in a variant called sparse implicit treap.
  • Treap also make a good persistent BST mainly because of their simplicity to code and a constant average number of operations upon insert/delete.
  • Treap can also be extended to multiple dimensions in the form of quadtrees¬†which are a balanced variant of a quadtree data structure.

Sources

  1. Tanuj Khattar
  2. http://e-maxx.ru/algo/treap
  3. Wikipedia
  4. geeksforgeeks
Awesome
Awesome Interesting Useful Cool Boring Sucks