.TH gb_trees 3erl "stdlib 3.2" "Ericsson AB" "Erlang Module Definition"
.SH NAME
gb_trees \- General balanced trees.
.SH DESCRIPTION
.LP
This module provides Prof\&. Arne Andersson\&'s General Balanced Trees\&. These have no storage overhead compared to unbalanced binary trees, and their performance is better than AVL trees\&.
.LP
This module considers two keys as different if and only if they do not compare equal (\fI==\fR\&)\&.
.SH "DATA STRUCTURE"

.LP
.nf

{Size, Tree}
.fi
.LP
\fITree\fR\& is composed of nodes of the form \fI{Key, Value, Smaller, Bigger}\fR\& and the "empty tree" node \fInil\fR\&\&.
.LP
There is no attempt to balance trees after deletions\&. As deletions do not increase the height of a tree, this should be OK\&.
.LP
The original balance condition \fIh(T) <= ceil(c * log(|T|))\fR\& has been changed to the similar (but not quite equivalent) condition \fI2 ^ h(T) <= |T| ^ c\fR\&\&. This should also be OK\&.
.SH DATA TYPES
.nf

\fBtree(Key, Value)\fR\&
.br
.fi
.RS
.LP
A general balanced tree\&.
.RE

.nf

\fBtree()\fR\& = \fBtree\fR\&(term(), term())
.br
.fi
.nf

\fBiter(Key, Value)\fR\&
.br
.fi
.RS
.LP
A general balanced tree iterator\&.
.RE

.nf

\fBiter()\fR\& = \fBiter\fR\&(term(), term())
.br
.fi
.SH EXPORTS
.LP
.nf

.B
balance(Tree1) -> Tree2
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree1 = Tree2 = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Rebalances \fITree1\fR\&\&. Notice that this is rarely necessary, but can be motivated when many nodes have been deleted from the tree without further insertions\&. Rebalancing can then be forced to minimize lookup times, as deletion does not rebalance the tree\&.
.RE

.LP
.nf

.B
delete(Key, Tree1) -> Tree2
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree1 = Tree2 = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Removes the node with key \fIKey\fR\& from \fITree1\fR\& and returns the new tree\&. Assumes that the key is present in the tree, crashes otherwise\&.
.RE

.LP
.nf

.B
delete_any(Key, Tree1) -> Tree2
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree1 = Tree2 = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Removes the node with key \fIKey\fR\& from \fITree1\fR\& if the key is present in the tree, otherwise does nothing\&. Returns the new tree\&.
.RE

.LP
.nf

.B
empty() -> tree()
.br
.fi
.br
.RS
.LP
Returns a new empty tree\&.
.RE

.LP
.nf

.B
enter(Key, Value, Tree1) -> Tree2
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree1 = Tree2 = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Inserts \fIKey\fR\& with value \fIValue\fR\& into \fITree1\fR\& if the key is not present in the tree, otherwise updates \fIKey\fR\& to value \fIValue\fR\& in \fITree1\fR\&\&. Returns the new tree\&.
.RE

.LP
.nf

.B
from_orddict(List) -> Tree
.br
.fi
.br
.RS
.LP
Types:

.RS 3
List = [{Key, Value}]
.br
Tree = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Turns an ordered list \fIList\fR\& of key-value tuples into a tree\&. The list must not contain duplicate keys\&.
.RE

.LP
.nf

.B
get(Key, Tree) -> Value
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Retrieves the value stored with \fIKey\fR\& in \fITree\fR\&\&. Assumes that the key is present in the tree, crashes otherwise\&.
.RE

.LP
.nf

.B
insert(Key, Value, Tree1) -> Tree2
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree1 = Tree2 = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Inserts \fIKey\fR\& with value \fIValue\fR\& into \fITree1\fR\& and returns the new tree\&. Assumes that the key is not present in the tree, crashes otherwise\&.
.RE

.LP
.nf

.B
is_defined(Key, Tree) -> boolean()
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key, Value :: term())
.br
.RE
.RE
.RS
.LP
Returns \fItrue\fR\& if \fIKey\fR\& is present in \fITree\fR\&, otherwise \fIfalse\fR\&\&.
.RE

.LP
.nf

.B
is_empty(Tree) -> boolean()
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree()\fR\&
.br
.RE
.RE
.RS
.LP
Returns \fItrue\fR\& if \fITree\fR\& is an empty tree, othwewise \fIfalse\fR\&\&.
.RE

.LP
.nf

.B
iterator(Tree) -> Iter
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key, Value)
.br
Iter = \fBiter\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Returns an iterator that can be used for traversing the entries of \fITree\fR\&; see \fB\fInext/1\fR\&\fR\&\&. The implementation of this is very efficient; traversing the whole tree using \fInext/1\fR\& is only slightly slower than getting the list of all elements using \fB\fIto_list/1\fR\&\fR\& 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\&.
.RE

.LP
.nf

.B
iterator_from(Key, Tree) -> Iter
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key, Value)
.br
Iter = \fBiter\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Returns an iterator that can be used for traversing the entries of \fITree\fR\&; see \fB\fInext/1\fR\&\fR\&\&. The difference as compared to the iterator returned by \fB\fIiterator/1\fR\&\fR\& is that the first key greater than or equal to \fIKey\fR\& is returned\&.
.RE

.LP
.nf

.B
keys(Tree) -> [Key]
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key, Value :: term())
.br
.RE
.RE
.RS
.LP
Returns the keys in \fITree\fR\& as an ordered list\&.
.RE

.LP
.nf

.B
largest(Tree) -> {Key, Value}
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Returns \fI{Key, Value}\fR\&, where \fIKey\fR\& is the largest key in \fITree\fR\&, and \fIValue\fR\& is the value associated with this key\&. Assumes that the tree is not empty\&.
.RE

.LP
.nf

.B
lookup(Key, Tree) -> none | {value, Value}
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Looks up \fIKey\fR\& in \fITree\fR\&\&. Returns \fI{value, Value}\fR\&, or \fInone\fR\& if \fIKey\fR\& is not present\&.
.RE

.LP
.nf

.B
map(Function, Tree1) -> Tree2
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Function = fun((K :: Key, V1 :: Value1) -> V2 :: Value2)
.br
Tree1 = \fBtree\fR\&(Key, Value1)
.br
Tree2 = \fBtree\fR\&(Key, Value2)
.br
.RE
.RE
.RS
.LP
Maps function F(K, V1) -> V2 to all key-value pairs of tree \fITree1\fR\&\&. Returns a new tree \fITree2\fR\& with the same set of keys as \fITree1\fR\& and the new set of values \fIV2\fR\&\&.
.RE

.LP
.nf

.B
next(Iter1) -> none | {Key, Value, Iter2}
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Iter1 = Iter2 = \fBiter\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Returns \fI{Key, Value, Iter2}\fR\&, where \fIKey\fR\& is the smallest key referred to by iterator \fIIter1\fR\&, and \fIIter2\fR\& is the new iterator to be used for traversing the remaining nodes, or the atom \fInone\fR\& if no nodes remain\&.
.RE

.LP
.nf

.B
size(Tree) -> integer() >= 0
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree()\fR\&
.br
.RE
.RE
.RS
.LP
Returns the number of nodes in \fITree\fR\&\&.
.RE

.LP
.nf

.B
smallest(Tree) -> {Key, Value}
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Returns \fI{Key, Value}\fR\&, where \fIKey\fR\& is the smallest key in \fITree\fR\&, and \fIValue\fR\& is the value associated with this key\&. Assumes that the tree is not empty\&.
.RE

.LP
.nf

.B
take_largest(Tree1) -> {Key, Value, Tree2}
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree1 = Tree2 = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Returns \fI{Key, Value, Tree2}\fR\&, where \fIKey\fR\& is the largest key in \fITree1\fR\&, \fIValue\fR\& is the value associated with this key, and \fITree2\fR\& is this tree with the corresponding node deleted\&. Assumes that the tree is not empty\&.
.RE

.LP
.nf

.B
take_smallest(Tree1) -> {Key, Value, Tree2}
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree1 = Tree2 = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Returns \fI{Key, Value, Tree2}\fR\&, where \fIKey\fR\& is the smallest key in \fITree1\fR\&, \fIValue\fR\& is the value associated with this key, and \fITree2\fR\& is this tree with the corresponding node deleted\&. Assumes that the tree is not empty\&.
.RE

.LP
.nf

.B
to_list(Tree) -> [{Key, Value}]
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Converts a tree into an ordered list of key-value tuples\&.
.RE

.LP
.nf

.B
update(Key, Value, Tree1) -> Tree2
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree1 = Tree2 = \fBtree\fR\&(Key, Value)
.br
.RE
.RE
.RS
.LP
Updates \fIKey\fR\& to value \fIValue\fR\& in \fITree1\fR\& and returns the new tree\&. Assumes that the key is present in the tree\&.
.RE

.LP
.nf

.B
values(Tree) -> [Value]
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree = \fBtree\fR\&(Key :: term(), Value)
.br
.RE
.RE
.RS
.LP
Returns the values in \fITree\fR\& as an ordered list, sorted by their corresponding keys\&. Duplicates are not removed\&.
.RE

.SH "SEE ALSO"

.LP
\fB\fIdict(3erl)\fR\&\fR\&, \fB\fIgb_sets(3erl)\fR\&\fR\&