《python算法教程》Day8 - 构建二分搜索树二分搜索树介绍二分搜索树创建代码

今天是《python算法教程》的第8篇读书笔记,笔记的主要内容是构建二分搜索树。

二分搜索树介绍

若要对一组有序值中执行操作(如查找),二分搜索法是一个优秀的选择,因为其时间复杂度仅为对数级。但很多时候,对序列的操作不仅仅是查找,还涉及到插入新数据。若此时选用数组作为存储数据的结构,插入数据的时间复度是线性级的,显然无法满足快速插入数据的需求。因此,这里引入二分搜索树这一既能利于二分搜索又能以对数级的时间完成搜索的数据结构。

二分搜索树创建代码

二分搜索树是一个对象,其提供插入、搜索节点和判断是否存在某个节点的方法。

#构建二分搜索树

#二分搜索树的节点的自定义类
class Node:
    lft=None
    rgt=None
    def __init__(self,key,val):
        self.key=key
        self.val=val

#定义插入节点的函数
def insert(node,key,val):
    if node is None :
        return Node(key,val)
    #如插入的节点的键与已存在的键相同,则更新节点的值
    if node.key==key:
        node.val=val
    elif key<node.key:
        insert(node.lft,key.val)
    else:
        insert(node.rgt,key,val)
    return node

#从指定节点开始搜索节点
def search(node,key):
    if node is None:
        raise KeyError
    if node.key==key:
        return node.val
    if key<node.key:
        return search(node.lft,key)
    else:
        return search(node.rgt,key)

#定义二分搜索树类
class tree:
    root=None
    #
    def __setitem__(self,key,val):
        self.root=insert(self.root,key,val)
    def __getitem__(self,key):
        return search(self.root,key)
    def __contians__(self,key):
        try:
            search(self.root,key)
        except KeyError:
            return False
        return True

t=tree()
t['root']=10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程之旅

线性表的顺序存储结构

举个简单的例子,蔺老师在给九班学生安排座位之前,会让学生们从矮到高按照身高的高矮升序排列,假如蔺老师的班上只有十个学生,而全班共有50个座位,那蔺老师会把这10...

1552
来自专栏数据结构与算法

cf914D. Bash and a Tough Math Puzzle(线段树)

可以这么想,如果能成功的话,我们可以把那个数改成$1$,这样比$x$大的数就不会对答案产生影响了。

961
来自专栏开发与安全

数据结构:队列的顺序存储结构(循环队列)

队列(Queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。是一种先进先出的线性表(FIFO)。允许插入的一端称为队尾,允许删除的一端称为队头...

2287
来自专栏一枝花算不算浪漫

Java中常见数据结构Set之HashSet

3206
来自专栏架构说

leetcode538. 把二叉搜索树转换为累加树

给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater

1493
来自专栏Java技术栈

java程序员被误导的一个概念,90%人不知道

我们经常听说List是有序且重复的,Set是无序不重复的。这里有个误区,这里说的顺序有两个概念,一是按添加的顺序排列,二是按自然顺序a-z排列。Set并不是无序...

3356
来自专栏趣学算法

数据结构 第1讲 基础知识

        著名的瑞士科学家N.Wirth教授提出:数据结构+算法=程序。数据结构是程序的骨架,算法则是程序的灵魂。

943
来自专栏xcywt

《大话数据结构》 查找 以及一个简单的哈希表例子

第八章 查找 定义:查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。 8.2 查找概论 查找表(Search table):...

88412
来自专栏java一日一条

Java编程常见问题汇总3

这里本意是希望用当前类来加载希望的对象, 但是这里的getClass()可能抛出异常, 特别在一些受管理的环境中, 比如应用服务器, web容器, Java W...

782
来自专栏desperate633

LintCode 简化路径题目分析代码

思路比较简单,遇到..就回到上一级,遇到.或者空就不处理。 我们使用一个队列来处理,同时将三个需要特殊处理的字符存到一个set里面

691

扫码关注云+社区

领取腾讯云代金券