MkTreap functor
functor MkTreap (structure Key :
ORDKEY) :>
BST
where Key = Key
Implements the BST signature with treaps.
A node's priority is a hash of its key, so it is pseudo-random but deterministic.
Besides the BST operations, a treap structure has
split and join:
val split :
'a bst * Key.t → 'a bst * 'a option * 'a bstsplit (T, k) evaluates to $(L, v, R)$, where $L$ holds the
key-value pairs of $T$ with keys less than $k$, $R$ the pairs with keys
greater than $k$, and $v$ is the value at $k$, or NONE if $k$
is not in $T$.val join :
'a bst * 'a bst → 'a bstjoin (L, R) evaluates to a tree holding every key-value pair
of $L$ and $R$. Requires every key of $L$ to be less than every key of
$R$.BST Cost SpecificationsThe following costs assume that comparing and hashing keys take constant work and span.
| Work | Span | |
empty $()$size $T$expose $T$
|
$O(1)$ | $O(1)$ |
joinMid $(L, (k, v), R)$join $(L, R)$
|
$O(\log(|L| + |R|))$* | $O(\log(|L| + |R|))$* |
split $(T, k)$
|
$O(\log|T|)$* | $O(\log|T|)$* |