数据结构(Java):揭开二叉搜索树删除机制的奥秘

目录

1、二叉搜索树

1.1 概念

2、代码模拟实现

2.1 插入操作

2.2 查找操作

2.3 🌟删除操作🌟(难点)

 2.3.1 要删除节点的左子树为空

2.3.2 要删除节点的右子树为空

2.3.3 要删除节点的左右子树均不为空

2.3.4 删除操作代码

 3、整体模拟实现代码


1、二叉搜索树

1.1 概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  1. 若其左子树不为空,则左子树上所有节点的值都小于根节点的值
  2. 若其右子树不为空,则右子树上所有节点的值都大于根节点的值
  3. 树中每个节点的左右子树也均为二叉搜索树(递归定义)

总结:left.val < root.val < right.val(左子树 < 根节点 < 右子树) 


2、代码模拟实现

首先,我们肯定是要在SearchTree类中定义一个内部类TreeNode来表示节点,定义节点时使用左右孩子表示法。

//内部类 -> 定义搜索树的节点
static class TreeNode {//左右孩子表示法int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}

2.1 插入操作

定义cur和parent指针,根据搜索树左子树 < 根节点 < 右子树的特点,移动cur和parent,找到到新节点插入的位置,插入新节点。

注意:这里parent指针的作用是记录cur父节点的位置,当cur为空即找到要插入的位置时,parent就是新节点node的父节点。

插入操作较为简单,这里不再赘述。

/*** 数据插入* @param val*/public void insert(int val) {TreeNode node = new TreeNode(val);if (root == null) {root = node;return;}TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (val > cur.val) {parent = cur;cur = cur.right;}else if (val < cur.val) {parent = cur;cur = cur.left;}else {//二叉搜索树中节点的值不能重复return;}if (val > parent.val) {parent.right = node;}else {parent.left = node;}}}

2.2 查找操作

查找的思想与插入的思想大致是相同的,只是不用再定义parent了,当找到指定节点时返回即可。

/*** 查找数据* @param val* @return*/public TreeNode searchNode(int val) {TreeNode cur = root;while (cur != null) {if (val > cur.val) {cur = cur.right;}else if (val < cur.val) {cur = cur.left;}else {return cur;}}return null;}

2.3 🌟删除操作🌟(难点)

删除操作是二叉搜索树代码实现时较难的点,因为删除指定节点后需要使树仍为二叉搜索树,所以需要考虑多种情况:

  1. 当要删除的节点的左子树不存在时
  2. 当要删除的节点的右子树不存在时
  3. 当要删除的节点的左右子树均存在时
  4. 要删除的节点是否为根节点,是根节点要怎么办,不是根节点要怎么办

当删除节点后,到底要怎样修改节点间的关系使其仍保持为二叉搜索树呢? 

在下文的讲解中,cur代表要删除的节点,parent代表当cur的父节点

 2.3.1 要删除节点的左子树为空

2.3.2 要删除节点的右子树为空

2.3.3 要删除节点的左右子树均不为空

当要删除节点的左右子树均不为空时,只有这样修改才能使树仍为搜索树:

  1. 将cur的值修改为其左子树中的最大值(左树中最右边的节点),再删除最值节点
  2. 将cur的值修改为其右子树中的最小值(右树中最左边的节点),再删除最值节点

只有这样,才能在删除完该节点后使树仍为搜索树。

这里需要注意一个特殊情况:

2.3.4 删除操作代码

/*** 删除数据* @param val* @return*/public boolean removeNode(int val) {TreeNode cur = root;TreeNode parent = null;//找到要删除的节点cur和其父节点parent的位置while (cur != null) {if (val > cur.val) {parent = cur;cur = cur.right;}else if (val < cur.val) {parent = cur;cur = cur.left;}else {break;}}//没有该节点if (cur == null) {return false;}if (cur != root) {//cur不为根节点if (cur == parent.right) {//cur为父节点的左孩子if (cur.left == null) {//cur左树为空parent.right = cur.right;}else if (cur.right == null){//cur右树为空parent.right = cur.left;}else {//左右都不为空removeSub(cur);}return true;}else {//cur为父节点的右孩子if (cur.left == null) {//cur左树为空parent.left = cur.right;}else if (cur.right == null){//cur右树为空parent.left = cur.left;}else {//左右都不为空removeSub(cur);}return true;}}else {//cur为根节点if (cur.left == null) {//cur左树为空root = cur.right;}else if (cur.right == null) {//cur右树为空root = cur.left;}else {//左右都不为空removeSub(cur);}return true;}}private void removeSub(TreeNode cur) {//将要删除节点的值更改为其左树中值最大的节点(左树中最右边的节点)或者右树中值最小的节点(右树中最左边的节点),并删除这个节点//这样可以使其仍满足二叉搜索树的特征:左 < 根 < 右//这里更改为左树中的值最大的节点TreeNode rParent = cur.left;TreeNode right = rParent.right;if (right != null) {while (right.right != null) {rParent = right;right = right.right;}cur.val = right.val;rParent.right = right.left;}else {//当cur的左孩子就是左子树中的最大值时cur.val = rParent.val;cur.left = rParent.left;}}

 3、整体模拟实现代码

/*** Created with IntelliJ IDEA.* Description:二叉搜索树的模拟实现* User: dings* Date: 2024-08-18* Time: 23:30*/
public class SearchTree {TreeNode root;static class TreeNode {//左右孩子表示法int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}}/*** 数据插入* @param val*/public void insert(int val) {TreeNode node = new TreeNode(val);if (root == null) {root = node;return;}TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (val > cur.val) {parent = cur;cur = cur.right;}else if (val < cur.val) {parent = cur;cur = cur.left;}else {//二叉搜索树中节点的值不能重复return;}if (val > parent.val) {parent.right = node;}else {parent.left = node;}}}/*** 查找数据* @param val* @return*/public TreeNode searchNode(int val) {TreeNode cur = root;while (cur != null) {if (val > cur.val) {cur = cur.right;}else if (val < cur.val) {cur = cur.left;}else {return cur;}}return null;}/*** 删除数据* @param val* @return*/public boolean removeNode(int val) {TreeNode cur = root;TreeNode parent = null;//找到要删除的节点cur和其父节点parent的位置while (cur != null) {if (val > cur.val) {parent = cur;cur = cur.right;}else if (val < cur.val) {parent = cur;cur = cur.left;}else {break;}}//没有该节点if (cur == null) {return false;}if (cur != root) {//cur不为根节点if (cur == parent.right) {//cur为父节点的左孩子if (cur.left == null) {//cur左树为空parent.right = cur.right;}else if (cur.right == null){//cur右树为空parent.right = cur.left;}else {//左右都不为空removeSub(cur);}return true;}else {//cur为父节点的右孩子if (cur.left == null) {//cur左树为空parent.left = cur.right;}else if (cur.right == null){//cur右树为空parent.left = cur.left;}else {//左右都不为空removeSub(cur);}return true;}}else {//cur为根节点if (cur.left == null) {//cur左树为空root = cur.right;}else if (cur.right == null) {//cur右树为空root = cur.left;}else {//左右都不为空removeSub(cur);}return true;}}private void removeSub(TreeNode cur) {//将要删除节点的值更改为其左树中值最大的节点(左树中最右边的节点)或者右树中值最小的节点(右树中最左边的节点),并删除这个节点//这样可以使其仍满足二叉搜索树的特征:左 < 根 < 右//这里更改为左树中的值最大的节点TreeNode rParent = cur.left;TreeNode right = rParent.right;if (right != null) {while (right.right != null) {rParent = right;right = right.right;}cur.val = right.val;rParent.right = right.left;}else {//当cur的左孩子就是左子树中的最大值时cur.val = rParent.val;cur.left = rParent.left;}}
}

END

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/408746.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ollma 本地部署大模型

因为我本地是 windows 的系统&#xff0c;所以这里直接写的是通过 docker 来实现本地大模型的部署。 windows 下 WSl 的安装这里就不做重复&#xff0c;详见 windows 部署 mindspore GPU 开发环境&#xff08;WSL&#xff09; 一、Docker 部署 ollma 1. 拉取镜像&#xff08;…

【PyTorch】关于Tensorboard的简单使用

前提文章目录 【PyTorch】深度学习PyTorch环境配置及安装【详细清晰】 【PyTorch】深度学习PyTorch加载数据 文章目录 前提文章目录SummaryWriter使用add_image()的使用&#xff08;常用来观察训练结果&#xff09;利用Tensorboard观察图片 SummaryWriter使用 from torch.util…

Graphics2D绘图方法总结

一、简介 在开发中可能会遇到这样一类场景&#xff0c;业务复杂度不算太高&#xff0c;技术难度不算太深&#xff0c;但是做起来就很容易把人整破防&#xff0c;伤害很高侮辱性很强的&#xff1a;绘图。 绘图最怕有人挑刺&#xff1a;这里变形&#xff0c;那里不对&#xff0…

【Node】【2】创建node应用

创建node应用 node应用&#xff0c;不仅可以实现web应用&#xff0c;也能实现http服务器。 如果是php写后端&#xff0c;还需要有http服务器&#xff0c;比如apache 或者 nginx。 但是现在主流都是java写后端&#xff0c;也可以像 Node.js 一样用于实现 Web 应用和 HTTP 服务…

<C++> 多态

目录 一、多态的概念 二、多态的定义和实现 1. 多态的构成条件 2. 虚函数 3.虚函数的重写 3.1 析构函数的重写 4. override 和 final &#xff08;C11&#xff09; 5. 重载、重定义&#xff08;隐藏&#xff09;、重写&#xff08;覆盖&#xff09;的对比 三、抽象类 1. 概念 …

银行总分支文件分发系统:在安全与效率之间找到平衡

银行的组织结构通常根据其规模、业务范围和地域分布而有所不同&#xff0c;但一般会包括以下几个层级&#xff1a;总行-区域总部或分行-分行-支行-业务中心或服务中心-国际分支机构-附属机构或子公司。 在日常中&#xff0c;存在总分支文件分发的业务场景&#xff0c;文件类型通…

高效的时间序列可视化:减少认知负荷获得更清晰的洞察

可视化时间序列数据是具有挑战性,尤其是涉及多个数据集时。精心设计的可视化不仅能清晰地传达信息,还能减少观察者的认知负荷,使其更容易提取有意义的洞察。 在本文中,我们将探讨使真实世界的疫苗接种数据来可视化单个时间序列和多个时间序列。 数据可视化中认知负荷的重要性 …

VScode 连接远程服务器

1、 2、 3、免密登录 1、本地生成密钥 ssh-keygen2、生成的密钥默认在 C:\Users\***\.ssh\ 中3、将私钥 C:\Users\***\.ssh\id_rsa 添加到上面的配置文件中的 IdentityFile 项内4、将公钥 C:\Users\***\.ssh\id_rsa\id_rsa.pub 拷贝到远程 ~/.ssh/authorized_keys 中 4、远程…

wpf 定制 个性圆角信息面板

先上图&#xff1a; 代码实现&#xff1a; <Canvas Grid.Column"1"><Border Background"#5665F4" BorderBrush"#5665F4" BorderThickness"0.5" CornerRadius"10,10,10,30"Width"180" Height"165&qu…

图解Redis五大数据类型

五种数据类型的不同之处&#xff0c;是value在存储时的形式不同。 hash类型 value类型是<key,value>键值对。如果发生hash冲突&#xff0c;用开放定址法解决&#xff0c;不拉链&#xff01; key值重复&#xff0c;则新值覆盖旧值 List类型 Set类型 与List的类似&…

C语言中的预处理详解

1. 预定义符号 C语⾔设置了⼀些预定义符号&#xff0c;可以直接使⽤&#xff0c;预定义符号也是在预处理期间处理的。 举个例⼦&#xff1a; printf("file:%s line:%d\n", __FILE__, __LINE__); 2. #define 定义常量 基本语法&#xff1a; #define name stuff 举个例…

openlayers+vite+vue3加载离线地图并实现初始化(一)

前景提示&#xff1a;本文主要讲解使用vite工具构建的项目&#xff0c;利用openlayers实现离线地图的主要一些功能&#xff0c;包括初始化地图、打点、画线、弹窗等等&#xff0c;这些后续有时间会持续为大家更新&#xff0c;本文主要阐述如何实现其首要功能离线地图的初始化。…

【python报错已解决】`Set PROTOCOL_BUFFERS_PYTHON_IMPLEMENTATION=python`

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 引言&#xff1a; 在开发过程中&#xff0c;环境配置常常会引发一些难以预料的报错。如何快速定位并解决这些问题&#xff0c;成…

借题《黑神话悟空》,聊聊UE5 游戏开发中基本的 C++ 概念

最近火的一塌糊涂的《黑神话悟空》就是用UE5引擎开发的。借题发挥&#xff0c;今天讲讲UE游戏开中的一些C基本概念&#xff1b; 编写代码与蓝图&#xff08;可视化脚本&#xff09;相结合具有独特的功能&#xff0c;您需要利用这些功能来实现两全其美。编程可以帮助创建更复杂…

在树莓派5上使用pytroch进行模型训练—全流程笔记

在树莓派上运行pytroch模型&#x1f680; 在完成了树莓派的一系列基础配置学习之后&#xff0c;按照规划&#xff0c;下一步要做的就是在树莓派上安装一个pytorch&#xff0c;尝试运行一下深度学习的模型&#xff0c;如果可以实现且准速度有一定保证的话&#xff0c;就可以作为…

linux(Ubuntu )搭C++ 最新版GDAL完整教程

在前面的文章中主要是介绍如何在windows系统下利用python安装gdal库&#xff0c;如下&#xff1a; 如何快速安装GDAL 在linux环境下python安装gdal也可以利用现成的whl文件&#xff0c;但是安装c GDAL环境的比较麻烦&#xff0c;目前网络上大多是安装的老版本的教程&#xff…

uniapp在线视频监控开发

我这里是uniapp开发的H5项目 视频流是flv模式 用到的插件是flv.js Flv.js Flv.js 是 HTML5 Flash 视频&#xff08;FLV&#xff09;播放器&#xff0c;纯原生 JavaScript 开发&#xff0c;没有用到 Flash。。由 bilibili 网站开源。 常见直播协议 RTMP: 底层基于TCP&…

安泰ATA-7015高压放大器在机器人测试中的应用研究

随着机器人技术的快速发展&#xff0c;机器人在各个领域的应用日益广泛。然而&#xff0c;要确保机器人能够稳定、准确地完成各种任务&#xff0c;就需要对其进行严格的测试和评估。在机器人测试过程中&#xff0c;高压放大器作为一种关键的测试设备&#xff0c;发挥着不可替代…

基于YOLOv8的无人机高空红外(HIT-UAV)检测算法,魔改SimAM注意力助力涨点(一)

&#x1f4a1;&#x1f4a1;&#x1f4a1;本文内容&#xff1a;针对基于YOLOv8的无人机高空红外&#xff08;HIT-UAV&#xff09;检测算法进行性能提升&#xff0c;加入各个创新点做验证性试验。 1&#xff09;魔改SimAM注意力&#xff0c;引入切片操作&#xff1a;mAP从原始的…

python-随机序列(赛氪OJ)

[题目描述] 小理的作业太多了&#xff0c;怎么也做不完。 小理的数学作业由 T 张试卷组成&#xff0c;每张试卷上有 n 个数 a1..n​ &#xff0c;小理需要算出这些数的极差和方差。极差是一个整数&#xff0c;方差是一个浮点数&#xff0c;要求保留到小数点后 3 位。虽然题目很…