linuxsir首页 LinuxSir.Org | Linux、BSD、Solaris、Unix | 开源传万世,因有我参与欢迎您!
网站首页 | 设为首页 | 加入收藏
您所在的位置:主页 > Linux基础建设 >

用Python实现数据结构之二叉搜索树

时间:2019-02-11  来源:未知  作者:admin666

二叉搜索树

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

  • 对于任意一个节点p,存储在p的左子树的中的所有节点中的值都小于p中的值
  • 对于任意一个节点p,存储在p的右子树的中的所有节点中的值都大于p中的值


一个图例:

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

遍历二叉搜索树

基于二叉搜索树的特性,采用中序遍历的方式可以使得遍历结果是按照从小到大的顺序排列的。了解中序遍历可以参考用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 = self.left(walk)
    return walk

def _subtree_last_position(self, p):
    """返回树的最右节点"""
    walk = p
    while self.right(walk) is not None:
        walk = self.right(walk)
    return walk

下面是一些公开的访问方法:

def first(self):
    return self._subtree_first_position(
        self.root()) if len(self) > 0 else None

def last(self):
    return self._subtree_last_position(
        self.root()) if len(self) > 0 else None

def before(self, p):
    """前驱位置"""
    if self.left(p):
        return self._subtree_last_position(self.left(p))
    else:
        walk = p
        above = self.parent(walk)
        while above is not None and walk == self.left(above):
            walk = above
            above = self.parent(walk)
        return above

def after(self, p):
    """后继位置"""
    if self.right(p):
        return self._subtree_first_position(self.right(p))
 甘蔗斗地主   else:
        walk = p
        above = self.parent(walk)
        while above is not None and walk == self.right(above):
            walk = above
            above = self.parent(walk)
        return above

def find_position(self,k):
    if self.is_empty():
        return None
    else:
        p = self._subtree_search(self.root(),k)
        return p

接下来是映射的核心方法:

def __getitem__(self, k):
    if self.is_empty():
        raise KeyError('Key Error'+repr(k))
    else:
        p = self._subtree_search(self.root(),k)
        if k!=p.key():
            raise KeyError('Key Error' + repr(k))
        return p.value()

def __setitem__(self, k,v):
    if self.is_empty():
        leaf = self.add_root(self._Item(k,v))
    else:
        p = self._subtree_search(self.root(),k)
        if p.key() == k:
            p.element().value = v
            return
        else:
            item = self._Item(k,v)
            if p.key() < k:
                leaf = self.add_right(p,item)
            else:
                leaf = self.add_left(p, item)

def __iter__(self):
    p = self.first()
    while p is not None:
        yield p.key()
        p = self.after(p)

def mapdelete(self,p):
    if self.left(p) and self.right(p):      #两个孩子都有的时候
        replacement = self._subtree_last_position(self.left(p)) #用左子树最右位置代替
        self.replace(p,replacement.element())
        p = replacement
    self.delete(p)

def __delitem__(self, k):
    if not self.is_empty():
        p = self._subtree_search(self.root(),k)
        if k == p.key():
            self.mapdelete(p)
            return
    raise KeyError('Key Error' + repr(k))

最后是一些有序映射特有的方法:

def find_min(self):
    """找最小值,返回键值元组"""
    if self.is_empty():
        return None
    else:
        p = self.first()
        return(p.key(), p.value())

def find_ge(self, k):
    """找第一个大于等于k的键值元组"""
    if self.is_empty():
        return None
    else:
        p = self.find_position(k)
        if p.key() < k:
            p = self.after(p)
        return (p.key(), p.value()) if p is not None else None

def find_range(self, start, stop):

    if not self.is_empty():
        if start is None:
            p = self.first()
        else:
            p = self.find_position(start)
            if p.key() < start:
                p = self.after(p)
        while p is not None and (stop is None or p.key() < stop):
            yield (p.key(), p.value())
            p = self.after(p)

Linux公社的RSS地址:https://www.linuxidc.com/rssFeed.aspx

友情链接
  • Mozilla发布Firefox 67.0.4,修复沙箱逃逸漏洞
  • 蚂蚁金服正式成为CNCF云原生计算基金会黄金会员
  • Firefox 68将采用Microsoft BITS安装更新
  • OpenSSH增加对存储在RAM中的私钥的保护
  • 谷歌想实现自己的curl,为什么?
  • Raspberry Pi 4发布:更快的CPU、更大的内存
  • Firefox的UA将移除CPU架构信息
  • Ubuntu放弃支持32位应用程序实属乌龙,Steam会否重回Ubuntu怀抱
  • Qt 5.13稳定版发布:引入glTF 2.0、改进Wayland以及支持Lottie动
  • 红帽企业Linux 7现已内置Redis 5最新版
  • Slack进入微软内部禁用服务清单,GitHub也在其列?
  • 安全的全新编程语言V发布首个可用版本
  • Windows Terminal已上架,快尝鲜
  • 阿里巴巴微服务开源生态报告No.1
  • 面世两年,Google地球将支持所有基于Chromium的浏览器
  • 推进企业容器化持续创新,Rancher ECIC千人盛典完美收官
  • CentOS 8.0最新构建状态公布,或于数周后发布
  • Debian移植RISC
  • 微软拆分操作系统的计划初现雏形
  • Oracle发布基于VS Code的开发者工具,轻松使用Oracle数据库
  • Ubuntu 19.10停止支持32位的x86架构
  • 微软为Windows Terminal推出全新logo
  • 联想ThinkPad P系列笔记本预装Ubuntu系统
  • 微软发布适用于Win7/8的Microsoft Edge预览版
  • 启智平台发布联邦学习开源数据协作项目OpenI纵横
  • 经过六个多月的延迟,微软终于推出Hyper
  • ZFS On Linux 0.8.1 发布,Python可移植性工作
  • DragonFly BSD 5.6.0 发布,HAMMER2状态良好
  • Linux Kernel 5.2
  • CentOS 8.0 看起来还需要几周的时间
  • 百度网盘Linux版正式发布
  • PCIe 6.0宣布:带宽翻倍 狂飙至256GB/s
  • PHP 7.4 Alpha 发布,FFI扩展,预加载Opcache以获得更好的性能
  • Canonical将在未来的Ubuntu版本中放弃对32位架构的支持
  • Scala 2.13 发布,改进的编译器性能
  • 微软的GitHub收购了Pull Panda,并且使所有订阅完全免费
  • Windows Subsystem for Linux 2 (WSL 2)现在适用于Windows 10用
  • Debian 10 “Buster”的RISC
  • MariaDB宣布发布MariaDB Enterprise Server 10.4
  • DXVK 1.2.2 发布,带来微小的CPU开销优化
  • DragonFlyBSD 5.6 RC1 发布,VM优化,默认为HAMMER2
  • PrimeNG 8.0.0 发布,支持Angular 8,FocusTrap等
  • GIMP 2.10.12 发布,一些有用的改进
  • 清华大学Anaconda 镜像服务即将恢复
  • Debian GNU/Linux 10 “Buster” 操作系统将于2019年7月6日发布
  • 时时彩论坛
  • 五星体育斯诺克
  • 北单比分直播
  • 河北11选5走势图
  • 福建体彩36选7开奖结果
  • 九龙图库下载