## `baltree`: basic balanced binary trees

  This module implements balanced ordered binary trees. All operations over binary trees are applicative (no side-effects). The `set` and `map` modules are based on this module. This modules gives a more direct access to the internals of the binary tree implementation than the `set` and `map` abstractions, but is more delicate to use and not as safe. For advanced users only.

    type 'a t = Empty | Node of 'a t * 'a * 'a t * int

  The type of trees containing elements of type `'a`. `Empty` is the empty tree (containing no elements).

    type 'a contents = Nothing | Something of 'a

  Used with the functions `modify` and `split`, to represent the presence or the absence of an element in a tree.

    value add: ('a -> int) -> 'a -> 'a t -> 'a t

  `add f x t` inserts the element `x` into the tree `t`. `f` is an ordering function: `f y` must return `0` if `x` and `y` are equal (or equivalent), a negative integer if `x` is smaller than `y`, and a positive integer if `x` is greater than `y`. The tree `t` is returned unchanged if it already contains an element equivalent to `x` (that is, an element `y` such that `f y` is `0`). The ordering `f` must be consistent with the orderings used to build `t` with `add`, `remove`, `modify` or `split` operations.

    value contains: ('a -> int) -> 'a t -> bool

  `contains f t` checks whether `t` contains an element satisfying `f`, that is, an element `x` such that `f x` is `0`. `f` is an ordering function with the same constraints as for `add`. It can be coarser (identify more elements) than the orderings used to build `t`, but must be consistent with them.

    value find: ('a -> int) -> 'a t -> 'a

  Same as `contains`, except that `find f t` returns the element `x` such that `f x` is `0`, or raises `Not_found` if none has been found.

    value remove: ('a -> int) -> 'a t -> 'a t

  `remove f t` removes one element `x` of `t` such that `f x` is `0`. `f` is an ordering function with the same constraints as for `add`. `t` is returned unchanged if it does not contain any element satisfying `f`. If several elements of `t` satisfy `f`, only one is removed.

    value modify: ('a -> int) -> ('a contents -> 'a contents) -> 'a t -> 'a t

  General insertion/modification/deletion function. `modify f g t` searchs `t` for an element `x` satisfying the ordering function `f`. If one is found, `g` is applied to `Something x`; if `g` returns `Nothing`, the element `x` is removed; if `g` returns `Something y`, the element `y` replaces `x` in the tree. (It is assumed that `x` and `y` are equivalent, in particular, that `f y` is `0`.) If the tree does not contain any `x` satisfying `f`, `g` is applied to `Nothing`; if it returns `Nothing`, the tree is returned unchanged; if it returns `Something x`, the element `x` is inserted in the tree. (It is assumed that `f x` is `0`.) The functions `add` and `remove` are special cases of `modify`, slightly more efficient.

    value split: ('a -> int) -> 'a t -> 'a t * 'a contents * 'a t

  `split f t` returns a triple `(less, elt, greater)` where `less` is a tree containing all elements `x` of `t` such that `f x` is negative, `greater` is a tree containing all elements `x` of `t` such that `f x` is positive, and `elt` is `Something x` if `t` contains an element `x` such that `f x` is `0`, and `Nothing` otherwise.

    value compare: ('a -> 'a -> int) -> 'a t -> 'a t -> int

  Compare two trees. The first argument `f` is a comparison function over the tree elements: `f e1 e2` is zero if the elements `e1` and `e2` are equal, negative if `e1` is smaller than `e2`, and positive if `e1` is greater than `e2`. `compare f t1 t2` compares the fringes of `t1` and `t2` by lexicographic extension of `f`.