The BST signature

« 210 Library Documentation

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.