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.