The MkAugTreap functor

« 210 Library Documentation


functor 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.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(\log|T|)\] \[O(\log|T|)\]