MkAugTreap
functorfunctor MkAugTreap
(structure Key : HASHKEY
structure Val : MONOID)
:> AUG_BST where Key = Key and Val = Val
BST
Cost Specifications
The following costs assume that the work and span of
Key.compare
, Key.hash
, and Val.f
are constant.
Work  Span  
expose $T$size $T$reduceVal $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)\] 