#
Python
#
Pythonpython
python
- BinaryTree
- AVLTreeAVL
- RBTree
pythoncCython
- FastBinaryTree
- FastAVLTree
- FastRBTree
**pythondict**
#
##
###
ubuntu12.04, python 2.7.6
###
- https://bitbucket.org/mozman/bintrees/src
- setup.py
python setup.py install
ok!
###
bintreesAPI,
-
>>> import bintrees
(
Warning: FastBinaryTree not available, using Python version BinaryTree.
Warning: FastAVLTree not available, using Python version AVLTree.
Warning: FastRBTree not available, using Python version RBTree.
>>> from bintrees import BinaryTree #BinartTree
>>> from bintrees import * #
-
>>> btree = BinaryTree()
>>> btree
BinaryTree({})
>>> type(btree)
- .__setitem__(k,v) .O(log(n))(O(log(n)).)
>>> btree.__setitem__("Tom","headmaster")
>>> btree
BinaryTree({'Tom': 'headmaster'})
>>> btree.__setitem__("blog","http://blog.csdn.net/qiwsir")
>>> btree
BinaryTree({'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
- .update(E) Edict/iterableEbtree. O(E*log(n))
>>> adict = [(2,"phone"),(5,"tea"),(9,"scree"),(7,"computer")]
>>> btree.update(adict)
>>> btree
BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
- key.__contains__(k) kTrue,False. O(log(n))
>>> btree
BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
>>> btree.__contains__(5)
True
>>> btree.__contains__("blog")
True
>>> btree.__contains__("qiwsir")
False
>>> btree.__contains__(1)
False
- keykey-value.__delitem__(key), O(log(n))
>>> btree
BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
>>> btree.__delitem__(5) #key=5key-value,5:'tea' .
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
- keykyevalue.__getitem__(key)
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
>>> btree.__getitem__("blog")
'http://blog.csdn.net/qiwsir'
>>> btree.__getitem__(7)
'computer'
>>> btree._getitem__(5) #btreekey=5
Traceback (most recent call last):
File "", line 1, in
AttributeError: 'BinaryTree' object has no attribute '_getitem__'
- .__iter__()
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
>>> aiter = btree.__iter__()
>>> aiter
>>> aiter.next() #next()list
2
>>> aiter.next()
7
>>> list(aiter)
[9, 'Tom', 'blog']
>>> list(aiter) #
[]
>>> bool(aiter) #but,is True
True
- .__len__(),btreeO(1)
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
>>> btree.__len__()
5
- keyk-v.__max__(),keykey
- key.__min__()
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> btree.__max__()
(9, 'scree')
>>> btree.__min__()
(2, 'phone')
-
>>> other = [(3,'http://blog.csdn.net/qiwsir'),(7,'qiwsir')]
>>> bother = BinaryTree() #
>>> bother.update(other) #
>>> bother
BinaryTree({3: 'http://blog.csdn.net/qiwsir', 7: 'qiwsir'})
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> btree.__and__(bother) #
BinaryTree({7: 'computer'})
>>> btree.__or__(bother) #
BinaryTree({2: 'phone', 3: 'http://blog.csdn.net/qiwsir', 7: 'computer', 9: 'scree'})
>>> btree.__sub__(bother) #btreebother
BinaryTree({2: 'phone', 9: 'scree'})
>>> btree.__xor__(bother) #
BinaryTree({2: 'phone', 3: 'http://blog.csdn.net/qiwsir', 9: 'scree'})
- .__repr__()
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> btree.__repr__()
"BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})"
- :.clear(),O(log(n))
>>> bother
BinaryTree({3: 'http://blog.csdn.net/qiwsir', 7: 'qiwsir'})
>>> bother.clear()
>>> bother
BinaryTree({})
>>> bool(bother)
False
- .copy(),O(n*log(n))
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> ctree = btree.copy()
>>> ctree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> btree.__setitem__("github","qiwsir") #btree
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> ctree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) #
>>> ctree.__delitem__(7) #ctree
>>> ctree
BinaryTree({2: 'phone', 9: 'scree'})
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
- .discard(key).__delitem__(key).O(log(n))
>>> ctree
BinaryTree({2: 'phone', 9: 'scree'})
>>> ctree.discard(2) #None
>>> ctree
BinaryTree({9: 'scree'})
>>> ctree.discard(2) #keyNone
>>> ctree.discard(3)
>>> ctree.__delitem__(3) #.__delitem__(key)key
Traceback (most recent call last):
File "", line 1, in
File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 264, in __delitem__
self.remove(key)
File "/usr/local/lib/python2.7/site-packages/bintrees/bintree.py", line 124, in remove
raise KeyError(str(key))
KeyError: '3'
- key.get(key[,d])keyvalue,ddO(log(n))
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> btree.get(2,"algorithm")
'phone'
>>> btree.get("python","algorithm") #key='python''algorithm'
'algorithm'
>>> btree.get("python") #None
>>>
- is_empty().0,O(1)
>>> ctree
BinaryTree({9: 'scree'})
>>> ctree.clear() #
>>> ctree
BinaryTree({})
>>> ctree.is_empty()
True
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> btree.is_empty()
False
- keyvalue
>>.items([reverse])--(key,value);
>>.keys([reverse])--key
>>.values([reverse])--value. O(n)
>>.iter_items(s,e[,reverse]--s,ekeykey O(n)
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> for (k,v) in btree.items():
... print k,v
...
2 phone
7 computer
9 scree
github qiwsir
>>> for k in btree.keys():
... print k
...
2
7
9
github
>>> for v in btree.values():
... print v
...
phone
computer
scree
qiwsir
>>> for (k,v) in btree.items(reverse=True): #
... print k,v
...
github qiwsir
9 scree
7 computer
2 phone
>>> btree
BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
>>> for (k,v) in btree.iter_items(6,9): #6>
-
>>.pop(key[,d]), keyvalueddd
>>.pop_item(),(key,value)
>>> ctree = btree.copy()
>>> ctree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> ctree.pop(2) #key=2value
'phone'
>>> ctree.pop(2) #key
Traceback (most recent call last):
File "", line 1, in
File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 350, in pop
value = self.get_value(key)
File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 557, in get_value
raise KeyError(str(key))
KeyError: '2'
>>> ctree.pop_item() #(key,value),
(7, 'computer')
>>> ctree
BinaryTree({9: 'scree', 'github': 'qiwsir'})
>>> ctree.pop(7,"sing") #
'sing'
- ,value.set_default(key[,d])key,valued,key,dd(key,None). O(log(n))
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> btree.set_default(7) #
'computer'
>>> btree.set_default(8,"eight") #
'eight'
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
>>> btree.set_default(5) #None
>>> btree
BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
>>> btree.get(2) #.get(key).set_default(key[,d])
'phone'
>>> btree.get(3,"mobile") # key,
'mobile'
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
- key
>>.remove(key),(key,value)
>>.remove_items(keys),keyskeylist,
>>> ctree
BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
>>> ctree.remove_items([5,6]) #key=6
Traceback (most recent call last):
File "", line 1, in
File "/usr/local/lib/python2.7/site-packages/bintrees/abctree.py", line 271, in remove_items
self.remove(key)
File "/usr/local/lib/python2.7/site-packages/bintrees/bintree.py", line 124, in remove
raise KeyError(str(key))
KeyError: '6'
>>> ctree
BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
>>> ctree.remove_items([2,7,'github']) #
>>> ctree
BinaryTree({8: 'eight', 9: 'scree'})
###