👤
Home Man
Search
Today's Posts
Register

Linux & Unix Commands - Search Man Pages
Man Page or Keyword Search:
Select Section of Man Page:
Select Man Page Repository:

Linux 2.6 - man page for gb_trees (linux section 3erl)

gb_trees(3erl)			     Erlang Module Definition			   gb_trees(3erl)

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  gen-
       eral 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 deletion works for these trees, but not for the
       book's trees. Behaviour is logarithmic (as it should be).

DATA TYPES
       gb_tree() = a GB tree

EXPORTS
       balance(Tree1) -> Tree2

	      Types  Tree1 = Tree2 = gb_tree()

	      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  Key = term()
		     Tree1 = Tree2 = gb_tree()

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

       delete_any(Key, Tree1) -> Tree2

	      Types  Key = term()
		     Tree1 = Tree2 = gb_tree()

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

       empty() -> Tree

	      Types  Tree = gb_tree()

	      Returns a new empty tree

       enter(Key, Val, Tree1) -> Tree2

	      Types  Key = Val = term()
		     Tree1 = Tree2 = gb_tree()

	      Inserts Key with value Val into Tree1 if the key is not present in the tree, other-
	      wise updates Key to value Val in Tree1 . Returns the new tree.

       from_orddict(List) -> Tree

	      Types  List = [{Key, Val}]
		     Key = Val = term()
		     Tree = gb_tree()

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

       get(Key, Tree) -> Val

	      Types  Key = Val = term()
		     Tree = gb_tree()

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

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

	      Types  Key = Val = term()
		     Tree = gb_tree()

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

       insert(Key, Val, Tree1) -> Tree2

	      Types  Key = Val = term()
		     Tree1 = Tree2 = gb_tree()

	      Inserts Key with value Val into Tree1 ; returns the new tree. Assumes that the  key
	      is not present in the tree, crashes otherwise.

       is_defined(Key, Tree) -> bool()

	      Types  Tree = gb_tree()

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

       is_empty(Tree) -> bool()

	      Types  Tree = gb_tree()

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

       iterator(Tree) -> Iter

	      Types  Tree = gb_tree()
		     Iter = term()

	      Returns  an  iterator  that  can	be  used for traversing the entries of Tree ; see
	      next/1 . The implementation of this is very efficient; 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 = gb_tree()
		     Key = term()

	      Returns the keys in Tree as an ordered list.

       largest(Tree) -> {Key, Val}

	      Types  Tree = gb_tree()
		     Key = Val = term()

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

       map(Function, Tree1) -> Tree2

	      Types  Function = fun(K, V1) -> V2
		     Tree1 = Tree2 = gb_tree()

	      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 val-
	      ues V2.

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

	      Types  Iter1 = Iter2 = Key = Val = term()

	      Returns {Key, Val, Iter2} where Key is the smallest key referred 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) -> int()

	      Types  Tree = gb_tree()

	      Returns the number of nodes in Tree .

       smallest(Tree) -> {Key, Val}

	      Types  Tree = gb_tree()
		     Key = Val = term()

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

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

	      Types  Tree1 = Tree2 = gb_tree()
		     Key = Val = term()

	      Returns {Key, Val, Tree2} , where Key is the largest key in  Tree1  ,  Val  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, Val, Tree2}

	      Types  Tree1 = Tree2 = gb_tree()
		     Key = Val = term()

	      Returns {Key, Val, Tree2} , where Key is the smallest key in Tree1  ,  Val  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, Val}]

	      Types  Tree = gb_tree()
		     Key = Val = term()

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

       update(Key, Val, Tree1) -> Tree2

	      Types  Key = Val = term()
		     Tree1 = Tree2 = gb_tree()

	      Updates Key to value Val in Tree1 ; returns the new tree. Assumes that the  key  is
	      present in the tree.

       values(Tree) -> [Val]

	      Types  Tree = gb_tree()
		     Val = term()

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

SEE ALSO
       gb_sets(3erl) , dict(3erl)

Ericsson AB				  stdlib 1.17.3 			   gb_trees(3erl)


All times are GMT -4. The time now is 07:07 AM.

Unix & Linux Forums Content Copyrightę1993-2018. All Rights Reserved.
×
UNIX.COM Login
Username:
Password:  
Show Password





Not a Forum Member?
Forgot Password?