Module Reins.RBSet

module RBSet: sig .. end

Balanaced binary search tree with small memory footprint

Redblack trees are balanced binary search trees that provide O(log n) mem, add, and remove tree operations and O(n) union, inter, and diff set operations. They can also be more memory efficient than AVL trees since they only need to store 1 bit of information to maintain their internal invariants. In the current implementation, this bit is encoded in the type constructor, meaning that each internal node of the tree uses one less word of memory than AVL trees.

module PolySet: Reins.Sets.PolySetSigStd

This module provides an implementation of RedBlack trees with a polymorphic element type.

module MonoSet: Reins.Sets.MonoSetSigFnStd

This functor provides an implementation of RedBlack trees that are parameterized by a specific monomorphic element type.

module GenSet: Reins.Sets.GenSetSigFnStd

This functor is similar to the Reins.RBSet.MonoSet functor except it is parameterized by a module that also supports the gen operation.