#问题

Python中的二叉树查找算法模块

#思路说明

二叉树查找算法，在开发实践中，会经常用到。按照惯例，对于这么一个常用的东西，Python一定会提供轮子的。是的，python就是这样，一定会让开发者省心，降低开发者的工作压力。

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
    
- 根据key删除某个key-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=5的key-value,即：5:'tea' 被删除.
    >>> btree
    BinaryTree({2: 'phone', 7: 'computer', 9: 'scree', 'Tom': 'headmaster', 'blog': 'http://blog.csdn.net/qiwsir'})

- 根据key值得到该kye的value：.__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)         #在btree中没有key=5，于是报错。
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    AttributeError: '