1 Binary Tree Package 2 =================== 3 4 Abstract 5 ======== 6 7 This package provides Binary- RedBlack- and AVL-Trees written in Python and Cython. 8 9 This Classes are much slower than the built-in dict class, but all 10 iterators/generators yielding data in sorted key order. 11 12 Source of Algorithms 13 -------------------- 14 15 AVL- and RBTree algorithms taken from Julienne Walker: http://eternallyconfuzzled.com/jsw_home.aspx 16 17 Trees 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 24 Trees 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 31 All trees provides the same API, the pickle protocol is supported. 32 33 FastXTrees has C-structs as tree-node structure and C-implementation for low level 34 operations: insert, remove, get_value, max_item, min_item. 35 36 Constructor 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 43 Methods 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 73 slicing 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 106 prev/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 118 Heap 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 130 Set 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 141 Classmethods 142 ~~~~~~~~~~~~ 143 144 * fromkeys(S[,v]) -> New tree with keys from S and values equal to v. 145 146 Performance 147 =========== 148 149 Profiling with timeit(): 5000 unique random int keys, time in seconds 150 151 ======================== ============= ============== ============== ============== 152 unbalanced Trees CPython 2.7.2 FastBinaryTree ipy 2.7.0 pypy 1.7.0 153 ======================== ============= ============== ============== ============== 154 build time 100x 7,55 0,60 2,51 0,29 155 build & delete time 100x 13,34 1,48 4,45 0,47 156 search 100x all keys 2,86 0,96 0,27 0,06 157 ======================== ============= ============== ============== ============== 158 159 ======================== ============= ============== ============== ============== 160 AVLTrees CPython 2.7.2 FastAVLTree ipy 2.7.0 pypy 1.7.0 161 ======================== ============= ============== ============== ============== 162 build time 100x 22,66 0,65 10,45 1,29 163 build & delete time 100x 36,71 1,47 20,89 3,02 164 search 100x all keys 2,34 0,85 0,89 0,14 165 ======================== ============= ============== ============== ============== 166 167 ======================== ============= ============== ============== ============== 168 RBTrees CPython 2.7.2 FastRBTree ipy 2.7.0 pypy 1.7.0 169 ======================== ============= ============== ============== ============== 170 build time 100x 14,78 0,65 4,43 0,49 171 build & delete time 100x 39,34 1,63 12,43 1,32 172 search 100x all keys 2,32 0,86 0,86 0,13 173 ======================== ============= ============== ============== ============== 174 175 News 176 ==== 177 178 Version 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 189 Version 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 196 Version 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 210 Installation 211 ============ 212 213 from source:: 214 215 python setup.py install 216 217 Download 218 ======== 219 220 http://bitbucket.org/mozman/bintrees/downloads 221 222 Documentation 223 ============= 224 225 this README.txt 226 227 bintrees can be found on bitbucket.org at: 228 229 http://bitbucket.org/mozman/bintrees 230
