自平衡二叉搜索树
aa-sbst的Python项目详细描述
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
Features:
You can use this module through import instruction or simply copy-paste the implementation into your source code, and be happy.
While instantiating sbst object 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 inclusive parameter is True) or greater (inclusive=False) than specified limit.
- max - returns maximal value that is not greater (if inclusive parameter 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.
Function forward_from returns generator that yields sorted sequence of values starting from a specified value. Function backward_from yields reverse-sorted sequence down from a specified value. These functions have inclusive option 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 forward_from and backward_from generators 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.
Methods add and remove are not thread-safe. Be careful.
Tutorial: [doc/tutorial.md](doc/tutorial.md)
关键词：二叉树 平台：未知 分类器：开发状态：：4-测试版 分类器：目标受众：：开发人员 分类器：目标受众：教育 分类器：主题：：软件开发：：库 分类器：许可证：：CC0 1.0通用（cc01.0）公共域专用 分类器：编程语言：：python：：3 分类器：编程语言：：python：：3.4 分类器：编程语言：：python：：3.5 分类器：编程语言：：python：：3.6 描述内容类型：文本/标记
欢迎加入QQ群-->： 979659372
