Treaps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import Data.List

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

searchKey::Ord a => Treap a -> a-> Maybe a
searchKey NIL  k = Nothing
searchKey ( T _ a x y ) k = 
  case compare k a of 
	LT -> searchKey x k 
	GT -> searchKey y k
	EQ -> Just a

--move left subtree or clockwise rotation or right rotation
rotateL::Treap a -> Treap a
rotateL NIL = NIL
rotateL ( T p a ( T p_l a_l x_l y_l ) y_r ) = ( T p_l a_l x_l ( T p a y_l y_r ) )
rotateL ( T p a x y ) = T p a x y 

--move right subtree to root or anticlockwise rotation or left rotation 
rotateR::Treap a -> Treap a
rotateR NIL = NIL 
rotateR ( T p a x_l ( T p_r a_r x_r y_r ) ) = ( T  p_r a_r (T p a x_l x_r )  y_r )
rotateR ( T p a x y ) =  T p a x y 

prioritY :: Treap a -> Integer
prioritY NIL = -1
prioritY ( T p a x y ) = p


balancE :: Treap a -> Treap a
balancE NIL = NIL 
balancE x@( T p a l r )  
	| p < prioritY l = rotateL x
	| p < prioritY r  = rotateR x
	| otherwise = x 

--excellent article for deletion http://infoarena.ro/treapuri
erasE::(Ord a) => Treap a ->  a -> Treap a
erasE NIL a' = NIL
erasE  ( T p a x y )  a' 
	| a' < a =  T p a ( erasE x a' ) y
	| a' > a =  T p a x ( erasE y a' )
	| otherwise = if prioritY x > prioritY y then  erasE ( rotateL x) a'   else erasE ( rotateR y ) a'

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 )