<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="style.css" type="text/css">
<meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type">
<link rel="Start" href="index.html">
<link rel="previous" href="Reins.OracleSet.html">
<link rel="next" href="Reins.PatriciaSet.html">
<link rel="Up" href="Reins.html">
<link title="Index of types" rel=Appendix href="index_types.html">
<link title="Index of exceptions" rel=Appendix href="index_exceptions.html">
<link title="Index of values" rel=Appendix href="index_values.html">
<link title="Index of modules" rel=Appendix href="index_modules.html">
<link title="Index of module types" rel=Appendix href="index_module_types.html">
<link title="Reins" rel="Chapter" href="Reins.html"><title>Reins.AVLSet</title>
</head>
<body>
<div class="navbar"><a href="Reins.OracleSet.html">Previous</a>
<a href="Reins.html">Up</a>
<a href="Reins.PatriciaSet.html">Next</a>
</div>
<center><h1>Module <a href="type_Reins.AVLSet.html">Reins.AVLSet</a></h1></center>
<br>
<pre><span class="keyword">module</span> AVLSet: <code class="code">sig</code> <a href="Reins.AVLSet.html">..</a> <code class="code">end</code></pre><hr width="100%">
<br>
Height balanced binary search trees implementing sets
<p>
AVL trees are balanced binary search trees with O(log n) lookup,
add, and remove operations. The set operations <code class="code">union</code>, <code class="code">inter</code>,
and <code class="code">diff</code> 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).<br>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.PolySet.html">PolySet</a>: <code class="type"><a href="Reins.Sets.PolySetSigStd.html">Reins.Sets.PolySetSigStd</a></code><code class="type"> </code></pre><div class="info">
This module provides an implementation of AVL trees with a
polymorphic element type.
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.MonoSet.html">MonoSet</a>: <code class="type"><a href="Reins.Sets.MonoSetSigFnStd.html">Reins.Sets.MonoSetSigFnStd</a></code><code class="type"> </code></pre><div class="info">
This functor provides an implementation of AVL trees that are
parameterized by a specific monomorphic element type.
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.GenSet.html">GenSet</a>: <code class="type"><a href="Reins.Sets.GenSetSigFnStd.html">Reins.Sets.GenSetSigFnStd</a></code><code class="type"> </code></pre><div class="info">
This functor is similar to the <a href="Reins.AVLSet.MonoSet.html"><code class="code">Reins.AVLSet.MonoSet</code></a> functor except
it is parameterized by a module that also supports the <code class="code">gen</code>
operation.
</div>
<br>
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.<br>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.AVL_PolySet.html">AVL_PolySet</a>: <div class="sig_block"><code class="code">functor (</code><code class="code">HeightDiff</code><code class="code"> : </code><code class="code">sig</code><div class="sig_block"><pre><span id="VALv"><span class="keyword">val</span> v</span> : <code class="type">int</code></pre></div><code class="code">end</code><code class="code">) -> </code><code class="type"><a href="Reins.Sets.PolySetSigStd.html">Reins.Sets.PolySetSigStd</a></code><code class="type"> </code></div></pre><div class="info">
This functor is similar to the <a href="Reins.AVLSet.PolySet.html"><code class="code">Reins.AVLSet.PolySet</code></a> module above,
except it allows the user to specify the maximum difference
between the heights of two subtrees at a node with <code class="code">HeightDiff.v</code>.
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.PolySet1.html">PolySet1</a>: <code class="type"><a href="Reins.Sets.PolySetSigStd.html">Reins.Sets.PolySetSigStd</a></code><code class="type"> </code></pre><div class="info">
<a href="Reins.AVLSet.AVL_PolySet.html"><code class="code">Reins.AVLSet.AVL_PolySet</code></a> instanced with HeightDiff.v = 1
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.PolySet2.html">PolySet2</a>: <code class="type"><a href="Reins.Sets.PolySetSigStd.html">Reins.Sets.PolySetSigStd</a></code><code class="type"> </code></pre><div class="info">
<a href="Reins.AVLSet.AVL_PolySet.html"><code class="code">Reins.AVLSet.AVL_PolySet</code></a> instanced with HeightDiff.v = 2
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.PolySet3.html">PolySet3</a>: <code class="type"><a href="Reins.Sets.PolySetSigStd.html">Reins.Sets.PolySetSigStd</a></code><code class="type"> </code></pre><div class="info">
<a href="Reins.AVLSet.AVL_PolySet.html"><code class="code">Reins.AVLSet.AVL_PolySet</code></a> instanced with HeightDiff.v = 3
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.AVL_MonoSet.html">AVL_MonoSet</a>: <div class="sig_block"><code class="code">functor (</code><code class="code">HeightDiff</code><code class="code"> : </code><code class="code">sig</code><div class="sig_block"><pre><span id="VALv"><span class="keyword">val</span> v</span> : <code class="type">int</code></pre></div><code class="code">end</code><code class="code">) -> </code><code class="type"><a href="Reins.Sets.MonoSetSigFnStd.html">Reins.Sets.MonoSetSigFnStd</a></code><code class="type"> </code></div></pre><div class="info">
This functor is similar to the <a href="Reins.AVLSet.MonoSet.html"><code class="code">Reins.AVLSet.MonoSet</code></a> module above,
except it allows the user to specify the maximum difference
between the heights of two subtrees at a node with <code class="code">HeightDiff.v</code>.
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.MonoSet1.html">MonoSet1</a>: <code class="type"><a href="Reins.Sets.MonoSetSigFnStd.html">Reins.Sets.MonoSetSigFnStd</a></code><code class="type"> </code></pre><div class="info">
<a href="Reins.AVLSet.AVL_MonoSet.html"><code class="code">Reins.AVLSet.AVL_MonoSet</code></a> instanced with HeightDiff.v = 1
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.MonoSet2.html">MonoSet2</a>: <code class="type"><a href="Reins.Sets.MonoSetSigFnStd.html">Reins.Sets.MonoSetSigFnStd</a></code><code class="type"> </code></pre><div class="info">
<a href="Reins.AVLSet.AVL_MonoSet.html"><code class="code">Reins.AVLSet.AVL_MonoSet</code></a> instanced with HeightDiff.v = 2
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.MonoSet3.html">MonoSet3</a>: <code class="type"><a href="Reins.Sets.MonoSetSigFnStd.html">Reins.Sets.MonoSetSigFnStd</a></code><code class="type"> </code></pre><div class="info">
<a href="Reins.AVLSet.AVL_MonoSet.html"><code class="code">Reins.AVLSet.AVL_MonoSet</code></a> instanced with HeightDiff.v = 3
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.AVL_GenSet.html">AVL_GenSet</a>: <div class="sig_block"><code class="code">functor (</code><code class="code">HeightDiff</code><code class="code"> : </code><code class="code">sig</code><div class="sig_block"><pre><span id="VALv"><span class="keyword">val</span> v</span> : <code class="type">int</code></pre></div><code class="code">end</code><code class="code">) -> </code><code class="type"><a href="Reins.Sets.GenSetSigFnStd.html">Reins.Sets.GenSetSigFnStd</a></code><code class="type"> </code></div></pre><div class="info">
This functor is similar to the <a href="Reins.AVLSet.GenSet.html"><code class="code">Reins.AVLSet.GenSet</code></a> module above,
except it allows the user to specify the maximum difference
between the heights of two subtrees at a node with <code class="code">HeightDiff.v</code>.
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.GenSet1.html">GenSet1</a>: <code class="type"><a href="Reins.Sets.GenSetSigFnStd.html">Reins.Sets.GenSetSigFnStd</a></code><code class="type"> </code></pre><div class="info">
<a href="Reins.AVLSet.AVL_GenSet.html"><code class="code">Reins.AVLSet.AVL_GenSet</code></a> instanced with HeightDiff.v = 1
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.GenSet2.html">GenSet2</a>: <code class="type"><a href="Reins.Sets.GenSetSigFnStd.html">Reins.Sets.GenSetSigFnStd</a></code><code class="type"> </code></pre><div class="info">
<a href="Reins.AVLSet.AVL_GenSet.html"><code class="code">Reins.AVLSet.AVL_GenSet</code></a> instanced with HeightDiff.v = 2
</div>
<pre><span class="keyword">module</span> <a href="Reins.AVLSet.GenSet3.html">GenSet3</a>: <code class="type"><a href="Reins.Sets.GenSetSigFnStd.html">Reins.Sets.GenSetSigFnStd</a></code><code class="type"> </code></pre><div class="info">
<a href="Reins.AVLSet.AVL_GenSet.html"><code class="code">Reins.AVLSet.AVL_GenSet</code></a> instanced with HeightDiff.v = 3
</div>
</body></html>
