My Weblog

Blog about programming and math

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 Control.Monad
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
rInt = read 


main::IO ( )
main = do 
	  l <- fmap ( map rInt.words )  getLine 
	  --n <- fmap read 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 "
	  n <- fmap read getLine
	  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 );
	}
Advertisements

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


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: