Processing math: 100%

The `MkTreap` functor

Overview


    functor MkTreap (structure Key :
    HASHKEY) :>
    BST
    where Key = Key

The following costs assume that the work and span of Key.compare and Key.hash are constant.

	Work	Span
`expose` $T$ `size` $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\|)$