1gb_trees(3)                Erlang Module Definition                gb_trees(3)
2
3
4

NAME

6       gb_trees - General balanced trees.
7

DESCRIPTION

9       This  module  provides  Prof.  Arne Andersson's General Balanced Trees.
10       These have no storage overhead compared to unbalanced binary trees, and
11       their performance is better than AVL trees.
12
13       This  module considers two keys as different if and only if they do not
14       compare equal (==).
15

DATA STRUCTURE

17       Trees and iterators are built using opaque data structures that  should
18       not be pattern-matched from outside this module.
19
20       There  is  no attempt to balance trees after deletions. As deletions do
21       not increase the height of a tree, this should be OK.
22
23       The original balance condition h(T) <=  ceil(c  *  log(|T|))  has  been
24       changed to the similar (but not quite equivalent) condition 2 ^ h(T) <=
25       |T| ^ c. This should also be OK.
26

DATA TYPES

28       tree(Key, Value)
29
30              A general balanced tree.
31
32       tree() = tree(term(), term())
33
34       iter(Key, Value)
35
36              A general balanced tree iterator.
37
38       iter() = iter(term(), term())
39

EXPORTS

41       balance(Tree1) -> Tree2
42
43              Types:
44
45                 Tree1 = Tree2 = tree(Key, Value)
46
47              Rebalances Tree1. Notice that this is rarely necessary, but  can
48              be  motivated  when  many  nodes have been deleted from the tree
49              without further insertions. Rebalancing can then  be  forced  to
50              minimize lookup times, as deletion does not rebalance the tree.
51
52       delete(Key, Tree1) -> Tree2
53
54              Types:
55
56                 Tree1 = Tree2 = tree(Key, Value)
57
58              Removes  the  node  with  key Key from Tree1 and returns the new
59              tree. Assumes that the key is present in the tree, crashes  oth‐
60              erwise.
61
62       delete_any(Key, Tree1) -> Tree2
63
64              Types:
65
66                 Tree1 = Tree2 = tree(Key, Value)
67
68              Removes  the  node with key Key from Tree1 if the key is present
69              in the tree, otherwise does nothing. Returns the new tree.
70
71       take(Key, Tree1) -> {Value, Tree2}
72
73              Types:
74
75                 Tree1 = Tree2 = tree(Key, term())
76                 Key = Value = term()
77
78              Returns a value Value from node with key Key and new Tree2 with‐
79              out  the node with this value. Assumes that the node with key is
80              present in the tree, crashes otherwise.
81
82       take_any(Key, Tree1) -> {Value, Tree2} | error
83
84              Types:
85
86                 Tree1 = Tree2 = tree(Key, term())
87                 Key = Value = term()
88
89              Returns a value Value from node with key Key and new Tree2 with‐
90              out the node with this value. Returns error if the node with the
91              key is not present in the tree.
92
93       empty() -> tree()
94
95              Returns a new empty tree.
96
97       enter(Key, Value, Tree1) -> Tree2
98
99              Types:
100
101                 Tree1 = Tree2 = tree(Key, Value)
102
103              Inserts Key with value Value  into  Tree1  if  the  key  is  not
104              present  in  the  tree,  otherwise updates Key to value Value in
105              Tree1. Returns the new tree.
106
107       from_orddict(List) -> Tree
108
109              Types:
110
111                 List = [{Key, Value}]
112                 Tree = tree(Key, Value)
113
114              Turns an ordered list List of key-value tuples into a tree.  The
115              list must not contain duplicate keys.
116
117       get(Key, Tree) -> Value
118
119              Types:
120
121                 Tree = tree(Key, Value)
122
123              Retrieves  the  value  stored with Key in Tree. Assumes that the
124              key is present in the tree, crashes otherwise.
125
126       insert(Key, Value, Tree1) -> Tree2
127
128              Types:
129
130                 Tree1 = Tree2 = tree(Key, Value)
131
132              Inserts Key with value Value into  Tree1  and  returns  the  new
133              tree.  Assumes  that the key is not present in the tree, crashes
134              otherwise.
135
136       is_defined(Key, Tree) -> boolean()
137
138              Types:
139
140                 Tree = tree(Key, Value :: term())
141
142              Returns true if Key is present in Tree, otherwise false.
143
144       is_empty(Tree) -> boolean()
145
146              Types:
147
148                 Tree = tree()
149
150              Returns true if Tree is an empty tree, othwewise false.
151
152       iterator(Tree) -> Iter
153
154              Types:
155
156                 Tree = tree(Key, Value)
157                 Iter = iter(Key, Value)
158
159              Returns an iterator that can be used for traversing the  entries
160              of  Tree;  see  next/1. The implementation of this is very effi‐
161              cient; traversing the whole tree using next/1 is  only  slightly
162              slower than getting the list of all elements using to_list/1 and
163              traversing that. The main advantage of the iterator approach  is
164              that it does not require the complete list of all elements to be
165              built in memory at one time.
166
167       iterator_from(Key, Tree) -> Iter
168
169              Types:
170
171                 Tree = tree(Key, Value)
172                 Iter = iter(Key, Value)
173
174              Returns an iterator that can be used for traversing the  entries
175              of  Tree; see next/1. The difference as compared to the iterator
176              returned by iterator/1 is that the first  key  greater  than  or
177              equal to Key is returned.
178
179       keys(Tree) -> [Key]
180
181              Types:
182
183                 Tree = tree(Key, Value :: term())
184
185              Returns the keys in Tree as an ordered list.
186
187       largest(Tree) -> {Key, Value}
188
189              Types:
190
191                 Tree = tree(Key, Value)
192
193              Returns  {Key, Value}, where Key is the largest key in Tree, and
194              Value is the value associated with this key.  Assumes  that  the
195              tree is not empty.
196
197       lookup(Key, Tree) -> none | {value, Value}
198
199              Types:
200
201                 Tree = tree(Key, Value)
202
203              Looks  up Key in Tree. Returns {value, Value}, or none if Key is
204              not present.
205
206       map(Function, Tree1) -> Tree2
207
208              Types:
209
210                 Function = fun((K :: Key, V1 :: Value1) -> V2 :: Value2)
211                 Tree1 = tree(Key, Value1)
212                 Tree2 = tree(Key, Value2)
213
214              Maps function F(K, V1) -> V2 to  all  key-value  pairs  of  tree
215              Tree1.  Returns  a  new  tree Tree2 with the same set of keys as
216              Tree1 and the new set of values V2.
217
218       next(Iter1) -> none | {Key, Value, Iter2}
219
220              Types:
221
222                 Iter1 = Iter2 = iter(Key, Value)
223
224              Returns {Key, Value, Iter2}, where Key is the smallest  key  re‐
225              ferred to by iterator Iter1, and Iter2 is the new iterator to be
226              used for traversing the remaining nodes, or the atom none if  no
227              nodes remain.
228
229       size(Tree) -> integer() >= 0
230
231              Types:
232
233                 Tree = tree()
234
235              Returns the number of nodes in Tree.
236
237       smallest(Tree) -> {Key, Value}
238
239              Types:
240
241                 Tree = tree(Key, Value)
242
243              Returns {Key, Value}, where Key is the smallest key in Tree, and
244              Value is the value associated with this key.  Assumes  that  the
245              tree is not empty.
246
247       take_largest(Tree1) -> {Key, Value, Tree2}
248
249              Types:
250
251                 Tree1 = Tree2 = tree(Key, Value)
252
253              Returns  {Key,  Value,  Tree2},  where Key is the largest key in
254              Tree1, Value is the value associated with this key, and Tree2 is
255              this  tree with the corresponding node deleted. Assumes that the
256              tree is not empty.
257
258       take_smallest(Tree1) -> {Key, Value, Tree2}
259
260              Types:
261
262                 Tree1 = Tree2 = tree(Key, Value)
263
264              Returns {Key, Value, Tree2}, where Key is the  smallest  key  in
265              Tree1, Value is the value associated with this key, and Tree2 is
266              this tree with the corresponding node deleted. Assumes that  the
267              tree is not empty.
268
269       to_list(Tree) -> [{Key, Value}]
270
271              Types:
272
273                 Tree = tree(Key, Value)
274
275              Converts a tree into an ordered list of key-value tuples.
276
277       update(Key, Value, Tree1) -> Tree2
278
279              Types:
280
281                 Tree1 = Tree2 = tree(Key, Value)
282
283              Updates  Key  to  value Value in Tree1 and returns the new tree.
284              Assumes that the key is present in the tree.
285
286       values(Tree) -> [Value]
287
288              Types:
289
290                 Tree = tree(Key :: term(), Value)
291
292              Returns the values in Tree as an ordered list, sorted  by  their
293              corresponding keys. Duplicates are not removed.
294

SEE ALSO

296       dict(3), gb_sets(3)
297
298
299
300Ericsson AB                     stdlib 4.3.1.3                     gb_trees(3)
Impressum