MkTreap functor
functor MkTreap (structure Key :
HASHKEY) :>
BST
where Key = Key
Implements the BST signature with treaps. Keys are hashed in order to generated pseudo-random priorities.
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(\log|T|)\] | \[O(\log|T|)\] |
The costs of join and split are with high probability.