1gb_trees(3) Erlang Module Definition gb_trees(3)
2
6 gb_trees - General balanced trees.
7
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 This module considers two keys as different if and only if they do not
14 compare equal (==).
15
17 Trees and iterators are built using opaque data structures that should
18 not be pattern-matched from outside this module.
19 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 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
28 tree(Key, Value)
29 A general balanced tree.
31 tree() = tree(term(), term())
33 iter(Key, Value)
35 A general balanced tree iterator.
37 iter() = iter(term(), term())
39
41 balance(Tree1) -> Tree2
42 Types:
44 Tree1 = Tree2 = tree(Key, Value)
46 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 delete(Key, Tree1) -> Tree2
53 Types:
55 Tree1 = Tree2 = tree(Key, Value)
57 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 delete_any(Key, Tree1) -> Tree2
63 Types:
65 Tree1 = Tree2 = tree(Key, Value)
67 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 take(Key, Tree1) -> {Value, Tree2}
72 Types:
74 Tree1 = Tree2 = tree(Key, term())
76 Key = Value = term()
77 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 take_any(Key, Tree1) -> {Value, Tree2} | error
83 Types:
85 Tree1 = Tree2 = tree(Key, term())
87 Key = Value = term()
88 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 empty() -> tree()
94 Returns a new empty tree.
96 enter(Key, Value, Tree1) -> Tree2
98 Types:
100 Tree1 = Tree2 = tree(Key, Value)
102 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 from_orddict(List) -> Tree
108 Types:
110 List = [{Key, Value}]
112 Tree = tree(Key, Value)
113 Turns an ordered list List of key-value tuples into a tree. The
115 list must not contain duplicate keys.
116 get(Key, Tree) -> Value
118 Types:
120 Tree = tree(Key, Value)
122 Retrieves the value stored with Key in Tree. Assumes that the
124 key is present in the tree, crashes otherwise.
125 insert(Key, Value, Tree1) -> Tree2
127 Types:
129 Tree1 = Tree2 = tree(Key, Value)
131 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 is_defined(Key, Tree) -> boolean()
137 Types:
139 Tree = tree(Key, Value :: term())
141 Returns true if Key is present in Tree, otherwise false.
143 is_empty(Tree) -> boolean()
145 Types:
147 Tree = tree()
149 Returns true if Tree is an empty tree, othwewise false.
151 iterator(Tree) -> Iter
153 Types:
155 Tree = tree(Key, Value)
157 Iter = iter(Key, Value)
158 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 iterator_from(Key, Tree) -> Iter
168 Types:
170 Tree = tree(Key, Value)
172 Iter = iter(Key, Value)
173 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 keys(Tree) -> [Key]
180 Types:
182 Tree = tree(Key, Value :: term())
184 Returns the keys in Tree as an ordered list.
186 largest(Tree) -> {Key, Value}
188 Types:
190 Tree = tree(Key, Value)
192 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 lookup(Key, Tree) -> none | {value, Value}
198 Types:
200 Tree = tree(Key, Value)
202 Looks up Key in Tree. Returns {value, Value}, or none if Key is
204 not present.
205 map(Function, Tree1) -> Tree2
207 Types:
209 Function = fun((K :: Key, V1 :: Value1) -> V2 :: Value2)
211 Tree1 = tree(Key, Value1)
212 Tree2 = tree(Key, Value2)
213 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 next(Iter1) -> none | {Key, Value, Iter2}
219 Types:
221 Iter1 = Iter2 = iter(Key, Value)
223 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 size(Tree) -> integer() >= 0
230 Types:
232 Tree = tree()
234 Returns the number of nodes in Tree.
236 smallest(Tree) -> {Key, Value}
238 Types:
240 Tree = tree(Key, Value)
242 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 take_largest(Tree1) -> {Key, Value, Tree2}
248 Types:
250 Tree1 = Tree2 = tree(Key, Value)
252 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 take_smallest(Tree1) -> {Key, Value, Tree2}
259 Types:
261 Tree1 = Tree2 = tree(Key, Value)
263 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 to_list(Tree) -> [{Key, Value}]
270 Types:
272 Tree = tree(Key, Value)
274 Converts a tree into an ordered list of key-value tuples.
276 update(Key, Value, Tree1) -> Tree2
278 Types:
280 Tree1 = Tree2 = tree(Key, Value)
282 Updates Key to value Value in Tree1 and returns the new tree.
284 Assumes that the key is present in the tree.
285 values(Tree) -> [Value]
287 Types:
289 Tree = tree(Key :: term(), Value)
291 Returns the values in Tree as an ordered list, sorted by their
293 corresponding keys. Duplicates are not removed.
294
296 dict(3), gb_sets(3)
297Ericsson AB stdlib 4.2 gb_trees(3)