Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

home | help
gb_trees(3)		   Erlang Module Definition		   gb_trees(3)

NAME
       gb_trees	- General Balanced Trees

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

       This  module considers two keys as different if and only	if they	do not
       compare equal (==).

DATA STRUCTURE
       Data structure:

       - {Size,	Tree}, where `Tree' is composed	of nodes of the	form:
	 - {Key, Value,	Smaller, Bigger}, and the "empty tree" node:
	 - nil.

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

       Original	 balance condition h(T)	_= ceil(c * log(|T|)) has been changed
       to the similar (but not quite equivalent) condition 2 ^ h(T) _=	|T|  ^
       c. This should also be OK.

       Performance  is	comparable  to	the  AVL trees in the Erlang book (and
       faster in general due to	less overhead);	the difference is  that	 dele-
       tion  works for these trees, but	not for	the book's trees. Behaviour is
       logarithmic (as it should be).

DATA TYPES
       tree(Key, Value)

	      A	GB tree.

       tree()

	      tree() is	equivalent to tree(term(), term()).

       iter(Key, Value)

	      A	GB tree	iterator.

       iter()

	      iter() is	equivalent to iter(term(), term()).

EXPORTS
       balance(Tree1) -> Tree2

	      Types:

		 Tree1 = Tree2 = tree(Key, Value)

	      Rebalances Tree1.	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.

       delete(Key, Tree1) -> Tree2

	      Types:

		 Tree1 = Tree2 = tree(Key, Value)

	      Removes the node with key	Key from Tree1;	returns	new tree.  As-
	      sumes that the key is present in the tree, crashes otherwise.

       delete_any(Key, Tree1) -> Tree2

	      Types:

		 Tree1 = Tree2 = tree(Key, Value)

	      Removes  the  node with key Key from Tree1 if the	key is present
	      in the tree, otherwise does nothing; returns new tree.

       empty() -> tree()

	      Returns a	new empty tree

       enter(Key, Value, Tree1)	-> Tree2

	      Types:

		 Tree1 = Tree2 = tree(Key, Value)

	      Inserts Key with value Value  into  Tree1	 if  the  key  is  not
	      present  in  the	tree,  otherwise updates Key to	value Value in
	      Tree1. Returns the new tree.

       from_orddict(List) -> Tree

	      Types:

		 List =	[{Key, Value}]
		 Tree =	tree(Key, Value)

	      Turns an ordered list List of key-value tuples into a tree.  The
	      list must	not contain duplicate keys.

       get(Key,	Tree) -> Value

	      Types:

		 Tree =	tree(Key, Value)

	      Retrieves	 the  value  stored with Key in	Tree. Assumes that the
	      key is present in	the tree, crashes otherwise.

       insert(Key, Value, Tree1) -> Tree2

	      Types:

		 Tree1 = Tree2 = tree(Key, Value)

	      Inserts Key with value Value into	Tree1; returns the  new	 tree.
	      Assumes  that the	key is not present in the tree,	crashes	other-
	      wise.

       is_defined(Key, Tree) ->	boolean()

	      Types:

		 Tree =	tree(Key, Value	:: term())

	      Returns true if Key is present in	Tree, otherwise	false.

       is_empty(Tree) -> boolean()

	      Types:

		 Tree =	tree()

	      Returns true if Tree is an empty tree, and false otherwise.

       iterator(Tree) -> Iter

	      Types:

		 Tree =	tree(Key, Value)
		 Iter =	iter(Key, Value)

	      Returns an iterator that can be used for traversing the  entries
	      of  Tree;	 see  next/1. The implementation of this is very effi-
	      cient; traversing	the whole tree using next/1 is	only  slightly
	      slower than getting the list of all elements using to_list/1 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.

       keys(Tree) -> [Key]

	      Types:

		 Tree =	tree(Key, Value	:: term())

	      Returns the keys in Tree as an ordered list.

       largest(Tree) ->	{Key, Value}

	      Types:

		 Tree =	tree(Key, Value)

	      Returns {Key, Value}, where Key is the largest key in Tree,  and
	      Value  is	 the  value associated with this key. Assumes that the
	      tree is nonempty.

       lookup(Key, Tree) -> none | {value, Value}

	      Types:

		 Tree =	tree(Key, Value)

	      Looks up Key in Tree; returns {value, Value}, or none if Key  is
	      not present.

       map(Function, Tree1) -> Tree2

	      Types:

		 Function = fun((K :: Key, V1 :: Value1) -> V2 :: Value2)
		 Tree1 = tree(Key, Value1)
		 Tree2 = tree(Key, Value2)

	      Maps  the	 function F(K, V1) -> V2 to all	key-value pairs	of the
	      tree Tree1 and returns a new tree	Tree2 with  the	 same  set  of
	      keys as Tree1 and	the new	set of values V2.

       next(Iter1) -> none | {Key, Value, Iter2}

	      Types:

		 Iter1 = Iter2 = iter(Key, Value)

	      Returns  {Key,  Value,  Iter2} where Key is the smallest key re-
	      ferred to	by the iterator	Iter1, and Iter2 is the	 new  iterator
	      to  be used for traversing the remaining nodes, or the atom none
	      if no nodes remain.

       size(Tree) -> integer() >= 0

	      Types:

		 Tree =	tree()

	      Returns the number of nodes in Tree.

       smallest(Tree) -> {Key, Value}

	      Types:

		 Tree =	tree(Key, Value)

	      Returns {Key, Value}, where Key is the smallest key in Tree, and
	      Value  is	 the  value associated with this key. Assumes that the
	      tree is nonempty.

       take_largest(Tree1) -> {Key, Value, Tree2}

	      Types:

		 Tree1 = Tree2 = tree(Key, Value)

	      Returns {Key, Value, Tree2}, where Key is	 the  largest  key  in
	      Tree1, Value is the value	associated with	this key, and Tree2 is
	      this tree	with the corresponding node deleted. Assumes that  the
	      tree is nonempty.

       take_smallest(Tree1) -> {Key, Value, Tree2}

	      Types:

		 Tree1 = Tree2 = tree(Key, Value)

	      Returns  {Key,  Value,  Tree2}, where Key	is the smallest	key in
	      Tree1, Value is the value	associated with	this key, and Tree2 is
	      this  tree with the corresponding	node deleted. Assumes that the
	      tree is nonempty.

       to_list(Tree) ->	[{Key, Value}]

	      Types:

		 Tree =	tree(Key, Value)

	      Converts a tree into an ordered list of key-value	tuples.

       update(Key, Value, Tree1) -> Tree2

	      Types:

		 Tree1 = Tree2 = tree(Key, Value)

	      Updates Key to value Value in Tree1; returns the new  tree.  As-
	      sumes that the key is present in the tree.

       values(Tree) -> [Value]

	      Types:

		 Tree =	tree(Key :: term(), Value)

	      Returns  the  values in Tree as an ordered list, sorted by their
	      corresponding keys. Duplicates are not removed.

SEE ALSO
       gb_sets(3), dict(3)

Ericsson AB			  stdlib 2.4			   gb_trees(3)

NAME | DESCRIPTION | DATA STRUCTURE | DATA TYPES | EXPORTS | SEE ALSO

Want to link to this manual page? Use this URL:
<https://www.freebsd.org/cgi/man.cgi?query=gb_trees&sektion=3&manpath=FreeBSD+12.1-RELEASE+and+Ports>

home | help