Pure Python implementation of self-balancing binary search tree (SBST)
There is no implemenation of SBST in Standard Python Library, and I found it quite inconvenient and a little bit disappointing.
This is a compact, portable (no dependencies) and extremely easy-to-use implementation of self-balancing binary search tree. This particular type of trees (so called AA-tree) is described here: https://en.wikipedia.org/wiki/AA_tree
- You can use this module through
importinstruction or simply copy-paste the implementation into your source code, and be happy.
- While instantiating
sbstobject you can specify your own comparison function or use default simple comparison.
- You can add values to tree one-by-one using function
add, or fill it from some iterable object (function
addfrom). Either initialization in constructor is possible.
- The tree stores all duplicates. This feature is vital if the tree is an index for in-memory table.
- This SBST gives you two basic search operations:
min- returns minimal value that is not less (if
inclusiveparameter is True) or greater (inclusive=False) than specified limit.
max- returns maximal value that is not greater (if
inclusiveparameter is True) or less (inclusive=False) than specified limit. If you have not specified limit, functions return respectively minimal or maximal value in the tree.
forward_fromreturns generator that yields sorted sequence of values starting from a specified value. Function
backward_fromyields reverse-sorted sequence down from a specified value. These functions have
inclusiveoption too. If starting value is not specified, these functions yield respectively sorted or reverse-sorted sequences of all values in the tree. If tree modified while iterating (some values inserted, some removed, tree rebalanced), sequence will be yielded in right predictable way.
- If comparison function treats values as equal, they will be yielded by
backward_fromgenerators in the insertion order.
- Do not store None values into tree. Even if your comparison function can process them, you will not be able to search them because None value will be treated as 'not specified'.
- If mutable objects inserted into the tree are changed, their sequence in tree may become irrelevant. So after value mutation it is a good idea to remove it from tree and add again.
removeare not thread-safe. Be careful.