python中的二叉树模块内容:
BinaryTree:非平衡二叉树
AVLTree:平衡的AVL树
RBTree:平衡的红黑树
以上是用python写的,相面的模块是用c写的,并且可以做为Cython的包。
FastBinaryTree
FastAVLTree
FastRBTree
特别需要说明的是:树往往要比python内置的dict类慢一些,但是它中的所有数据都是按照某个关键词进行排序的,故在某些情况下是必须使用的。
安装和使用
安装方法
安装环境:
ubuntu12.04, python 2.7.6
安装方法
下载源码,地址:https://bitbucket.org/mozman/bintrees/src
进入源码目录,看到setup.py文件,在该目录内运行
python setup.py install
安装成功,ok!下面就看如何使用了。
应用
bintrees提供了丰富的API,涵盖了通常的多种应用。下面逐条说明其应用。
- 引用
如果按照一般模块的思路,输入下面的命令引入上述模块
>>> 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) <class 'bintrees.bintree.BinaryTree'>
- 逐个增加键值对: .__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) E是dict/iterable,将E批量更新入btree. 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) 如果含有键k,则返回True,否则返回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
新闻热点
疑难解答