设为首页 加入收藏

TOP

用Python实现数据结构之二叉搜索树(一)
2019-02-10 22:08:30 】 浏览:84
Tags:Python 实现 数据结构之二 搜索

二叉搜索树


二叉搜索树是一种特殊的二叉树,它的特点是:



一个图例:



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


遍历二叉搜索树


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


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


算法用伪代码表示为:


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


def _subtree_first_position(self, p):
    """返回树的最左节点"""
    walk = p
    while self.left(walk) is not None:
        walk = sel
编程开发网

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Spring Boot 2注解使用Mybatis动.. 下一篇用Python实现数据结构之映射

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }