Processing math: 100%

The `MkAugTreap` functor

Overview

functor MkAugTreap
  (structure Key : HASHKEY
   structure Val : MONOID)
  :> AUG_BST where Key = Key and Val = Val

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\|)$