Package provides Binary-, RedBlack- and AVL-Trees in Python and Cython.
Project description
Binary Tree Package
Bintrees Development Stopped
Use sortedcontainers instead: https://pypi.python.org/pypi/sortedcontainers
see also PyCon 2016 presentation: https://www.youtube.com/watch?v=7z2Ki44Vs4E
Advantages:
pure Python no Cython/C dependencies
faster
active development
more & better testing/profiling
Abstract
This package provides Binary- RedBlack- and AVL-Trees written in Python and Cython/C.
This Classes are much slower than the built-in dict class, but all iterators/generators yielding data in sorted key order. Trees can be uses as drop in replacement for dicts in most cases.
Source of Algorithms
AVL- and RBTree algorithms taken from Julienne Walker: http://eternallyconfuzzled.com/jsw_home.aspx
Trees written in Python
BinaryTree – unbalanced binary tree
AVLTree – balanced AVL-Tree
RBTree – balanced Red-Black-Tree
Trees written with C-Functions and Cython as wrapper
FastBinaryTree – unbalanced binary tree
FastAVLTree – balanced AVL-Tree
FastRBTree – balanced Red-Black-Tree
All trees provides the same API, the pickle protocol is supported.
Cython-Trees have C-structs as tree-nodes and C-functions for low level operations:
insert
remove
get_value
min_item
max_item
prev_item
succ_item
floor_item
ceiling_item
Constructor
Tree() -> new empty tree;
Tree(mapping) -> new tree initialized from a mapping (requires only an items() method)
Tree(seq) -> new tree initialized from seq [(k1, v1), (k2, v2), … (kn, vn)]
Methods
__contains__(k) -> True if T has a key k, else False, O(log(n))
__delitem__(y) <==> del T[y], del[s:e], O(log(n))
__getitem__(y) <==> T[y], T[s:e], O(log(n))
__iter__() <==> iter(T)
__len__() <==> len(T), O(1)
__max__() <==> max(T), get max item (k,v) of T, O(log(n))
__min__() <==> min(T), get min item (k,v) of T, O(log(n))
__and__(other) <==> T & other, intersection
__or__(other) <==> T | other, union
__sub__(other) <==> T - other, difference
__xor__(other) <==> T ^ other, symmetric_difference
__repr__() <==> repr(T)
__setitem__(k, v) <==> T[k] = v, O(log(n))
clear() -> None, remove all items from T, O(n)
copy() -> a shallow copy of T, O(n*log(n))
discard(k) -> None, remove k from T, if k is present, O(log(n))
get(k[,d]) -> T[k] if k in T, else d, O(log(n))
is_empty() -> True if len(T) == 0, O(1)
items([reverse]) -> generator for (k, v) items of T, O(n)
keys([reverse]) -> generator for keys of T, O(n)
values([reverse]) -> generator for values of T, O(n)
pop(k[,d]) -> v, remove specified key and return the corresponding value, O(log(n))
pop_item() -> (k, v), remove and return some (key, value) pair as a 2-tuple, O(log(n)) (synonym popitem() exist)
set_default(k[,d]) -> value, T.get(k, d), also set T[k]=d if k not in T, O(log(n)) (synonym setdefault() exist)
update(E) -> None. Update T from dict/iterable E, O(E*log(n))
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)
iter_items(s, e[, reverse]) -> generator for (k, v) items of T for s <= key < e, O(n)
remove_items(keys) -> None, remove items by keys, O(n)
slicing by keys
item_slice(s, e[, reverse]) -> generator for (k, v) items of T for s <= key < e, O(n), synonym for iter_items(…)
key_slice(s, e[, reverse]) -> generator for keys of T for s <= key < e, O(n)
value_slice(s, e[, reverse]) -> generator for values of T for s <= key < e, O(n)
T[s:e] -> TreeSlice object, with keys in range s <= key < e, O(n)
del T[s:e] -> remove items by key slicing, for s <= key < e, O(n)
start/end parameter:
if ‘s’ is None or T[:e] TreeSlice/iterator starts with value of min_key();
if ‘e’ is None or T[s:] TreeSlice/iterator ends with value of max_key();
T[:] is a TreeSlice which represents the whole tree;
The step argument of the regular slicing syntax T[s:e:step] will silently ignored.
TreeSlice is a tree wrapper with range check and contains no references to objects, deleting objects in the associated tree also deletes the object in the TreeSlice.
TreeSlice[k] -> get value for key k, raises KeyError if k not exists in range s:e
- TreeSlice[s1:e1] -> TreeSlice object, with keys in range s1 <= key < e1
new lower bound is max(s, s1)
new upper bound is min(e, e1)
TreeSlice methods:
items() -> generator for (k, v) items of T, O(n)
keys() -> generator for keys of T, O(n)
values() -> generator for values of T, O(n)
__iter__ <==> keys()
__repr__ <==> repr(T)
__contains__(key)-> True if TreeSlice has a key k, else False, O(log(n))
prev/succ operations
prev_item(key) -> get (k, v) pair, where k is predecessor to key, O(log(n))
prev_key(key) -> k, get the predecessor of key, O(log(n))
succ_item(key) -> get (k,v) pair as a 2-tuple, where k is successor to key, O(log(n))
succ_key(key) -> k, get the successor of key, O(log(n))
floor_item(key) -> get (k, v) pair, where k is the greatest key less than or equal to key, O(log(n))
floor_key(key) -> k, get the greatest key less than or equal to key, O(log(n))
ceiling_item(key) -> get (k, v) pair, where k is the smallest key greater than or equal to key, O(log(n))
ceiling_key(key) -> k, get the smallest key greater than or equal to key, O(log(n))
Heap methods
max_item() -> get largest (key, value) pair of T, O(log(n))
max_key() -> get largest key of T, O(log(n))
min_item() -> get smallest (key, value) pair of T, O(log(n))
min_key() -> get smallest key of T, O(log(n))
pop_min() -> (k, v), remove item with minimum key, O(log(n))
pop_max() -> (k, v), remove item with maximum key, O(log(n))
nlargest(i[,pop]) -> get list of i largest items (k, v), O(i*log(n))
nsmallest(i[,pop]) -> get list of i smallest items (k, v), O(i*log(n))
Set methods (using frozenset)
intersection(t1, t2, …) -> Tree with keys common to all trees
union(t1, t2, …) -> Tree with keys from either trees
difference(t1, t2, …) -> Tree with keys in T but not any of t1, t2, …
symmetric_difference(t1) -> Tree with keys in either T and t1 but not both
is_subset(S) -> True if every element in T is in S (synonym issubset() exist)
is_superset(S) -> True if every element in S is in T (synonym issuperset() exist)
is_disjoint(S) -> True if T has a null intersection with S (synonym isdisjoint() exist)
Classmethods
from_keys(S[,v]) -> New tree with keys from S and values equal to v. (synonym fromkeys() exist)
Helper functions
bintrees.has_fast_tree_support() -> True if Cython extension is working else False (False = using pure Python implementation)
Installation
from source:
python setup.py install
or from PyPI:
pip install bintrees
Compiling the fast Trees requires Cython and on Windows is a C-Compiler necessary.
Download Binaries for Windows
Documentation
this README.rst
bintrees can be found on GitHub.com at:
NEWS
bintrees development stopped, use sortedcontainers instead: https://pypi.python.org/pypi/sortedcontainers
Repository moved to GitHub: https://github.com/mozman/bintrees.git
Version 2.0.4 - 2016-01-09
removed logging statements on import
added helper function bintrees.has_fast_tree_support()
HINT: pypy runs faster than CPython with Cython extension
Version 2.0.3 - 2016-01-06
replaced print function by logging.warning for import warning messages
KNOWN ISSUE: unable to build Cython extension with MingW32 and CPython 3.5 & CPython 2.7.10
Version 2.0.2 - 2015-02-12
fixed foreach cython-function by Sam Yaple
Version 2.0.1 - 2013-10-01
removed __del__() method to avoid problems with garbage collection
Version 2.0.0 - 2013-06-01
API change: consistent method naming with synonyms for dict/set compatibility
code base refactoring
removed tree walkers
removed low level node stack implementation -> caused crashes
optimizations for pypy: iter_items(), succ_item(), prev_item()
tested with CPython2.7, CPython3.3, pypy-2.0 on Win7 and Linux Mint 15 x64 (pypy-1.9)
Version 1.0.3 - 2013-05-01
extended iter_items(startkey=None, endkey=None, reverse=reverse) -> better performance for slicing
Cython implementation of iter_items() for Fast_X_Trees()
added key parameter reverse to itemslice(), keyslice(), valueslice()
tested with CPython2.7, CPython3.3, pypy-2.0
Version 1.0.2 - 2013-04-01
bug fix: FastRBTree data corruption on inserting existing keys
bug fix: union & symmetric_difference - copy all values to result tree
Version 1.0.1 - 2013-02-01
bug fixes
refactorings by graingert
skip useless tests for pypy
new license: MIT License
tested with CPython2.7, CPython3.2, CPython3.3, pypy-1.9, pypy-2.0-beta1
unified line endings to LF
PEP8 refactorings
added floor_item/key, ceiling_item/key methods, thanks to Dai Mikurube
Version 1.0.0 - 2011-12-29
bug fixes
status: 5 - Production/Stable
removed useless TreeIterator() class and T.treeiter() method.
patch from Max Motovilov to use Visual Studio 2008 for building C-extensions
Version 0.4.0 - 2011-04-14
API change!!!
full Python 3 support, also for Cython implementations
removed user defined compare() function - keys have to be comparable!
removed T.has_key(), use ‘key in T’
keys(), items(), values() generating ‘views’
removed iterkeys(), itervalues(), iteritems() methods
replaced index slicing by key slicing
removed index() and item_at()
repr() produces a correct representation
installs on systems without cython (tested with pypy)
new license: GNU Library or Lesser General Public License (LGPL)
Version 0.3.2 - 2011-04-09
added itemslice(startkey, endkey), keyslice(startkey, endkey), valueslice(startkey, endkey) - slicing by keys
tested with pypy 1.4.1, damn fast
Pure Python trees are working with Python 3
No Cython implementation for Python 3
Version 0.3.1 - 2010-09-10
runs with Python 2.7
Version 0.3.0 - 2010-05-11
low level functions written as c-module only interface to python is a cython module
support for the pickle protocol
Version 0.2.1 - 2010-05-06
added delslice del T[0:3] -> remove treenodes 0, 1, 2
added discard -> remove key without KeyError if not found
added heap methods: min, max, nlarges, nsmallest …
added Set methods -> intersection, differnce, union, …
- added slicing: T[5:10] get items with position (not key!) 5, 6, 7, 8, 9
T[5] get item with key! 5
added index: T.index(key) -> get position of item <key>
- added item_at: T.item_at(0) -> get item at position (not key!) 0
T.item_at(0) O(n)! <==> T.min_item() O(log(n))
Version 0.2.0 - 2010-05-03
TreeMixin Class as base for Python-Trees and as Mixin for Cython-Trees
Version 0.1.0 - 2010-04-27
Alpha status
Initial release
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for bintrees-2.0.4.win-amd64-py3.6.exe
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5b6424b6969f43e579baa5bfae664dce56de574a56cfc88909ed48e1eaf54d77 |
|
MD5 | f9d1be2a2cbbe447f2869c29c8fa51d5 |
|
BLAKE2b-256 | ec197227b60e2a97998c72873c517987b6751783192fb31a082ff0f4b6a0c1c5 |
Hashes for bintrees-2.0.4.win-amd64-py3.5.exe
Algorithm | Hash digest | |
---|---|---|
SHA256 | a606f145104da98a730528a04664bc0d0a40fc444c3717615259dee2dd973505 |
|
MD5 | c14b1c3f2d36477387654eb4e5e9f318 |
|
BLAKE2b-256 | 6c040d21c7185be41102b48666c727bf5ce61f355c3c80b8c5eb75071d3037e4 |
Hashes for bintrees-2.0.4.win-amd64-py2.7.exe
Algorithm | Hash digest | |
---|---|---|
SHA256 | cf41a2298477b272c236a66f6afdf81098b5c9485958168cfb989a878bc21509 |
|
MD5 | 8813ad6e1d031dd41af488ce38a0ddc0 |
|
BLAKE2b-256 | 64e77aca0395c7f3ad6b69a2ab924a1953cb076a84781deb00cdb7ef066787cc |
Hashes for bintrees-2.0.4-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7a1b8b64b8b9c2475b4fbd8dbe6a68c79fa6c591d57d3bb978eb1edb1760217d |
|
MD5 | 9bcd8547ed429d5fe290a68ed633f758 |
|
BLAKE2b-256 | d059b92beb84038a20fe6c54e53f0658bffb5f806bfdf7abea0d41938cdbdecc |
Hashes for bintrees-2.0.4-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2377a669a08a04c2188363b687b0fdcb00254104deb602b28e788e6aedac5655 |
|
MD5 | 13482a727e66d78156dcd70b41aa04f9 |
|
BLAKE2b-256 | a57ddf3a51160cd9e7fd641c094c0a94a74296917b6d46942e6830962dca0ea7 |
Hashes for bintrees-2.0.4-cp35-none-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0ca15f299c8bb5576df8ecaa14fd47a6dacf07ceb0aabb4213d15f295d3ea22d |
|
MD5 | 7a27229646375fdece99dba83f8bd3f9 |
|
BLAKE2b-256 | bef10d435599781583e5d25d6709e69021573ab50974669382db7cc463d1d193 |
Hashes for bintrees-2.0.4-cp35-cp35m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 77508d3430d567d10a1663bef5fd1ca691ea97affee4864ee581b56bd1de9b66 |
|
MD5 | 486782d2be6cf59838cc95cf686eccde |
|
BLAKE2b-256 | 209e83413cedf30f380c2e3da1102ba7529277cc22daf5a917e26e0778361b01 |
Hashes for bintrees-2.0.4-cp34-none-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9af98ae13c2f6a298893d174a2f98e9d92ab7faf32b900105f5bafb0f3c27454 |
|
MD5 | 7f419b81abe27bbcfeb36e8be4f49327 |
|
BLAKE2b-256 | e739ccc0b7d6f392919083d1d7732d124e0a53540e63edb6ecbdaac411750ad7 |
Hashes for bintrees-2.0.4-cp27-none-win32.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d81a147e0730c6b605c0ccd3e3d9bec494512e4ee47321aa1b8084cc1fb820cb |
|
MD5 | c9f6281aab9bc6375079e8e9c4c49323 |
|
BLAKE2b-256 | 53d2f615cd98a4a9f64999e2a2b681fc51c3352d0ecce017de9bd8574ddbeaf0 |
Hashes for bintrees-2.0.4-cp27-cp27m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b6cefb01ea7097fd9941a65c95170c80c7621c170a54003dd92761beff6f96aa |
|
MD5 | 990aa4847e466b9352a05e93102156be |
|
BLAKE2b-256 | 67607ef68f0d7d1985a287eeef7224c9104a7d9b8153290af493c2a8993be3f9 |