File: gb_trees.html

package info (click to toggle)
erlang-doc-html 1%3A11.b.2-1
links: PTS
area: main
in suites: etch, etch-m68k
size: 23,284 kB
ctags: 10,724
sloc: erlang: 505; ansic: 323; makefile: 62; perl: 61; sh: 45
file content (496 lines) | stat: -rw-r--r-- 12,937 bytes
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<!-- This document was generated using DocBuilder 3.3.3 -->
<HTML>
<HEAD>
  <TITLE>gb_trees</TITLE>
  <SCRIPT type="text/javascript" src="../../../../doc/erlresolvelinks.js">
</SCRIPT>
  <STYLE TYPE="text/css">
<!--
    .REFBODY     { margin-left: 13mm }
    .REFTYPES    { margin-left: 8mm }
-->
  </STYLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#FF00FF"
      ALINK="#FF0000">
<!-- refpage -->
<CENTER>
<A HREF="http://www.erlang.se">
  <IMG BORDER=0 ALT="[Ericsson AB]" SRC="min_head.gif">
</A>
<H1>gb_trees</H1>
</CENTER>

<H3>MODULE</H3>
<DIV CLASS=REFBODY>
gb_trees
</DIV>

<H3>MODULE SUMMARY</H3>
<DIV CLASS=REFBODY>
General Balanced Trees
</DIV>

<H3>DESCRIPTION</H3>
<DIV CLASS=REFBODY>

<P>An efficient implementation of Prof. Arne Andersson's General
Balanced Trees. These have no storage overhead compared to
unbalaced binary trees, and their performance is in general
better than AVL trees.
</DIV>

<H3>Data structure</H3>
<DIV CLASS=REFBODY>

<P> Data structure:

<PRE>
      
- {Size, Tree}, where `Tree' is composed of nodes of the form:
  - {Key, Value, Smaller, Bigger}, and the &#34;empty tree&#34; node:
  - nil.
    
</PRE>

<P>There is no attempt to balance trees after deletions. Since
deletions do not increase the height of a tree, this should be OK.

<P>Original balance condition <STRONG>h(T) &#60;= ceil(c * log(|T|))</STRONG>
has been changed to the similar (but not quite equivalent)
condition <STRONG>2 ^ h(T) &#60;= |T| ^ c</STRONG>. This should also be OK.

<P>Performance is comparable to the AVL trees in the Erlang book
(and faster in general due to less overhead); the difference is
that deletion works for these trees, but not for the book's
trees. Behaviour is logaritmic (as it should be).
</DIV>

<H3>DATA TYPES</H3>
<DIV CLASS=REFBODY>

<PRE>
gb_tree() = a GB tree
    
</PRE>

</DIV>

<H3>EXPORTS</H3>

<P><A NAME="balance/1"><STRONG><CODE>balance(Tree1) -&#62; Tree2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree1 = Tree2 = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Rebalances <CODE>Tree1</CODE>. Note that this is rarely necessary,
         but may be motivated when a large number of nodes have been
         deleted from the tree without further insertions. Rebalancing
         could then be forced in order to minimise lookup times, since
         deletion only does not rebalance the tree.
</DIV>

<P><A NAME="delete/2"><STRONG><CODE>delete(Key, Tree1) -&#62; Tree2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Key = term()</CODE></STRONG><BR>
<STRONG><CODE>Tree1 = Tree2 = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Removes the node with key <CODE>Key</CODE> from <CODE>Tree1</CODE>;
         returns new tree. Assumes that the key is present in the tree,
         crashes otherwise.
</DIV>

<P><A NAME="delete_any/2"><STRONG><CODE>delete_any(Key, Tree1) -&#62; Tree2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Key = term()</CODE></STRONG><BR>
<STRONG><CODE>Tree1 = Tree2 = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Removes the node with key <CODE>Key</CODE> from <CODE>Tree1</CODE> if
         the key is present in the tree, otherwise does nothing;
         returns new tree.
</DIV>

<P><A NAME="empty/0"><STRONG><CODE>empty() -&#62; Tree</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns a new empty tree
</DIV>

<P><A NAME="enter/3"><STRONG><CODE>enter(Key, Val, Tree1) -&#62; Tree2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>
<STRONG><CODE>Tree1 = Tree2 = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Inserts <CODE>Key</CODE> with value <CODE>Val</CODE> into <CODE>Tree1</CODE> if
         the key is not present in the tree, otherwise updates
         <CODE>Key</CODE> to value <CODE>Val</CODE> in <CODE>Tree1</CODE>. Returns the
         new tree.
</DIV>

<P><A NAME="from_orddict/1"><STRONG><CODE>from_orddict(List) -&#62; Tree</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>List = [{Key, Val}]</CODE></STRONG><BR>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Turns an ordered list <CODE>List</CODE> of key-value tuples into a
         tree. The list must not contain duplicate keys.
</DIV>

<P><A NAME="get/2"><STRONG><CODE>get(Key, Tree) -&#62; Val</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Retrieves the value stored with <CODE>Key</CODE> in <CODE>Tree</CODE>.
         Assumes that the key is present in the tree, crashes
         otherwise.
</DIV>

<P><A NAME="lookup/2"><STRONG><CODE>lookup(Key, Tree) -&#62; {value, Val} | none</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Looks up <CODE>Key</CODE> in <CODE>Tree</CODE>; returns
         <CODE>{value, Val}</CODE>, or <CODE>none</CODE> if <CODE>Key</CODE> is not
         present.
</DIV>

<P><A NAME="insert/3"><STRONG><CODE>insert(Key, Val, Tree1) -&#62; Tree2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>
<STRONG><CODE>Tree1 = Tree2 = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Inserts <CODE>Key</CODE> with value <CODE>Val</CODE> into <CODE>Tree1</CODE>;
         returns the new tree. Assumes that the key is not present in
         the tree, crashes otherwise.
</DIV>

<P><A NAME="is_defined/2"><STRONG><CODE>is_defined(Key, Tree) -&#62; bool()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>true</CODE> if <CODE>Key</CODE> is present in <CODE>Tree</CODE>,
         otherwise <CODE>false</CODE>.
</DIV>

<P><A NAME="is_empty/1"><STRONG><CODE>is_empty(Tree) -&#62; bool()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>true</CODE> if <CODE>Tree</CODE> is an empty tree, and
         <CODE>false</CODE> otherwise.
</DIV>

<P><A NAME="iterator/1"><STRONG><CODE>iterator(Tree) -&#62; Iter</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>
<STRONG><CODE>Iter = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns an iterator that can be used for traversing the
         entries of <CODE>Tree</CODE>; see <CODE>next/1</CODE>. The implementation
         of this is very efficient; traversing the whole tree using
         <CODE>next/1</CODE> is only slightly slower than getting the list
         of all elements using <CODE>to_list/1</CODE> and traversing that.
         The main advantage of the iterator approach is that it does
         not require the complete list of all elements to be built in
         memory at one time.
</DIV>

<P><A NAME="keys/1"><STRONG><CODE>keys(Tree) -&#62; [Key]</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>
<STRONG><CODE>Key = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the keys in <CODE>Tree</CODE> as an ordered list.
</DIV>

<P><A NAME="largest/1"><STRONG><CODE>largest(Tree) -&#62; {Key, Val}</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>{Key, Val}</CODE>, where <CODE>Key</CODE> is the largest
         key in <CODE>Tree</CODE>, and <CODE>Val</CODE> is the value associated
         with this key. Assumes that the tree is nonempty.
</DIV>

<P><A NAME="next/1"><STRONG><CODE>next(Iter1) -&#62; {Key, Val, Iter2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Iter1 = Iter2 = Key = Val = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>{Key, Val, Iter2}</CODE> where <CODE>Key</CODE> is the
         smallest key referred to by the iterator <CODE>Iter1</CODE>, and
         <CODE>Iter2</CODE> is the new iterator to be used for
         traversing the remaining nodes, or the atom <CODE>none</CODE> if no
         nodes remain.
</DIV>

<P><A NAME="size/1"><STRONG><CODE>size(Tree) -&#62; int()</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the number of nodes in <CODE>Tree</CODE>.
</DIV>

<P><A NAME="smallest/1"><STRONG><CODE>smallest(Tree) -&#62; {Key, Val}</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>{Key, Val}</CODE>, where <CODE>Key</CODE> is the smallest
         key in <CODE>Tree</CODE>, and <CODE>Val</CODE> is the value associated
         with this key. Assumes that the tree is nonempty.
</DIV>

<P><A NAME="take_largest/1"><STRONG><CODE>take_largest(Tree1) -&#62; {Key, Val, Tree2}</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree1 = Tree2 = gb_tree()</CODE></STRONG><BR>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>{Key, Val, Tree2}</CODE>, where <CODE>Key</CODE> is the
         largest key in <CODE>Tree1</CODE>, <CODE>Val</CODE> is the value
         associated with this key, and <CODE>Tree2</CODE> is this tree with
         the corresponding node deleted. Assumes that the tree is
         nonempty.
</DIV>

<P><A NAME="take_smallest/1"><STRONG><CODE>take_smallest(Tree1) -&#62; {Key, Val, Tree2}</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree1 = Tree2 = gb_tree()</CODE></STRONG><BR>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns <CODE>{Key, Val, Tree2}</CODE>, where <CODE>Key</CODE> is the
         smallest key in <CODE>Tree1</CODE>, <CODE>Val</CODE> is the value
         associated with this key, and <CODE>Tree2</CODE> is this tree with
         the corresponding node deleted. Assumes that the tree is
         nonempty.
</DIV>

<P><A NAME="to_list/1"><STRONG><CODE>to_list(Tree) -&#62; [{Key, Val}]</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Converts a tree into an ordered list of key-value tuples.
</DIV>

<P><A NAME="update/3"><STRONG><CODE>update(Key, Val, Tree1) -&#62; Tree2</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Key = Val = term()</CODE></STRONG><BR>
<STRONG><CODE>Tree1 = Tree2 = gb_tree()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Updates <CODE>Key</CODE> to value <CODE>Val</CODE> in <CODE>Tree1</CODE>;
         returns the new tree. Assumes that the key is present in the
         tree.
</DIV>

<P><A NAME="values/1"><STRONG><CODE>values(Tree) -&#62; [Val]</CODE></STRONG></A><BR>

<DIV CLASS=REFBODY><P>Types:
  <DIV CLASS=REFTYPES>
<P>
<STRONG><CODE>Tree = gb_tree()</CODE></STRONG><BR>
<STRONG><CODE>Val = term()</CODE></STRONG><BR>

  </DIV>
</DIV>

<DIV CLASS=REFBODY>

<P>Returns the values in <CODE>Tree</CODE> as an ordered list, sorted
         by their corresponding keys. Duplicates are not removed.
</DIV>

<H3>SEE ALSO</H3>
<DIV CLASS=REFBODY>

<P> <A HREF="gb_sets.html">gb_sets(3)</A>, 
<A HREF="dict.html">dict(3)</A>

</DIV>

<H3>AUTHORS</H3>
<DIV CLASS=REFBODY>
Sven-Olof Nystrom, Richard Carlsson - support@erlang.ericsson.se<BR>

</DIV>
<CENTER>
<HR>
<SMALL>stdlib 1.14.2<BR>
Copyright &copy; 1991-2006
<A HREF="http://www.erlang.se">Ericsson AB</A><BR>
</SMALL>
</CENTER>
</BODY>
</HTML>