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       {Size, Tree}
18
19       Tree is composed of nodes of the form {Key, Value, Smaller, Bigger} and
20       the "empty tree" node nil.
21
22       There  is  no attempt to balance trees after deletions. As deletions do
23       not increase the height of a tree, this should be OK.
24
25       The original balance condition h(T) <=  ceil(c  *  log(|T|))  has  been
26       changed to the similar (but not quite equivalent) condition 2 ^ h(T) <=
27       |T| ^ c. This should also be OK.
28

DATA TYPES

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

EXPORTS

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

SEE ALSO

298       dict(3), gb_sets(3)
299
300
301
302Ericsson AB                     stdlib 3.8.2.1                     gb_trees(3)
Impressum