<!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.PatriciaSet.html">
<link rel="next" href="Reins.SplaySet.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.RBSet</title>
</head>
<body>
<div class="navbar"><a href="Reins.PatriciaSet.html">Previous</a>
<a href="Reins.html">Up</a>
<a href="Reins.SplaySet.html">Next</a>
</div>
<center><h1>Module <a href="type_Reins.RBSet.html">Reins.RBSet</a></h1></center>
<br>
<pre><span class="keyword">module</span> RBSet: <code class="code">sig</code> <a href="Reins.RBSet.html">..</a> <code class="code">end</code></pre><hr width="100%">
<br>
Balanaced binary search tree with small memory footprint
<p>
Redblack trees are balanced binary search trees that provide O(log
n) <code class="code">mem</code>, <code class="code">add</code>, and <code class="code">remove</code> tree operations and O(n) <code class="code">union</code>,
<code class="code">inter</code>, and <code class="code">diff</code> 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.<br>
<pre><span class="keyword">module</span> <a href="Reins.RBSet.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 RedBlack trees with a
polymorphic element type.
</div>
<pre><span class="keyword">module</span> <a href="Reins.RBSet.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 RedBlack trees that are
parameterized by a specific monomorphic element type.
</div>
<pre><span class="keyword">module</span> <a href="Reins.RBSet.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.RBSet.MonoSet.html"><code class="code">Reins.RBSet.MonoSet</code></a> functor except it
is parameterized by a module that also supports the <code class="code">gen</code>
operation.
</div>
</body></html>
