红黑树
blackjack的Python项目详细描述
21点是经典红黑树的简单实现 标准的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和deck的行为就像普通的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)
技术信息
使用的具体树木是左倾的红黑树木。红孩子是 如果节点无论如何都要重新创建，则在平衡过程中机会减少； 这会通过减少红色的数量来缩短整个树的高度 孩子们。复杂性如下：
| Operation | Time | Space |
|---|---|---|
| Lookup | O(log n) | O(1) |
| Membership | O(log n) | O(1) |
| Insertion | O(log n) | O(log n) |
| Deletion | O(log n) | O(log n) |
| Update | O(log n) | O(log n) |
| Sort | O(1) | O(1) |
| Length | O(1) | O(1) |
根据提供的键函数排序是常量，因为树的 遍历顺序是预先排序的。记录长度，并在突变时更新。 节点是持久的，改变树通常需要对数。 创建新节点的空间承诺。
欢迎加入QQ群-->： 979659372
