`BST`

signature
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.

```
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
```

`structure`

**Key**: ORDKEY-
The
`Key`

substructure defines the key type of a binary search tree, providing comparison and other useful functions on keys.

`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.

`exception`

**Order**`Order`

is raised whenever tree operations would violate the ordering invariant.

`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`

.