Skip to content

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

License

Notifications You must be signed in to change notification settings

tkluck/accumulation_tree

Repository files navigation

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

About

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

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages