The BSTREE signature

« 210 Library Documentation

Overview

functor MkTreap(structure HashKey : HASHKEY)

A BSTREE is a binary search tree. Are you sure you didn't already know that?

Interface

structure Key : ORDKEY

type 'v bst
type 'v node = { left : 'v bst, key : Key.t, value : 'v, right : 'v bst }
type key = Key.t

val size : 'v bst -> int
val empty : unit -> 'v bst
val singleton : key * 'v -> 'v bst

val makeNode : 'v node -> 'v bst
val expose : 'v bst -> 'v node option
val join : 'v bst * 'v bst -> 'v bst
val splitAt : 'v bst * key -> 'v bst * 'v option * 'v bst

val $ : key * 'v -> 'v bst

Substructures

structure Key : ORDKEY
The Key substructure defines the key type of a bst, providing equality and toString functions on such keys.

Types

type 'a bst
This is the abstract type that represents a bst as described in the overview.
type 'a node = { left : 'a bst, key : Key.t, value : 'a, right : 'a bst }
A node is a view of a binary search tree. Use makeNode and expose to convert a value of type 'a node to and from values of type 'a bst.
type key = Key.t
An alias for Key.t.

Values

val size : 'a bst -> int
I wonder what this does?
val empty : unit -> 'a bst
An empty tree! Not very interesting.
val singleton : key * 'a -> 'a bst
Neither is a singleton tree.
val makeNode : 'a node -> 'a bst
Converts a value of type 'a node to the internal 'a bst representation.
val expose : 'a bst -> 'a node option
Exposes a view of the root node of the tree.
val join : 'a bst * 'a bst -> 'a bst
If $A$ and $B$ are values of type bst such that all keys in $A$ are strictly less than all keys in $B$, (join (A, B)) evaluates to a bst containing all keys in $A$ and $B$.
val splitAt : 'a bst * key -> 'a bst * 'a option * 'a bst
(splitAt (T, k)) evaluates to $(L, m, R)$ where $L$ is a bst containing all keys less than $k$, $R$ is a bst containing all keys greater than $k$, and $m$ is an option indicating if $k\in T$ (and if so, what value $k$ is mapped to).