1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<!-- This document was generated using DocBuilder 3.3.2 -->
<HTML>
<HEAD>
<TITLE>gb_trees</TITLE>
<SCRIPT type="text/javascript" src="../../../../doc/erlresolvelinks.js">
</SCRIPT>
<STYLE TYPE="text/css">
<!--
.REFBODY { margin-left: 13mm }
.REFTYPES { margin-left: 8mm }
-->
</STYLE>
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#FF00FF"
ALINK="#FF0000">
<!-- refpage -->
<CENTER>
<A HREF="http://www.erlang.se">
<IMG BORDER=0 ALT="[Ericsson AB]" SRC="min_head.gif">
</A>
<H1>gb_trees</H1>
</CENTER>
<H3>MODULE</H3>
<DIV CLASS=REFBODY>
gb_trees
</DIV>
<H3>MODULE SUMMARY</H3>
<DIV CLASS=REFBODY>
General Balanced Trees
</DIV>
<H3>DESCRIPTION</H3>
<DIV CLASS=REFBODY>
<P> An efficient implementation of Prof. Arne Andersson's General
Balanced Trees. These have no storage overhead compared to
unbalaced binary trees, and their performance is in general
better than AVL trees.
</DIV>
<H3>Data structure</H3>
<DIV CLASS=REFBODY>
<P> Data structure:
<PRE>
- {Size, Tree}, where `Tree' is composed of nodes of the form:
- {Key, Value, Smaller, Bigger}, and the "empty tree" node:
- nil.
</PRE>
<P>There is no attempt to balance trees after deletions. Since
deletions don't increase the height of a tree, this should be
OK.
<P> Original balance condition <STRONG>h(T) <= ceil(c * log(|T|))</STRONG>
has been changed to the similar (but not quite equivalent)
condition <STRONG>2 ^ h(T) <= |T| ^ c</STRONG>. This should also be OK.
<P> 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 logaritmic (as it should be).
</DIV>
<H3>EXPORTS</H3>
<P><A NAME="empty/0"><STRONG><CODE>empty()</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns a new, empty tree.
</DIV>
<P><A NAME="is_empty/1"><STRONG><CODE>is_empty(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns 'true' if T is an empty tree, and 'false' otherwise.
</DIV>
<P><A NAME="size/1"><STRONG><CODE>size(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns the number of nodes in the tree as an
integer. Returns 0 (zero) if the tree is empty.
</DIV>
<P><A NAME="lookup/2"><STRONG><CODE>lookup(X, T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Looks up key X in tree T; returns {value, V}, or `none' if
the key is not present.
</DIV>
<P><A NAME="get/2"><STRONG><CODE>get(X, T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Retrieves the value stored with key X in tree T. Assumes
that the key is present in the tree, crashes otherwise.
</DIV>
<P><A NAME="insert/3"><STRONG><CODE>insert(X, V, T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Inserts key X with value V into tree T; returns the new
tree. Assumes that the key is *not* present in the tree,
crashes otherwise.
</DIV>
<P><A NAME="update/3"><STRONG><CODE>update(X, V, T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Updates key X to value V in tree T; returns the new
tree. Assumes that the key is present in the tree.
</DIV>
<P><A NAME="enter/3"><STRONG><CODE>enter(X, V, T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Inserts key X with value V into tree T if the key is not
present in the tree, otherwise updates key X to value V in
T. Returns the new tree.
</DIV>
<P><A NAME="delete/2"><STRONG><CODE>delete(X, T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Removes key X from tree T; returns new tree. Assumes that
the key is present in the tree, crashes otherwise.
</DIV>
<P><A NAME="delete_any/2"><STRONG><CODE>delete_any(X, T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Removes key X from tree T if the key is present in the tree,
otherwise does nothing; returns new tree.
</DIV>
<P><A NAME="balance/1"><STRONG><CODE>balance(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Rebalances tree T. Note that this is rarely necessary, but
may be motivated when a large number of entries 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.
</DIV>
<P><A NAME="is_defined/2"><STRONG><CODE>is_defined(X, T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns `true' if key X is present in tree T, and `false'
otherwise.
</DIV>
<P><A NAME="keys/1"><STRONG><CODE>keys(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns an ordered list of all keys in tree T.
</DIV>
<P><A NAME="values/1"><STRONG><CODE>values(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns the list of values for all keys in tree T,
sorted by their corresponding keys. Duplicates are not removed.
</DIV>
<P><A NAME="to_list/1"><STRONG><CODE>to_list(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns an ordered list of {Key, Value} pairs for all keys
in tree T.
</DIV>
<P><A NAME="from_orddict/1"><STRONG><CODE>from_orddict(L)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Turns an ordered list L of {Key, Value} pairs into a
tree. The list must not contain duplicate keys.
</DIV>
<P><A NAME="smallest/1"><STRONG><CODE>smallest(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns {X, V}, where X is the smallest key in tree T,
and V is the value associated with X in T. Assumes that the tree T
is nonempty.
</DIV>
<P><A NAME="largest/1"><STRONG><CODE>largest(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns {X, V}, where X is the largest key in tree T,
and V is the value associated with X in T. Assumes that the tree T
is nonempty.
</DIV>
<P><A NAME="take_smallest/1"><STRONG><CODE>take_smallest(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns {X, V, T1}, where X is the smallest key in tree T, V
is the value associated with X in T, and T1 is the tree T
with key X deleted. Assumes that the tree T is nonempty.
</DIV>
<P><A NAME="take_largest/1"><STRONG><CODE>take_largest(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns {X, V, T1}, where X is the largest key in tree T, V
is the value associated with X in T, and T1 is the tree T
with key X deleted. Assumes that the tree T is nonempty.
</DIV>
<P><A NAME="iterator/1"><STRONG><CODE>iterator(T)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns an iterator that can be used for traversing the
entries of tree T; see `next'. The implementation of this is
very efficient; traversing the whole tree using `next' is
only slightly slower than getting the list of all elements
using `to_list' 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.
</DIV>
<P><A NAME="next/1"><STRONG><CODE>next(S)</CODE></STRONG></A><BR>
<DIV CLASS=REFBODY>
<P> Returns {X, V, S1} where X is the smallest key referred to
by the iterator S, and S1 is the new iterator to be used for
traversing the remaining entries, or the atom `none' if no
entries remain.
</DIV>
<H3>SEE ALSO</H3>
<DIV CLASS=REFBODY>
<P> <A HREF="gb_sets.html">gb_sets(3)</A>,
<A HREF="dict.html">dict(3)</A>,
</DIV>
<H3>AUTHORS</H3>
<DIV CLASS=REFBODY>
Sven-Olof Nystrom, Richard Carlsson - support@erlang.ericsson.se<BR>
</DIV>
<CENTER>
<HR>
<SMALL>stdlib 1.13.2<BR>
Copyright © 1991-2004
<A HREF="http://www.erlang.se">Ericsson AB</A><BR>
</SMALL>
</CENTER>
</BODY>
</HTML>
|
