# My Weblog

## Treap data structure

Treap is data structure which use property of binary search tree and heap. According to wiki ” the treap and the randomized binary search tree are two closely-related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform ” .You can also have a look here.

```import Data.List
import System.Random
import Data.Bits

data Treap a = T Integer a ( Treap a ) ( Treap a ) | NIL deriving (Show , Eq , Ord )

searcH::(Ord a) => Treap a -> a -> Maybe a
searcH NIL a' = Nothing
searcH ( T p a l r ) a'
| a' < a = searcH l a'
| a' > a = searcH r a'
| otherwise = Just a'

prioritY::Treap a -> Integer
prioritY NIL = 0
prioritY ( T p _ _ _ ) = p

--clockwise rotation
rotateC::Treap a -> Treap a
rotateC ( T p a ( T p' a' x_l y_l ) y ) = T  p' a' x_l ( T p a y_l y )
rotateC ( T p a x y ) = T p a x y

--Anticlockwise rotation
rotateA::Treap a -> Treap a
rotateA ( T p a x ( T p' a' x_r y_r ) ) = T p' a' ( T p a x x_r ) y_r
rotateA ( T p a x y ) = T p a x y

balancE::Treap a -> Treap a
balancE t@( T p a x y )
| p < prioritY x = rotateC t
| p < prioritY y = rotateA t
| otherwise = t

inserT::(Ord a ) => ( Integer , a ) -> Treap a -> Treap a
inserT ( p' , a' ) NIL = T p' a' NIL NIL
inserT ( p' , a' ) ( T p a x y )
| a' <= a =  balancE \$ T p a ( inserT ( p' , a' ) x ) y
| otherwise = balancE \$ T p a x ( inserT ( p' , a' ) y )

--Elegant deletion algorithm http://infoarena.ro/treapuri
deletE::( Ord a ) => Treap a -> a -> Treap a
deletE NIL _ = NIL
deletE t@( T p a x y ) a'
| a' < a =  T p a ( deletE x a' ) y
| a' > a =  T p a x ( deletE y a' )
| otherwise = if x == NIL && y == NIL then NIL else if prioritY x > prioritY y then deletE ( rotateC t ) a' else deletE ( rotateA t  ) a'

getH::Treap a -> Integer
getH NIL = 0
getH ( T p a x y ) = 1 + max ( getH x ) ( getH y )

spliT::( Ord a ) => Treap a -> a -> ( Treap a , Treap a )
spliT NIL _ = ( NIL , NIL )
spliT t key = ( x , y ) where
T p a x y  = inserT ( ( shiftL ( 1::Integer ) 100 ) , key ) t

{-- Merging two treaps (assumed to be the product of a former split), one can safely assume that the greatest value in the first treap is less than the smallest value in the second treap. Insert a value x, such that x is larger than this max-value in the first treap, and smaller than the min-value in the second treap, and assign it the minimum priority.What if x is equal ? This program gets into infinity loop when x is present in one of the two subtree . Try testing on 1 2 3 4 5 6 7 8 9 10 and split it on key 5 and merge it on key 5 --}

joiN::( Ord a ) => Treap a -> Treap a -> a -> Treap a
joiN NIL NIL _ = NIL
joiN NIL t _ = t
joiN t NIL _ = t
joiN t_1 t_2 key = t where
t' =  T 0 key t_1 t_2
t = deletE t' key

rInt:: String -> Integer

main::IO ( )
main = do
l <- fmap ( map rInt.words )  getLine
--l <- replicateM n . randomRIO \$ ( 1::Integer, 20::Integer )
m <- replicateM ( length l ) . randomRIO \$ ( 1::Integer, shiftL (1::Integer ) 64 )
let list = zip m l
treap = foldr inserT NIL list
print treap
putStrLn "Height of treap "
print \$ getH treap
putStrLn " input the key to split "
let ( p , q ) = spliT treap  n
print p
print q
putStrLn "merging the two treaps "
print \$ joiN p q n
return ()
```

The same algorithm in C. Pointers are messy than pattern in Haskell.

```#include<cstdio>
#include<iostream>
#include<vector>
#include<cstdlib>
#include<climits>
#define INFINITY INT_MAX
using namespace std;

struct treap
{
int key,prio;
struct treap *L,*R;
treap(){}
treap(int key,int prio,struct treap *L,struct treap *R)
{
this->key=key;
this->prio=prio;
this->L=L;
this->R=R;
}
};

void print(struct treap *node,int lev)
{
if(node == NULL ) return;
cout<<"lev= "<<lev<<" node= "<<node->key<<" priority = "<< node->prio<<endl;
print(node->L,lev+1);
print(node->R,lev+1);

}

bool search(struct treap *node ,int key)
{
if(node == NULL) return false;
if(node->key == key ) return true;
if(key<node->key) return search(node->L,key);
else return search(node->R,key);
}

//clock wise rotation or right rotation
void rotate_C(struct treap **node)
{
struct treap *tmp = (*node)->L;
(*node)->L=tmp->R;
tmp->R=*node;
*node = tmp;
}

//anticlockwise or left rotation
void rotate_A(struct treap **node)
{
struct treap *tmp = (*node)->R;
(*node)->R=tmp->L;
tmp->L=*node;
*node = tmp;

}

void balance(struct treap **node )
{
if( (*node)->L != NULL &&   (*node)->L->prio >  (*node)->prio  ) rotate_C( node );
else if (  (*node)->R != NULL && (*node)->R->prio >  (*node)->prio ) rotate_A( node );
}

void erase(struct treap **node,int key)
{
if(*node == NULL ) return;
if( key < (*node)->key ) erase( & ( (*node)->L) , key );
else if ( key > (*node)->key )  erase( & ( (*node)->R) , key );
else // we have match
{
if( (*node)->L == NULL && (*node)->R == NULL ) *node = NULL;
else if ( (*node)->L == NULL ) *node = (*node)->R;
else if ( (*node)->R == NULL ) *node = (*node)->L;
else
{
// start rotating the tree aroung  node  depending on prioriy of left and right children and finally our tree
// will  converge to one of the upper cases. refer wiki
if ( (*node)->L->prio > (*node)->R->prio ) rotate_C( node );
else rotate_A( node );
erase(node,key);
}
}
}

void insert(struct treap **node, int key, int prio)
{

if(*node == NULL)
{
*node = (struct treap *) malloc ( sizeof ( struct treap ) );
(*node)->key=key;
(*node)->prio=prio;
(*node)->L=(*node)->R= NULL;
return;
}
else if (key <= (*node)->key) insert( &( (*node)->L ),key,prio);
else insert( &( (*node)->R ), key , prio);
balance(node);

}

void split(struct treap **node, struct treap **Ltreap, struct treap **Rtreap, int key)
{
insert(node,key,INFINITY);
*Ltreap = (*node)->L;
*Rtreap = (*node)->R;
*node = NULL;
}

//it assumes that key is larger than maximum value of Ltreap and smaller than minimum value of Rtreap
void join(struct treap **node,struct treap **Ltreap, struct treap **Rtreap, int key)
{
*node = (struct treap *) malloc (sizeof ( struct treap ) );
(*node)->key = key;
(*node)->prio = -1;
(*node)->L = *Ltreap;
(*node)->R = *Rtreap;
erase(node,key);
}

int main()
{
int n,a;
cin>>n;
struct treap *root= NULL;
for(int i=0;i<n;i++)  cin>>a,insert(&root,a,rand());
print(root,0);
cout<<" \n erase key \n";
cin>>a;
erase(&root,a);
print(root,0);
struct treap *p=NULL , *q=NULL, *r=NULL;
cout<<"\n enter the key to split\n";
cin>>n;
split(&root,&p,&q,n);
cout<<"\nfirst treap \n";print ( p ,0 );
cout<<" \nsecond treap \n"; print ( q, 0) ;
cout<<"\n merging with same key "<< n <<"\n";
join(&r,&p,&q,n); print( r , 0 );
}
```

May 2, 2011 - Posted by | Programming

## 1 Comment »

1. i can’t understand the following part of erase method:
if ( (*node)->L->prio > (*node)->R->prio ) rotate_C( node );
} else rotate_A( node );
erase(node,key);

Comment by emma12 | December 26, 2011 | Reply