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:

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:

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:

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