The BST signature

Overview

The BST signature is a minimalistic interface for a binary search tree, which is a set of key-value pairs. The key type is ordered and fixed by the Key substructure while the value type is polymorphic.

Interface

structure Key : ORDKEY

type α t
type α bst = α t

datatype α view =
LEAF
| NODE of { key : Key.t
, value : α
, left : α bst
, right : α bst }

exception Order

val expose : α bst → α view
val size : α bst → int

val empty : unit → α bst
val singleton : Key.t * α → α bst

val join : α bst * α bst → α bst
val joinMid : α bst * (Key.t * α) * α bst → α bst

val split : α bst * Key.t → α bst * α option * α bst

val $: Key.t * α → α bst Substructures structure Key : ORDKEY The Key substructure defines the key type of a binary search tree, providing comparison and other useful functions on keys. Types type α t The abstract tree type. type α bst = α t An alias, for readability. type α view = LEAF | NODE of {key : Key.t, value : α, left : α bst, right : α bst} A one-layer view of a tree, which is either a leaf (containing no data) or an interior node with a key, value, and two children. Exceptions exception Order Order is raised whenever tree operations would violate the ordering invariant. Values val expose : α bst → α view Expose a view of the root node of the tree. val size : α bst → int Return the number of nodes in the tree. val empty : unit → α bst Construct an empty tree. val singleton : Key.t * α → α bst Construct a tree containing a single node with the given key and value. val join : α bst * α bst → α bst Given trees$A$and$B$where all keys in$A$are strictly less than all keys in$B$, (join (A, B)) evaluates to the union of$A$and$B$. val joinMid : α bst * (Key.t * α) * α bst → α bst (joinMid (A, (k, v), B)) is logically equivalent to (join (A, join (singleton (k, v), B))). val split : α bst * Key.t → α bst * α option * α bst (split (T, k)) evaluates to$(L, x, R)$where$L$is a bst containing all keys less than$k$,$R$is a bst containing all keys greater than$k$, and$x$is the value associated with$k$(or NONE, if$k \not\in T$). val$ : Key.t * α → α bst
An alias for singleton.