package baby

  1. Overview
  2. Docs

Module BabySource

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.

Sourcemodule type OrderedType = sig ... end

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

Sourcemodule type CORE = sig ... end

The signature Baby.CORE describes the interface that must be offered by the balancing code to the rest of the balanced binary search tree library. Most operations on binary search tree are built on top of this interface, and are oblivious to the balancing criterion.

Sourcemodule type SET = sig ... end

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

Sourcemodule Make (E : OrderedType) (_ : CORE with type key = E.t) : SET with type elt = E.t

The functor Baby.Make constructs balanced binary search trees based on a user-supplied balancing scheme. The main operation that the user is expected to provide is join.

Sourcemodule H : sig ... end

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

Sourcemodule W : sig ... end

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