红黑树
项目描述
Blackjack是一个简单的红黑树实现，作为Python标准数据结构。包括集合和字典
>>> from blackjack import BJ, Deck >>> bj = BJ() >>> bj BJ([]) >>> bj.add(42) >>> 42 in bj True >>> d = Deck() >>> d[1] = 2 >>> d[3] = 4 >>> d.keys() [1, 3] >>> d.values() [2, 4]
用法
Blackjacks和牌组的行为与正常的Python集合和字典相同，但具有不同的性能特性和对键的要求。所有键都必须可比较，但不必是可哈希的
>>> bj = BJ() >>> bj.add([1]) >>> bj.add([1,2]) >>> bj.add([1,2,3]) >>> bj BJ([[1], [1, 2], [1, 2, 3]])
这会在一定程度上影响异构性，但不应成为大多数常见用途的问题。另一方面，访问、成员测试、插入和删除的平均和最坏情况时间都是对数级别的，这使得blackjacks非常适合存储具有不可信键的数据映射
$ python -mtimeit \ > -s 'l = [(x*(2**64 - 1), hash(x*(2**64 - 1))) for x in xrange(10000)]' \ > 'dict(l)' 10 loops, best of 3: 4.11 sec per loop $ python -mtimeit \ -s 'l = [(x*(2**64 - 1), hash(x*(2**64 - 1))) for x in xrange(10000)] from blackjack import Deck' \ 'Deck(l)' 10 loops, best of 3: 2.07 sec per loop
即使在小型到中型数据集上，blackjacks在面临不可信输入时也迅速成为比字典更有效的选择。
此包仅包含blackjack模块；测试在该模块中，可以使用任何标准测试运行器运行
$ trial blackjack | tail -n1 PASSED (successes=17)
技术信息
使用的特定树是左倾红黑树。如果节点将重新创建，则在平衡过程中会机会性地减少红色子节点；这通常会通过减少红色子节点的数量来缩短整体树的高度。复杂度如下
操作 |
时间 |
空间 |
|---|---|---|
查找 |
O(log n) |
O(1) |
成员资格 |
O(log n) |
O(1) |
插入 |
O(log n) |
O(log n) |
删除 |
O(log n) |
O(log n) |
更新 |
O(log n) |
O(log n) |
排序 |
O(1) |
O(1) |
长度 |
O(1) |
O(1) |
根据提供的键函数排序是常数，因为树的遍历顺序是预排序的。长度在变异时记录和更新。节点是持久的，修改树通常需要以对数空间承诺创建新节点。
关闭
blackjack-1.1.1.tar.gz 的哈希值
| 算法 | 哈希摘要 | |
|---|---|---|
| SHA256 | 9b709b61fc2888f3ab76231c78c1e1642e89f4c67a3e2629481680a8100801e0 |
|
| MD5 | f6ab60d22e93f1d60a8f75688380c91a |
|
| BLAKE2b-256 | bf36fcfea476d0def0fb62d4d65646d4ac6898381018aa99fc847f5cd44a5bc9 |