Guide to using the binary tree lookup algorithm module in Python
- 2020-04-02 13:48:31
- OfStack
Contents of binary tree module in python:
BinaryTree: non-balanced BinaryTree
AVLTree: a balanced AVL tree
RBTree: balanced red-black tree
The above is written in python, the surface module is written in c, and can be used as a package for Cython.
FastBinaryTree
FastAVLTree
FastRBTree
In particular, trees tend to be slower than python's built-in dict class, but all the data in them is sorted by a certain keyword, so in some cases you must use them.
Installation and use
Installation method
Installation environment:
Ubuntu12.04, python 2.7.6
Installation method
Download the source code, address: (link: https://bitbucket.org/mozman/bintrees/src)
Go to the source directory and see the setup.py file, which runs in that directory
python setup.py install
Successful installation, ok! Here's how to use it.
application
Bintrees provides a rich API that covers a wide range of common applications. The applications are described one by one.
- reference
If you follow the general module thinking, enter the following command to introduce the above module
>>> import bintrees
Wrong, this is wrong, the following warning appears :( XXX is not available, use XXX )
Warning: FastBinaryTree not available, using Python version BinaryTree.
Warning: FastAVLTree not available, using Python version AVLTree.
Warning: FastRBTree not available, using Python version RBTree.
The correct way to introduce it is:
>>> from bintrees import BinaryTree # Only the introduction of the BinartTree
>>> from bintrees import * # All three modules are introduced
To instantiate
See the examples:
>>> btree = BinaryTree()
>>> btree
BinaryTree({})
>>> type(btree)
<class 'bintrees.bintree.BinaryTree'>
- increase the key-value pair one by one:.s. S. (k,v). Order (log(n)).
See the examples:
>>> 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'})
- batch add:.update(E)
E is dict/iterable, update E into btree. O(E*log(n))
See the examples:
>>> 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'})
- find if a key exists:.contains__ (k)
Returns True if the key k is present, otherwise False. Order log n.
See the examples:
>>> 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
- according to key delete some key-value:.s.
See the examples:
>>> btree
BinaryTree({2: 'phone', 5: 'tea', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
>>> btree.__delitem__(5) # delete key=5 the key-value, That is: 5:'tea' Be deleted .
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
- value:.s/s/s/s/s/s/s/s/s/s/s/s/s/s/s/s/s/s/s/s/s/s/s/s
See the examples:
>>> 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) # in btree There is no key=5 "And reported an error.
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'BinaryTree' object has no attribute '_getitem__'
- iterator:.s.
See the examples:
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
>>> aiter = btree.__iter__()
>>> aiter
<generator object <genexpr> at 0xb7416dec>
>>> aiter.next() # Note: next() After one, the value from list Remove the
2
>>> aiter.next()
7
>>> list(aiter)
[9, 'Tom', 'blog']
>>> list(aiter) # The result is empty
[]
>>> bool(aiter) #but,is True
True
- length of the tree:.s/s (), return the length of the btree. The O (1)
See the examples:
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})
>>> btree.__len__()
5
- find the largest k-v pair of keys:.s. S.
- find the smallest key-value pair of keys:.s.
See the examples:
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> btree.__max__()
(9, 'scree')
>>> btree.__min__()
(2, 'phone')
- relationship between two trees
See the examples:
>>> other = [(3,'//www.jb51.net'),(7,'qiwsir')]
>>> bother = BinaryTree() # Build another tree
>>> bother.update(other) # Add data
>>> bother
BinaryTree({3: '//www.jb51.net', 7: 'qiwsir'})
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> btree.__and__(bother) # Overlapping part
BinaryTree({7: 'computer'})
>>> btree.__or__(bother) # all
BinaryTree({2: 'phone', 3: '//www.jb51.net, 7: 'computer', 9: 'scree'})
>>> btree.__sub__(bother) #btree Not with bother overlap
BinaryTree({2: 'phone', 9: 'scree'})
>>> btree.__xor__(bother) # They're not overlapping
BinaryTree({2: 'phone', 3: '//www.jb51.net, 9: 'scree'})
- output string appearance, note that it is only output appearance:.s/s ()
See the examples:
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> btree.__repr__()
"BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})"
-empty all data in the tree :.clear(), order (log(n))
See the examples:
>>> bother
BinaryTree({3: 'http://blog.csdn.net/qiwsir', 7: 'qiwsir'})
>>> bother.clear()
>>> bother
BinaryTree({})
>>> bool(bother)
False
-shallow copy:.copy(), the official document says shallow copy, but I've done the implementation, which is shown below, and I don't quite understand what "shallow" means. O (n * log (n))
See the examples:
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> ctree = btree.copy()
>>> ctree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'})
>>> btree.__setitem__("github","qiwsir") # increase btree The data of
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> ctree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree'}) # Does this mean it belongs to deep copy?
>>> ctree.__delitem__(7) # delete ctree A number of
>>> ctree
BinaryTree({2: 'phone', 9: 'scree'})
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
- removes a data in the tree:.sub (key). This function is similar to. O (log (n))
See the examples:
>>> ctree
BinaryTree({2: 'phone', 9: 'scree'})
>>> ctree.discard(2) # After deletion, no value is returned, or None
>>> ctree
BinaryTree({9: 'scree'})
>>> ctree.discard(2) # If deleted key Does not exist, also returns None
>>> ctree.discard(3)
>>> ctree.__delitem__(3) # However, .__delitem__(key) It's different if key Nonexistent. Error reported.
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
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'
- find by key and return or return the standby value:.get(key[,d]). Returns value if the key exists in the tree, or d if there is a d. O (log (n))
See the examples:
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> btree.get(2,"algorithm")
'phone'
>>> btree.get("python","algorithm") # There is no key='python' , returns 'algorithm'
'algorithm'
>>> btree.get("python") # If you do not specify the second parameter, if not, returns None
>>>
- determines if the tree is empty: is_empty(). According to the length of the tree data, if the data length is 0, it is empty. The O (1)
See the examples:
>>> ctree
BinaryTree({9: 'scree'})
>>> ctree.clear() # Empty data
>>> ctree
BinaryTree({})
>>> ctree.is_empty()
True
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> btree.is_empty()
False
- value from the tree according to the key and value loops:
> > .items([reverse])-- value according to the (key,value) structure;
> > Keys ([reverse]) - key
> > Values (/ reverse) -- value. O (n)
> > .iter_items(s,e[,reverse]--s,e is the range of key, that is, the iterator O(n) that generates the key in a range.
See the examples:
>>> 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): # trans
... 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): # Require iteration 6<=key<9 Key value pair data
... print k,v
...
7 computer
8 eight
>>>
- delete the data and return the value:
> > .pop(key[,d]), delete the data of the tree according to the key, and return the value. However, if there is no d and an alternative d is also specified, return d; if there is no d, report an error;
> > .pop_item(), randomly selected (key,value) in the tree to delete and return.
See the examples:
>>> ctree = btree.copy()
>>> ctree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> ctree.pop(2) # delete key=2 And return it value
'phone'
>>> ctree.pop(2) # Delete one that does not exist key An error,
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
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() # Return one at random (key,value), And has been deleted
(7, 'computer')
>>> ctree
BinaryTree({9: 'scree', 'github': 'qiwsir'})
>>> ctree.pop(7,"sing") # If not, you can return the specified value
'sing'
- find the data and return value:.set_default(key[,d]), find the key in the data of the tree and return the value if it exists. If it does not exist, when d is specified, the (key,d) is added to the tree; When d is not specified, add (key,None).o (log n).
See the examples:
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'github': 'qiwsir'})
>>> btree.set_default(7) # Existence returns
'computer'
>>> btree.set_default(8,"eight") # Returns the backing specified value and is added to the tree
'eight'
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
>>> btree.set_default(5) # If no value is specified, it is added None
>>> btree
BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
>>> btree.get(2) # Pay attention to, .get(key) with .set_default(key[,d]) The difference between
'phone'
>>> btree.get(3,"mobile") # There is no the key, Returns but does not increase to the tree
'mobile'
>>> btree
BinaryTree({2: 'phone', 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
- delete the value according to the key
> > . Remove (key), delete (key, value)
> >.remove_items(keys),keys is a list of keys that delete the corresponding data in the tree one by one
See the examples:
>>> ctree
BinaryTree({2: 'phone', 5: None, 7: 'computer', 8: 'eight', 9: 'scree', 'github': 'qiwsir'})
>>> ctree.remove_items([5,6]) #key=6 No. Error
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
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']) # In accordance with the Delete each order in the list
>>> ctree
BinaryTree({8: 'eight', 9: 'scree'})
The above is just a basic way to get started. There is more, please do not go to the official website at the beginning of the article