Loading [MathJax]/jax/output/CommonHTML/jax.js

The `MkTreap` functor

Overview


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

Implements the BST signature with treaps. Keys are hashed in order to generated pseudo-random priorities.

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

The costs of join and split are with high probability.