Module Reins.AVLSet

module AVLSet: sig .. end

Height balanced binary search trees implementing sets

AVL trees are balanced binary search trees with O(log n) lookup, add, and remove operations. The set operations union, inter, and diff all take O(n) time. However, some inputs to these functions will take significantly less time to process (e.g. when one tree is significantly smaller than the other, or when the trees have large number consecutive elements that do not overlap).

module PolySet: Reins.Sets.PolySetSigStd

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

module MonoSet: Reins.Sets.MonoSetSigFnStd

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

module GenSet: Reins.Sets.GenSetSigFnStd

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

All of the module below are variations of the above modules that allow client code to control the performance of the AVL tree. Note that in most cases, the modules defined above will perform the best.

module AVL_PolySet: functor (HeightDiff : sigval v : int
end) -> Reins.Sets.PolySetSigStd

This functor is similar to the Reins.AVLSet.PolySet module above, except it allows the user to specify the maximum difference between the heights of two subtrees at a node with HeightDiff.v.

module PolySet1: Reins.Sets.PolySetSigStd

Reins.AVLSet.AVL_PolySet instanced with HeightDiff.v = 1

module PolySet2: Reins.Sets.PolySetSigStd

Reins.AVLSet.AVL_PolySet instanced with HeightDiff.v = 2

module PolySet3: Reins.Sets.PolySetSigStd

Reins.AVLSet.AVL_PolySet instanced with HeightDiff.v = 3

module AVL_MonoSet: functor (HeightDiff : sigval v : int
end) -> Reins.Sets.MonoSetSigFnStd

This functor is similar to the Reins.AVLSet.MonoSet module above, except it allows the user to specify the maximum difference between the heights of two subtrees at a node with HeightDiff.v.

module MonoSet1: Reins.Sets.MonoSetSigFnStd

Reins.AVLSet.AVL_MonoSet instanced with HeightDiff.v = 1

module MonoSet2: Reins.Sets.MonoSetSigFnStd

Reins.AVLSet.AVL_MonoSet instanced with HeightDiff.v = 2

module MonoSet3: Reins.Sets.MonoSetSigFnStd

Reins.AVLSet.AVL_MonoSet instanced with HeightDiff.v = 3

module AVL_GenSet: functor (HeightDiff : sigval v : int
end) -> Reins.Sets.GenSetSigFnStd

This functor is similar to the Reins.AVLSet.GenSet module above, except it allows the user to specify the maximum difference between the heights of two subtrees at a node with HeightDiff.v.

module GenSet1: Reins.Sets.GenSetSigFnStd

Reins.AVLSet.AVL_GenSet instanced with HeightDiff.v = 1

module GenSet2: Reins.Sets.GenSetSigFnStd

Reins.AVLSet.AVL_GenSet instanced with HeightDiff.v = 2

module GenSet3: Reins.Sets.GenSetSigFnStd

Reins.AVLSet.AVL_GenSet instanced with HeightDiff.v = 3