The BST signature

Overview

The BST signature is a minimal interface for a binary search tree, which is a set of key-value pairs. The keys are distinct and increase from left to right. The key type is ordered and fixed by the Key substructure while the value type is polymorphic.

Interface

structure Key : ORDKEY

type 'a t
type 'a bst = 'a t

type 'a nodeview = { left : 'a bst,
                     key : Key.t,
                     value : 'a,
                     right : 'a bst }

exception Order

val empty : unit → 'a bst
val size : 'a bst → int
val expose : 'a bst → 'a nodeview option
val joinMid : 'a bst * (Key.t * 'a) * 'a bst → 'a 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 'a t

type 'a bst = 'a t

The abstract tree type 'a t maps keys of type Key.t to values of type 'a. The alias 'a bst is for readability.

type 'a nodeview = { left : 'a bst, key : Key.t, value : 'a, right : 'a bst }

The root of a non-empty tree: its key and value, and its left and right subtrees.

Exceptions

exception Order

Order is raised when an operation detects that its arguments would violate the ordering invariant.

Values

val empty : unit → 'a bst

Construct an empty tree.

val size : 'a bst → int

Return the number of keys in the tree.

val expose : 'a bst → 'a nodeview option

expose T evaluates to NONE if $T$ is empty, and otherwise to SOME {left, key, value, right}, the root of $T$.

val joinMid : 'a bst * (Key.t * 'a) * 'a bst → 'a bst

joinMid (L, (k, v), R) evaluates to a tree containing every key-value pair of $L$, the pair $(k, v)$, and every key-value pair of $R$. Requires every key of $L$ to be less than $k$, and $k$ to be less than every key of $R$.