The MkTreap functor

« 210 Library Documentation

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.

BST Cost Specifications

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.