Module Baby

This library offers two flavors of binary search trees as well as building blocks that allow advanced users to construct their own custom flavors.

For height-balanced binary search trees, ready for use, please see Baby.H.Set.Make.

For weight-balanced binary search trees, ready for use, please see Baby.W.Set.Make.

module type OrderedType = sig ... end

The signature Baby.OrderedType describes a type equipped with a total ordering function.

The signature Baby.BASE_SET describes the interface that is offered by the base layer (the balancing code) to the upper layer (the set library).

module type BASE_SET = sig ... end

The signature Baby.BASE_MAP describes the interface that is offered by the base layer (the balancing code) to the upper layer (the map library).

module type BASE_MAP = sig ... end
module type SET = sig ... end

The signature Baby.SET describes an abstract data type of sets, equipped with a wide array of efficient operations.

module type MAP = sig ... end

The signature Baby.MAP describes an abstract data type of maps, equipped with a wide array of efficient operations.

module type SET_MAP = sig ... end

The signature Baby.SET_MAP describes abstract data types of sets and maps. They are described in two forms:

module H : SET_MAP

The module Baby.H provides ready-made height-balanced binary search trees.

module W : SET_MAP

The module Baby.W provides ready-made weight-balanced binary search trees.

module Custom (_ : BASE_SET) (_ : BASE_MAP) : SET_MAP

The functor Baby.Custom constructs balanced binary search trees based on a user-supplied balancing scheme.