.TH gb_trees 3erl "stdlib 3.14" "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
Trees and iterators are built using opaque data structures that should not be pattern-matched from outside this module\&.
.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\& = tree(term(), term())
.br
.fi
.nf

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

.nf

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

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

.RS 3
Tree1 = Tree2 = tree(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 = tree(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 = tree(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
take(Key, Tree1) -> {Value, Tree2}
.br
.fi
.br
.RS
.LP
Types:

.RS 3
Tree1 = Tree2 = tree(Key, term())
.br
Key = Value = term()
.br
.RE
.RE
.RS
.LP
Returns a value \fIValue\fR\& from node with key \fIKey\fR\& and new \fITree2\fR\& without the node with this value\&. Assumes that the node with key is present in the tree, crashes otherwise\&.
.RE

.LP
.nf

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

.RS 3
Tree1 = Tree2 = tree(Key, term())
.br
Key = Value = term()
.br
.RE
.RE
.RS
.LP
Returns a value \fIValue\fR\& from node with key \fIKey\fR\& and new \fITree2\fR\& without the node with this value\&. Returns \fIerror\fR\& if the node with the key is not present in the 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 = tree(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 = tree(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 = tree(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 = tree(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 = tree(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 = tree()
.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 = tree(Key, Value)
.br
Iter = iter(Key, Value)
.br
.RE
.RE
.RS
.LP
Returns an iterator that can be used for traversing the entries of \fITree\fR\&; see \fInext/1\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 \fIto_list/1\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 = tree(Key, Value)
.br
Iter = iter(Key, Value)
.br
.RE
.RE
.RS
.LP
Returns an iterator that can be used for traversing the entries of \fITree\fR\&; see \fInext/1\fR\&\&. The difference as compared to the iterator returned by \fIiterator/1\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 = tree(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 = tree(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 = tree(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 = tree(Key, Value1)
.br
Tree2 = tree(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 = iter(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 = tree()
.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 = tree(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 = tree(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 = tree(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 = tree(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 = tree(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 = tree(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
\fIdict(3erl)\fR\&, \fIgb_sets(3erl)\fR\&