Baby: Fast Sets Based on Balanced Binary Search Trees

baby is an OCaml library that offers several implementations of balanced binary search trees.

Height-balanced and weight-balanced binary search trees are offered out of the box. Furthermore, to advanced users, the library offers a lightweight way of implementing other balancing strategies.

The algorithms in baby are based on those found in OCaml's Set library and in the paper Joinable Parallel Balanced Binary Trees by Blelloch, Ferizovic, and Sun (2022).

For a discussion of the strengths of baby over OCaml's standard library, see Comparison With OCaml's Set Library.

Installation and Usage

Type opam install baby.

In your dune file, add (libraries baby) to the description of your library or executable.

Ready-Made Weight-Balanced Trees

We recommend using baby's ready-made weight-balanced binary search trees, because they are generally faster than height-balanced trees, offer a constant-time cardinal function, and offer several logarithmic-time random access functions.

To use them, just use the functor Baby.W.Set.Make instead of the usual Set.Make.

Ready-Made Height-Balanced Trees

If you prefer to use baby's ready-made height-balanced binary search trees, use Baby.H.Set.Make.

Please be aware that, in this implementation, the cardinal function is slow: its time complexity is linear. Furthermore, the random access functions are unavailable: an attempt to invoke one of them will result in a Failure exception.

Rolling Your Own Balanced Trees

If you wish to design your own balancing scheme, while re-using most of baby's functionality, use the functor Baby.Make. This requires you to implement a module that satisfies the signature Baby.CORE.

As part of this signature, the central operation that you must provide is join. You must also implement join_neighbors and join_weight_balanced, two variants of join that make stronger assumptions about their inputs. If you are lazy, you can implement both of them as just join.

Comparison With OCaml's Set Library

Better Performance

At the time of writing (2024), baby offers generally better performance than OCaml's Set library. Its operations are generally faster (sometimes much faster; sometimes slightly faster; sometimes slightly slower) than those of the Set library, and its memory allocation rate is slightly lower.

Constant-Time Cardinal

In contrast with the Set library, baby's weight-balanced trees offer a cardinal function whose time complexity is O(1). They also offer a family of random access functions (get, index, etc.) whose time complexity is O(\log n). Furthermore, by exploiting cardinality information, the functions subset and equal are sometimes able to return false in constant time.

Better Sharing

baby's binary operations (union, inter, diff) take advantage of (and preserve) physical equality in a more aggressive way. This allows them to (sometimes) be faster and allocate less memory.

Adaptive Conversions To Sets

baby's conversion functions of_list, of_array, and of_seq have adaptive complexity. If the input data is sorted, their complexity is O(n); otherwise, their complexity gracefully degrades down to O(n.\log n).

More Operations

baby offers a few operations that do not exist in OCaml's Set library:

1. The symmetric difference, xor;
2. The conversion functions of_array and to_array;
3. The extremum-removal functions remove_min_elt and remove_max_elt;
4. The enumeration API in the submodule Enum. Enumerations should be slightly faster than standard sequences, and are able to efficiently seek ahead, via the function from.

Documented Complexity

In baby, the time complexity of every operation is documented.

Compatibility

baby is perfectly compatible with OCaml's Set library. In other words, using Baby.W.Set instead of Set is safe.

As a word of warning, though, if the equivalence relation on elements is coarser than equality (that is, if compare x y = 0 does not imply x = y), then Baby.W.Set and Set might behave differently when a choice must be made between two equivalent elements. This can occur in union, of_list, of_array, of_seq, add_seq, map.