二叉排序树的插入和删除操作(python实现)
二叉排序树的插入和删除操作都是在保持二叉排序树特性的前提下进行的。
插入操作:
在二叉排序树中插入一个新节点时,先比较新节点的值和当前节点的值的大小关系,若小于当前节点,则继续在当前节点的左子树中查找;若大于当前节点,则继续在当前节点的右子树中查找。重复该过程,直到找到一个空节点,将新节点插入到该位置上。
删除操作:
删除操作比较复杂,需要分类讨论。
若待删除节点为叶子节点,直接删除即可。
若待删除节点只有一个子节点,将其子节点替代自身即可。
若待删除节点有两个子节点,则需要寻找其右子树中的最小值节点或左子树中的最大值节点来替代自身,然后再将该最小值节点或最大值节点删除。
具体过程如下:
- 在二叉排序树中查找待删除节点,并记录其父节点;
- 对待删除节点进行分类讨论,若为叶子节点或只有一个子节点,则直接删除;
- 若待删除节点有两个子节点,则找到其右子树中的最小值节点,或左子树中的最大值节点;
- 将该最小值节点或最大值节点替代待删除节点,并将其子节点链接到其父节点上; 若待删除节点为根节点,则替换根节点。
- 需要注意的是,在删除节点之后,为了保持二叉排序树的特性,需要对该节点的父节点及其祖先节点进行平衡调整。
class Node:def __init__(self, key):self.left = Noneself.right = Noneself.key = keydef insert(root, key):if root is None:return Node(key)if key < root.key:root.left = insert(root.left, key)elif key > root.key:root.right = insert(root.right, key)return rootdef minValueNode(node):current = nodewhile(current.left is not None):current = current.leftreturn currentdef deleteNode(root, key):if root is None:return rootif key < root.key:root.left = deleteNode(root.left, key)elif(key > root.key):root.right = deleteNode(root.right, key)else:if root.left is None:temp = root.rightroot = Nonereturn tempelif root.right is None:temp = root.leftroot = Nonereturn temptemp = minValueNode(root.right)root.key = temp.keyroot.right = deleteNode(root.right, temp.key)return root相关文章:
二叉排序树的插入和删除操作(python实现)
二叉排序树的插入和删除操作都是在保持二叉排序树特性的前提下进行的。 插入操作: 在二叉排序树中插入一个新节点时,先比较新节点的值和当前节点的值的大小关系,若小于当前节点,则继续在当前节点的左子树中查找;若大…...
算法记录 | Day35 贪心算法
860.柠檬水找零 思路: 只需要维护三种金额的数量,5,10和20。 有如下三种情况: 情况一:账单是5,直接收下。情况二:账单是10,消耗一个5,增加一个10情况三:账…...
coinex // 撮合引擎 逻辑流程 (两种数据源 初始化源和前端源)
目录 1 生产者 数据源 1.1. match-server 一启动 初始化数据 自动查询数据库 查询level2要展示的数据 1.2 match-server接收 前端发给Exchange-server的数据 2. 将查询/接受的数据EntrustOrder 转成 Order 解耦 过滤掉不要的属性 3.Order转成 OrderEvent 4. 分配序号发布…...
CentOS7---部署LNMP数据存储到redis
一、部署LNMP及redis 1、部署LNMP,需要将 tengine-2.2.0.tar.gz 拷贝到虚拟机的 /root 目录下 步骤一:安装nginx 源码安装相关软件包 # pcre-devel做正则匹配,zlib-devel做数据压缩 [roottemplate ~]# yum -y install gcc pcre-devel zlib-de…...
Linux中的git命令行
Linux中的git命令行 目录 Linux中的git命令行引入1、Linux下的git工具起源2、gitee的使用.gitignore.git 3、git三板斧3.1 git add3.2 git commit3.3 git push 4、git操作4.1 查看提交日志4.2 查看状态4.3 远端同步4.4 删除文件4.5 修改文件名 引入 当多个开发者同时参与同一个…...
【C++】哈希表:开散列和闭散列
📝 个人主页 :超人不会飞)📑 本文收录专栏:《C的修行之路》💭 如果本文对您有帮助,不妨点赞、收藏、关注支持博主,我们一起进步,共同成长! 目录 前言一、基于哈希表的两个…...
C技能树:Hello World
Hello World 输出 "Hello, World!" 字符串,请选出错误答案。 小知识:Hello World究竟从何而来? Hello, World最早是由 Brian Kernighan 创建的。1978年,Brian Kernighan写了一本名叫《C程序设计语言》的编程书,在程…...
TryHackMe-Set(Windows渗透测试 | WinDefender免杀)
Set 您再次发现自己在Windcorp公司的内部网络上。上次你去那里的味道真好,你回来了 了解更多。 但是,这次他们设法保护了域控制器,因此您需要找到另一台服务器,并在第一次扫描时发现“Set”。 Set被用作开发人员的平台…...
信安大佬真的用kali吗?
Kali只是现在网络安全和kali比较火的一个操作系统 下面我为大家讲讲kali系统都有那些优点 Kali介绍Kali Linux是基于Debian的Linux发行版, 设计用于数字取证操作系统。面向专业的渗透测试和安全审计。 集成化:预装超过300个渗透测试工具兼容好&#x…...
禁用表单元素:Layui框架下的实践与技巧
引言 在日常的网页开发过程中,有时我们需要禁用表单元素,以防止用户在某些情况下进行输入或更改。在本文中,我们将介绍如何在Layui框架下使用JavaScript禁用表单元素,例如单选按钮(radio)、下拉列表&#…...
spring boot 访问HTML
HTML整合spring boot 简介默认文件路径访问自定义文件路径访问 或通过Controller控制器层跳转访问 简介 SpringBoot默认的页面映射路径(即模板文件存放的位置)为“classpath:/templates/*.html”。静态文件路径为“classpath:/static/”,其中…...
WPF教程(四)--Dispatcher
一、Dispatcher介绍 微软在WPF引入了Dispatcher,那么这个Dispatcher的主要作用是什么呢? 不管是WinForm应用程序还是WPF应用程序,实际上都是一个进程,一个进程可以包含多个线程,其中有一个是主线程,其余的是…...
ijkplayer 编译增加支持更多的音视频格式
ijkplayer是B站开源的一款基于ffmpeg的移动端播放器。但为了减少播放器的体积,很多音视频的格式播放默认都是不支持的,需要自己下载ijkplayer源码进行编译。这里以mac环境下android为例,简述ijkplayer的编译过程,以及为了支持更多…...
TOP命令显示完整命令行信息
TOP 在Linux系统中,可以使用top命令来查看系统的实时性能数据,包括CPU使用率、内存使用率、进程信息等。以下是top命令的常用选项: -d seconds:指定top命令的刷新时间,单位为秒。 -u username:只显示指定…...
Spring6从入门到精通 第一章 带你玩转Spring
这里写目录标题 一 Spring框架产生的原因二 Spring6配置的关键环节 一 Spring框架产生的原因 传统的JavaWeb存在着耦合度较高的问题,而且实现完整的的MVC三层架构,开发成本过大,因此出现了Spring这个轻量级的开发框架,相当于建筑里…...
Apache POI 实现用Java操作Excel完成读写操作
简介 Apache POI是一个用于操作Microsoft Office格式文件(包括xls、docx、xlsx、pptx等)的Java API库。POI全称为Poor Obfuscation Implementation,是Apache Software Foundation的一个开源项目。它提供了一组Java API,使得Java程…...
改善供应商关系的八种方法
与供应商保持良好关系的重要性有很多原因。最重要的是,它使每个人的日常工作更加愉快。它还可以为你获得更好的交易,有助于协作并增强商誉。 但是,每个供应商都是不同的,建立牢固的关系可能很棘手。本文将解释企业如何建立并操持…...
网络安全-CDN绕过寻找真实IP
网络安全-CDN绕过寻找真实IP CDN就是CDN加速,就是根据你的目标让你访问的更快 CDN CDN,即内容分发网络,主要解决因传输距离和不同运营商节点造成的网络速度性能低下的问题。说得简单点,就是一组在不同运营商之间的对接节点上的…...
牛客网 HJ28 素数伴侣【二分图匹配,匈牙利算法】困难
描述 若两个正整数的和为素数,则这两个正整数称之为“素数伴侣”,如2和5、6和13,它们能应用于通信加密。现在密码学会请你设计一个程序,从已有的 N ( N 为偶数)个正整数中挑选出若干对组成“素数伴侣”&am…...
带你畅玩ChatGPT
ChatGPT出来很久了,最近不少朋友还是不太会使用ChatGPT体验与机器人进行聊天,我正好发现有种非常简单的方式帮助大家体验ChatGPT,且响应速度非常快,写代码能力也不错,现在推荐给大家,希望对大家有所帮助。 目录 一、下载专用浏览器 1.1 下载链接 1.2 安装浏览器 二、…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
深度学习水论文:mamba+图像增强
🧀当前视觉领域对高效长序列建模需求激增,对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模,以及动态计算优势,在图像质量提升和细节恢复方面有难以替代的作用。 🧀因此短时间内,就有不…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
Rust 开发环境搭建
环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行: rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu 2、Hello World fn main() { println…...
