当前位置: 首页 > news >正文

二叉排序树的插入和删除操作(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实现)

二叉排序树的插入和删除操作都是在保持二叉排序树特性的前提下进行的。 插入操作&#xff1a; 在二叉排序树中插入一个新节点时&#xff0c;先比较新节点的值和当前节点的值的大小关系&#xff0c;若小于当前节点&#xff0c;则继续在当前节点的左子树中查找&#xff1b;若大…...

算法记录 | Day35 贪心算法

860.柠檬水找零 思路&#xff1a; 只需要维护三种金额的数量&#xff0c;5&#xff0c;10和20。 有如下三种情况&#xff1a; 情况一&#xff1a;账单是5&#xff0c;直接收下。情况二&#xff1a;账单是10&#xff0c;消耗一个5&#xff0c;增加一个10情况三&#xff1a;账…...

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&#xff0c;需要将 tengine-2.2.0.tar.gz 拷贝到虚拟机的 /root 目录下 步骤一&#xff1a;安装nginx 源码安装相关软件包 # pcre-devel做正则匹配&#xff0c;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++】哈希表:开散列和闭散列

&#x1f4dd; 个人主页 &#xff1a;超人不会飞)&#x1f4d1; 本文收录专栏&#xff1a;《C的修行之路》&#x1f4ad; 如果本文对您有帮助&#xff0c;不妨点赞、收藏、关注支持博主&#xff0c;我们一起进步&#xff0c;共同成长&#xff01; 目录 前言一、基于哈希表的两个…...

C技能树:Hello World

Hello World 输出 "Hello, World!" 字符串&#xff0c;请选出错误答案。 小知识&#xff1a;Hello World究竟从何而来? Hello, World最早是由 Brian Kernighan 创建的。1978年&#xff0c;Brian Kernighan写了一本名叫《C程序设计语言》的编程书&#xff0c;在程…...

TryHackMe-Set(Windows渗透测试 | WinDefender免杀)

Set 您再次发现自己在Windcorp公司的内部网络上。上次你去那里的味道真好&#xff0c;你回来了 了解更多。 但是&#xff0c;这次他们设法保护了域控制器&#xff0c;因此您需要找到另一台服务器&#xff0c;并在第一次扫描时发现“Set”。 Set被用作开发人员的平台&#xf…...

信安大佬真的用kali吗?

Kali只是现在网络安全和kali比较火的一个操作系统 下面我为大家讲讲kali系统都有那些优点 Kali介绍Kali Linux是基于Debian的Linux发行版&#xff0c; 设计用于数字取证操作系统。面向专业的渗透测试和安全审计。 集成化&#xff1a;预装超过300个渗透测试工具兼容好&#x…...

禁用表单元素:Layui框架下的实践与技巧

引言 在日常的网页开发过程中&#xff0c;有时我们需要禁用表单元素&#xff0c;以防止用户在某些情况下进行输入或更改。在本文中&#xff0c;我们将介绍如何在Layui框架下使用JavaScript禁用表单元素&#xff0c;例如单选按钮&#xff08;radio&#xff09;、下拉列表&#…...

spring boot 访问HTML

HTML整合spring boot 简介默认文件路径访问自定义文件路径访问 或通过Controller控制器层跳转访问 简介 SpringBoot默认的页面映射路径&#xff08;即模板文件存放的位置&#xff09;为“classpath:/templates/*.html”。静态文件路径为“classpath:/static/”&#xff0c;其中…...

WPF教程(四)--Dispatcher

一、Dispatcher介绍 微软在WPF引入了Dispatcher&#xff0c;那么这个Dispatcher的主要作用是什么呢&#xff1f; 不管是WinForm应用程序还是WPF应用程序&#xff0c;实际上都是一个进程&#xff0c;一个进程可以包含多个线程&#xff0c;其中有一个是主线程&#xff0c;其余的是…...

ijkplayer 编译增加支持更多的音视频格式

ijkplayer是B站开源的一款基于ffmpeg的移动端播放器。但为了减少播放器的体积&#xff0c;很多音视频的格式播放默认都是不支持的&#xff0c;需要自己下载ijkplayer源码进行编译。这里以mac环境下android为例&#xff0c;简述ijkplayer的编译过程&#xff0c;以及为了支持更多…...

TOP命令显示完整命令行信息

TOP 在Linux系统中&#xff0c;可以使用top命令来查看系统的实时性能数据&#xff0c;包括CPU使用率、内存使用率、进程信息等。以下是top命令的常用选项&#xff1a; -d seconds&#xff1a;指定top命令的刷新时间&#xff0c;单位为秒。 -u username&#xff1a;只显示指定…...

Spring6从入门到精通 第一章 带你玩转Spring

这里写目录标题 一 Spring框架产生的原因二 Spring6配置的关键环节 一 Spring框架产生的原因 传统的JavaWeb存在着耦合度较高的问题&#xff0c;而且实现完整的的MVC三层架构&#xff0c;开发成本过大&#xff0c;因此出现了Spring这个轻量级的开发框架&#xff0c;相当于建筑里…...

Apache POI 实现用Java操作Excel完成读写操作

简介 Apache POI是一个用于操作Microsoft Office格式文件&#xff08;包括xls、docx、xlsx、pptx等&#xff09;的Java API库。POI全称为Poor Obfuscation Implementation&#xff0c;是Apache Software Foundation的一个开源项目。它提供了一组Java API&#xff0c;使得Java程…...

改善供应商关系的八种方法

与供应商保持良好关系的重要性有很多原因。最重要的是&#xff0c;它使每个人的日常工作更加愉快。它还可以为你获得更好的交易&#xff0c;有助于协作并增强商誉。 但是&#xff0c;每个供应商都是不同的&#xff0c;建立牢固的关系可能很棘手。本文将解释企业如何建立并操持…...

网络安全-CDN绕过寻找真实IP

网络安全-CDN绕过寻找真实IP CDN就是CDN加速&#xff0c;就是根据你的目标让你访问的更快 CDN CDN&#xff0c;即内容分发网络&#xff0c;主要解决因传输距离和不同运营商节点造成的网络速度性能低下的问题。说得简单点&#xff0c;就是一组在不同运营商之间的对接节点上的…...

牛客网 HJ28 素数伴侣【二分图匹配,匈牙利算法】困难

描述 若两个正整数的和为素数&#xff0c;则这两个正整数称之为“素数伴侣”&#xff0c;如2和5、6和13&#xff0c;它们能应用于通信加密。现在密码学会请你设计一个程序&#xff0c;从已有的 N &#xff08; N 为偶数&#xff09;个正整数中挑选出若干对组成“素数伴侣”&am…...

带你畅玩ChatGPT

ChatGPT出来很久了,最近不少朋友还是不太会使用ChatGPT体验与机器人进行聊天,我正好发现有种非常简单的方式帮助大家体验ChatGPT,且响应速度非常快,写代码能力也不错,现在推荐给大家,希望对大家有所帮助。 目录 一、下载专用浏览器 1.1 下载链接 1.2 安装浏览器 二、…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...

Linux 下 DMA 内存映射浅析

序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存&#xff0c;但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程&#xff0c;可以参考这篇文章&#xff0c;我觉得写的非常…...

【Java多线程从青铜到王者】单例设计模式(八)

wait和sleep的区别 我们的wait也是提供了一个还有超时时间的版本&#xff0c;sleep也是可以指定时间的&#xff0c;也就是说时间一到就会解除阻塞&#xff0c;继续执行 wait和sleep都能被提前唤醒(虽然时间还没有到也可以提前唤醒)&#xff0c;wait能被notify提前唤醒&#xf…...

6.计算机网络核心知识点精要手册

计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法&#xff1a;数据与控制信息的结构或格式&#xff0c;如同语言中的语法规则语义&#xff1a;控制信息的具体含义和响应方式&#xff0c;规定通信双方"说什么"同步&#xff1a;事件执行的顺序与时序…...