The MkAugTreap functor

« 210 Library Documentation

Overview

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