MkAugTreap functorfunctor MkAugTreap
(structure Key : ORDKEY
type value
val combine : value * value → value
val identity : value)
:> AUG_BST where Key = Key and type value = value
Implements the AUG_BST signature
with treaps, as MkTreap does for
BST. Each node stores the reduced value of its subtree.
Besides the AUG_BST operations, a treap structure has
split and join:
val split :
bst * Key.t → bst * value option * 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 :
bst * bst → 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$.AUG_BST Cost Specifications
The following costs assume that comparing and hashing keys, and
combine, take constant work and span.
| Work | Span | |
empty $()$size $T$expose $T$reducedVal $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|)$* |