MkTreap
functor
functor MkTreap (structure Key :
HASHKEY) :>
BST
where Key = Key
BST
Cost Specifications
The following costs assume that the work and span of
Key.compare
and Key.hash
are constant.
Work  Span  
expose $T$size $T$empty $()$singleton $(k, v)$

\[O(1)\]  \[O(1)\] 
join $(A, B)$joinMid $(A, (k, v), B)$

\[O(\log(A + B))\]  \[O(\log(A + B))\] 
split $(T, k)$

\[O(\logT)\]  \[O(\logT)\] 