accumulation-tree

Red/black tree with support for fast accumulation of values in a key range


Keywords
BST, data, structure, accumulation
License
MIT
Install
pip install accumulation-tree==0.6.2

Documentation

accumulation_tree

CircleCI

A red/black tree which also stores partial aggregations at each node, making getting aggregations of key range slices an O(log(N)) operation.

This data structure is very similar to a Fenwick tree and can be used for the same purpose. The main difference with the description on Wikipedia is that we allocate nodes on the heap instead of using an implicit tree structure on a flat array.

This implementation was written specifically for use in tdigest, and borrows code from bintrees.

Synopsis

>>> from accumulation_tree import AccumulationTree
>>> t = AccumulationTree(lambda x: x)
>>> N = 10000
>>> for x in range(N):
...    t.insert(x,x)
>>> t.get_accumulation(0, 2)
1
>>> t.get_accumulation(0, 5)
10
>>> all(t.get_accumulation(0, x) == x*(x-1)/2 for x in range(N))
True