二叉搜索树

二叉搜索树是一种特殊的二叉树，它的特点是：

一个图例：

基于二叉搜索树的这种关系，我们可以用它来实现有序映射

遍历二叉搜索树

这里还需要思考的一个内容是在基于中序遍历的前提下，如何求一个节点的后继节点或前驱节点。

显然这就是求比该节点大的下一个节点或比它小的前一个节点。我们拿求后继节点为例：

算法用伪代码表示为：

def after(p):
    """寻找二叉搜索树的后继节点的伪代码"""

    if right(p) is not None:
        walk = right(p)
        while left(right(p)) is not None:  # 找最左
            walk = left(walk)
        return walk
    else:
        walk = p
        ancestor = parent(walk)
        while ancestor is not None and walk == right(ancestor):  # 当walk是左孩子时或walk是根节点时停止
            walk = ancestor
            ancestor = parent(walk)
        return ancestor

找前驱同理

搜索

既然叫做二叉搜索树，那它很重要的一个用途就是搜索，搜索的方式为：

算法用伪代码表示为：

def search(T,p,k):
    """二叉树搜索的伪代码，k是要搜索的值"""
    if k == p.key():
        return p
    elif k < p.key() and T.left(p) is not None:
        return search(T,T.left(p))
    elif k > p.key() and T.right(p) is not None:
        return search(T,T.right(p))
    return p

搜索的时间与高度有关，是O(h),也就是最坏的情况下为O(n),最好的情况下是O(log(n))

插入

插入算法较简单，它依赖于搜索算法，将搜索的返回的位置的值与key进行比较，

删除

删除操作较为复杂，因为删除的位置可以是任意的位置，设删除的位置为p

1.先找到位置p的前驱r，前驱在左子树中

2.把p删除，将r代替p

3.把r原来的位置删除

使用前驱的原因是它必然比p的右子树的所有节点小，也必然比除了r的p的左子树的所有节点大

python实现

我们利用二叉树来实现有序映射

class OrderedMap(BinaryTree,MutableMapping):
    """使用二叉搜索树实现的有序映射"""

    class _item():

        def __init__(self, key, value):
            self.key = key
            self.value = value

        def __eq__(self, other):
            return self.key == other.key

        def __ne__(self, other):
            return self.key != other.key

        def __lt__(self, other):
            return self.key < other.key

    class Position(BinaryTree.Position):

        def key(self):
            return self.element().key

        def value(self):
            return self.element().value

BinaryTree是在之前文章中定义的二叉树类，具体参考用Python实现数据结构之树

首先定义了两个内嵌类，一个表示键值项，一个用于封装节点

然后定义些非公开方法用于其他方法使用：

def _subtree_search(self, p, k):
    """搜索算法"""
    if k == p.key():
        return p
    elif k < p.key():
        if self.left(p) is not None:
            return self._subtree_search(self.left(p), k)
    else:
        if self.right(p) is not None:
            return self._subtree_search(self.right(p), k)
    return p