1Binary Tree Package
2===================
3
4Abstract
5========
6
7This package provides Binary- RedBlack- and AVL-Trees written in Python and Cython.
8
9This Classes are much slower than the built-in dict class, but all
10iterators/generators yielding data in sorted key order.
11
12Source of Algorithms
13--------------------
14
15AVL- and RBTree algorithms taken from Julienne Walker: http://eternallyconfuzzled.com/jsw_home.aspx
16
17Trees written in Python (only standard library)
18-----------------------------------------------
19
20 - *BinaryTree* -- unbalanced binary tree
21 - *AVLTree* -- balanced AVL-Tree
22 - *RBTree* -- balanced Red-Black-Tree
23
24Trees written with C-Functions and Cython as wrapper
25----------------------------------------------------
26
27 - *FastBinaryTree* -- unbalanced binary tree
28 - *FastAVLTree* -- balanced AVL-Tree
29 - *FastRBTree* -- balanced Red-Black-Tree
30
31All trees provides the same API, the pickle protocol is supported.
32
33FastXTrees has C-structs as tree-node structure and C-implementation for low level
34operations: insert, remove, get_value, max_item, min_item.
35
36Constructor
37~~~~~~~~~~~
38
39 * Tree() -> new empty tree;
40 * Tree(mapping) -> new tree initialized from a mapping (requires only an items() method)
41 * Tree(seq) -> new tree initialized from seq [(k1, v1), (k2, v2), ... (kn, vn)]
42
43Methods
44~~~~~~~
45
46 * __contains__(k) -> True if T has a key k, else False, O(log(n))
47 * __delitem__(y) <==> del T[y], del[s:e], O(log(n))
48 * __getitem__(y) <==> T[y], T[s:e], O(log(n))
49 * __iter__() <==> iter(T)
50 * __len__() <==> len(T), O(1)
51 * __max__() <==> max(T), get max item (k,v) of T, O(log(n))
52 * __min__() <==> min(T), get min item (k,v) of T, O(log(n))
53 * __and__(other) <==> T & other, intersection
54 * __or__(other) <==> T | other, union
55 * __sub__(other) <==> T - other, difference
56 * __xor__(other) <==> T ^ other, symmetric_difference
57 * __repr__() <==> repr(T)
58 * __setitem__(k, v) <==> T[k] = v, O(log(n))
59 * clear() -> None, remove all items from T, O(n)
60 * copy() -> a shallow copy of T, O(n*log(n))
61 * discard(k) -> None, remove k from T, if k is present, O(log(n))
62 * get(k[,d]) -> T[k] if k in T, else d, O(log(n))
63 * is_empty() -> True if len(T) == 0, O(1)
64 * items([reverse]) -> generator for (k, v) items of T, O(n)
65 * keys([reverse]) -> generator for keys of T, O(n)
66 * values([reverse]) -> generator for values of T, O(n)
67 * pop(k[,d]) -> v, remove specified key and return the corresponding value, O(log(n))
68 * popitem() -> (k, v), remove and return some (key, value) pair as a 2-tuple, O(log(n))
69 * setdefault(k[,d]) -> T.get(k, d), also set T[k]=d if k not in T, O(log(n))
70 * update(E) -> None. Update T from dict/iterable E, O(E*log(n))
71 * foreach(f, [order]) -> visit all nodes of tree (0 = 'inorder', -1 = 'preorder' or +1 = 'postorder') and call f(k, v) for each node, O(n)
72
73slicing by keys
74~~~~~~~~~~~~~~~
75
76 * itemslice(s, e) -> generator for (k, v) items of T for s <= key < e, O(n)
77 * keyslice(s, e) -> generator for keys of T for s <= key < e, O(n)
78 * valueslice(s, e) -> generator for values of T for s <= key < e, O(n)
79 * T[s:e] -> TreeSlice object, with keys in range s <= key < e, O(n)
80 * del T[s:e] -> remove items by key slicing, for s <= key < e, O(n)
81
82 start/end parameter:
83
84 * if 's' is None or T[:e] TreeSlice/iterator starts with value of min_key();
85 * if 'e' is None or T[s:] TreeSlice/iterator ends with value of max_key();
86 * T[:] is a TreeSlice which represents the whole tree;
87
88 TreeSlice is a tree wrapper with range check, and contains no references
89 to objects, deleting objects in the associated tree also deletes the object
90 in the TreeSlice.
91
92 * TreeSlice[k] -> get value for key k, raises KeyError if k not exists in range s:e
93 * TreeSlice[s1:e1] -> TreeSlice object, with keys in range s1 <= key < e1
94 - new lower bound is max(s, s1)
95 - new upper bound is min(e, e1)
96
97 TreeSlice methods:
98
99 * items() -> generator for (k, v) items of T, O(n)
100 * keys() -> generator for keys of T, O(n)
101 * values() -> generator for values of T, O(n)
102 * __iter__ <==> keys()
103 * __repr__ <==> repr(T)
104 * __contains__(key)-> True if TreeSlice has a key k, else False, O(log(n))
105
106prev/succ operations
107~~~~~~~~~~~~~~~~~~~~
108
109 * prev_item(key) -> get (k, v) pair, where k is predecessor to key, O(log(n))
110 * prev_key(key) -> k, get the predecessor of key, O(log(n))
111 * succ_item(key) -> get (k,v) pair as a 2-tuple, where k is successor to key, O(log(n))
112 * succ_key(key) -> k, get the successor of key, O(log(n))
113 * floor_item(key) -> get (k, v) pair, where k is the greatest key less than or equal to key, O(log(n))
114 * floor_key(key) -> k, get the greatest key less than or equal to key, O(log(n))
115 * ceiling_item(key) -> get (k, v) pair, where k is the smallest key greater than or equal to key, O(log(n))
116 * ceiling_key(key) -> k, get the smallest key greater than or equal to key, O(log(n))
117
118Heap methods
119~~~~~~~~~~~~
120
121 * max_item() -> get largest (key, value) pair of T, O(log(n))
122 * max_key() -> get largest key of T, O(log(n))
123 * min_item() -> get smallest (key, value) pair of T, O(log(n))
124 * min_key() -> get smallest key of T, O(log(n))
125 * pop_min() -> (k, v), remove item with minimum key, O(log(n))
126 * pop_max() -> (k, v), remove item with maximum key, O(log(n))
127 * nlargest(i[,pop]) -> get list of i largest items (k, v), O(i*log(n))
128 * nsmallest(i[,pop]) -> get list of i smallest items (k, v), O(i*log(n))
129
130Set methods (using frozenset)
131~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
132
133 * intersection(t1, t2, ...) -> Tree with keys *common* to all trees
134 * union(t1, t2, ...) -> Tree with keys from *either* trees
135 * difference(t1, t2, ...) -> Tree with keys in T but not any of t1, t2, ...
136 * symmetric_difference(t1) -> Tree with keys in either T and t1 but not both
137 * issubset(S) -> True if every element in T is in S
138 * issuperset(S) -> True if every element in S is in T
139 * isdisjoint(S) -> True if T has a null intersection with S
140
141Classmethods
142~~~~~~~~~~~~
143
144 * fromkeys(S[,v]) -> New tree with keys from S and values equal to v.
145
146Performance
147===========
148
149Profiling with timeit(): 5000 unique random int keys, time in seconds
150
151======================== ============= ============== ============== ==============
152unbalanced Trees CPython 2.7.2 FastBinaryTree ipy 2.7.0 pypy 1.7.0
153======================== ============= ============== ============== ==============
154build time 100x 7,55 0,60 2,51 0,29
155build & delete time 100x 13,34 1,48 4,45 0,47
156search 100x all keys 2,86 0,96 0,27 0,06
157======================== ============= ============== ============== ==============
158
159======================== ============= ============== ============== ==============
160AVLTrees CPython 2.7.2 FastAVLTree ipy 2.7.0 pypy 1.7.0
161======================== ============= ============== ============== ==============
162build time 100x 22,66 0,65 10,45 1,29
163build & delete time 100x 36,71 1,47 20,89 3,02
164search 100x all keys 2,34 0,85 0,89 0,14
165======================== ============= ============== ============== ==============
166
167======================== ============= ============== ============== ==============
168RBTrees CPython 2.7.2 FastRBTree ipy 2.7.0 pypy 1.7.0
169======================== ============= ============== ============== ==============
170build time 100x 14,78 0,65 4,43 0,49
171build & delete time 100x 39,34 1,63 12,43 1,32
172search 100x all keys 2,32 0,86 0,86 0,13
173======================== ============= ============== ============== ==============
174
175News
176====
177
178Version 1.0.1 February 2013
179
180 * bug fixes
181 * refactorings by graingert
182 * skip useless tests for pypy
183 * new license: MIT License
184 * tested with CPython2.7, CPython3.2, CPython3.3, pypy-1.9, pypy-2.0-beta1
185 * unified line endings to LF
186 * PEP8 refactorings
187 * added floor_item/key, ceiling_item/key methods, thanks to Dai Mikurube
188
189Version 1.0.0
190
191 * bug fixes
192 * status: 5 - Production/Stable
193 * removed useless TreeIterator() class and T.treeiter() method.
194 * patch from Max Motovilov to use Visual Studio 2008 for building C-extensions
195
196Version 0.4.0
197
198 * API change!!!
199 * full Python 3 support, also for Cython implementations
200 * removed user defined compare() function - keys have to be comparable!
201 * removed T.has_key(), use 'key in T'
202 * keys(), items(), values() generating 'views'
203 * removed iterkeys(), itervalues(), iteritems() methods
204 * replaced index slicing by key slicing
205 * removed index() and item_at()
206 * repr() produces a correct representation
207 * installs on systems without cython (tested with pypy)
208 * new license: GNU Library or Lesser General Public License (LGPL)
209
210Installation
211============
212
213from source::
214
215 python setup.py install
216
217Download
218========
219
220http://bitbucket.org/mozman/bintrees/downloads
221
222Documentation
223=============
224
225this README.txt
226
227bintrees can be found on bitbucket.org at:
228
229http://bitbucket.org/mozman/bintrees
230