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

C++ 搜索二叉树的删除

首先查找元素是否在二叉搜索树中,如果不存在,则返回

要删除的结点可能分下面四种情况:

a. 要删除的结点无孩子结点

b. 要删除的结点只有左孩子结点

c. 要删除的结点只有右孩子结点

d. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程如下:

情况1:删除该结点 且使被删除节点的双亲结点指向被删除节点的左孩子结点--直接删除

情况2:删除该结点 且使被删除节点的双亲结点指向被删除结点的右孩子结点--直接删除

情况3:找它的右子树的最小值或者左子树的最大值用它的值填补到被删除节点中,再来处理该结点的删除问题--替换法删除

tip:

我们可以把一个父节点看作父亲,每一个父亲只能照顾两个儿子

情况1和情况2:如果这个父亲只有一个孩子要照顾,或者一个也没有,那么他想要脱身,只需要把这个孩子托付给他的长辈,没有就是nullptr,我们可以把这个过程叫托孤

情况3:就比较复杂,这个父亲有两个孩子,托孤就行不通了,所以他要找一个人来代替他,他需要满足两个条件:

首先,要确保他是可以脱身的(他要是有一个孩子就托孤),这样他就可以过来照顾这两个孩子了

其次,他要满足照顾这两个孩子的条件,这个节点的key值要比左子树的每个节点key都要大,比右子树的每个节点key都要小,

右子树的最小值或者左子树的最大值就满足这些条件,我们可以把这个过程叫找月嫂

bool Erase(const K& data)
{node* parent = nullptr;node* cur = _root;while (cur && cur->_data != data)//找要删除的位置{parent = cur;if (data < cur->_data){cur = cur->_left;}else{cur = cur->_right;}}if (cur == nullptr)return false;if (cur->_left == nullptr)//托孤给父母{if (parent == nullptr)//考虑特殊root==nullptr{_root = cur->_right;}else{if (cur->_data < parent->_data)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr)//托孤给父母{if (parent == nullptr)//考虑特殊root==nullptr{_root = cur->_left;}else{if (cur->_data < parent->_data)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;}else//找月嫂替代(合适 有且只有一个娃或者没有){node* maxleft = cur->_left;node* maxparent = cur;while (maxleft->_right){maxparent = maxleft;maxleft = maxleft->_right;}cur->_data = maxleft->_data;// maxparent->_right = maxleft->_left;错误//月嫂托孤if (maxparent->_left == maxleft)//maxparent==cur{maxparent->_left = maxleft->_left;}else{maxparent->_right = maxleft->_left;}delete maxleft;}return true;
}

注意特殊情况:

1.在情况一和情况二下,可能删除_root节点,在函数里面就需要特殊考虑

2.情况三,月嫂的托孤,月嫂不一定是父亲的右孩子(左子树最大值的前提下),月嫂可能就是要被删除节点的左孩子,所以也要妥善处理

递归版

bool _EraseR(node*& root, const K& data)
{if (root == nullptr)return false;if (data < root->_data)return _EraseR(root->_left, data);else if (data > root->_data)return _EraseR(root->_right, data);else{node* del = root;if (root->_left == nullptr){root = root->_right;delete del;}else if (root->_right == nullptr){root = root->_left;delete del;}else{node* maxleft = root->_left;while (maxleft->_right)maxleft = maxleft->_right;del = maxleft;swap(root->_data, maxleft->_data);_EraseR(root->_left, data);//转为子问题}return true;}
}

node*& root

1.就不需要再找父节点了,这样还少了判断,被删除节点是父亲节点的左孩子还是右孩子

2.对于删除根节点的处理也可以不用特殊处理

_EraseR(root->_left, data);//转为子问题

月嫂托孤的过程,转变为删除月嫂节点

搜索二叉树的删除时间复杂度O(N)

相关文章:

C++ 搜索二叉树的删除

首先查找元素是否在二叉搜索树中&#xff0c;如果不存在&#xff0c;则返回 要删除的结点可能分下面四种情况&#xff1a; a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 看起来有待删除节点有4中…...

构建中国人自己的私人GPT—支持中文

上一篇已经讲解了如何构建自己的私人GPT&#xff0c;这一篇主要讲如何让GPT支持中文。 privateGPT 本地部署目前只支持基于llama.cpp 的 gguf格式模型&#xff0c;GGUF 是 llama.cpp 团队于 2023 年 8 月 21 日推出的一种新格式。它是 GGML 的替代品&#xff0c;llama.cpp 不再…...

elementui 回到顶部报错

<template>Scroll down to see the bottom-right button.<el-backtop target".page-component__scroll .el-scrollbar__wrap"></el-backtop> </template> 使用element的Backtop 回到顶部组件的伙伴们&#xff0c;把官网代码复制到页面使用时…...

go-carbon v2.3.8 发布,轻量级、语义化、对开发者友好的 golang 时间处理库

carbon 是一个轻量级、语义化、对开发者友好的 golang 时间处理库&#xff0c;支持链式调用。 目前已被 awesome-go 收录&#xff0c;如果您觉得不错&#xff0c;请给个 star 吧 github.com/golang-module/carbon gitee.com/golang-module/carbon 安装使用 Golang 版本大于…...

【详解】斗地主随机发牌项目

目录 前言&#xff1a; 1.初始化牌 2.洗牌 3.揭牌 总代码&#xff1a; Card类&#xff1a; CardGame类&#xff1a; Main类&#xff1a; 结语&#xff1a; 前言&#xff1a; 斗地主是全国范围内的一种桌面游戏&#xff0c;本节我们来实现一下斗地主中的简单初始化牌、…...

多账号运营为什么要使用动态住宅代理IP?

对于跨境有多账号运营需求的企业来说&#xff0c;选择正确类型的代理IP对于平稳运行至关重要。但最适合这项工作的代理类型是什么&#xff1f;为了更好地管理不同平台上的多个账户并优化成本&#xff0c;您可以选择动态住宅代理。 一、什么是动态住宅代理 动态住宅代理IP是互联…...

[C++] 如何使用Visual Studio 2022 + QT6创建桌面应用

安装Visual Studio 2022和C环境 [Visual Studio] 基础教程 - Window10下如何安装VS 2022社区版_visual studio 2022 社区版-CSDN博客 安装QT6开源版 下载开源版本QT Try Qt | 开发应用程序和嵌入式系统 | Qt Open Source Development | Open Source License | Qt 下载完成&…...

Arduino 推出基于乐鑫 ESP32-S3 的 STEM 教育机器人

Arduino Alvik 是 Arduino Education 推出的一款新型机器人&#xff0c;可作为一种跨学科工具&#xff0c;为当前教育和未来机器人世界筑起连接的桥梁。Hackster 的 Gareth Halfacree 表示&#xff1a;“Alvik 的设计灵感来自 Arduino 简化复杂技术的理念&#xff0c;同时它也 …...

Blender使用Rigify和Game Rig Tool基础

做动画需要的几个简要步骤&#xff1a; 1.建模 2.绑定骨骼 3.绘制权重 4.动画 1.Rigify是干嘛用的&#xff1f; 》 绑定骨骼 2.Game Rig Tool干嘛用的&#xff1f; 》 修复Rigify绑定骨骼做的动画导入游戏引擎的问题&#xff0c;如果Rigify自身修复了就不需要这个插件了&#…...

【Unity优化(一)】音频优化

整理资教程&#xff1a;https://learn.u3d.cn/tutorial/unity-optimization-metaverse 1.音频优化 音频一般不会成为性能瓶颈&#xff0c;是为了节省内存和优化包体大小。 1.0 文件格式和压缩格式 原始音频资源尽量采用WAV格式。 移动平台音频尽量采用Vorbis压缩格式&#x…...

算法.1-三大排序算法-对数器-二分

三大排序算法&对数器 1.选择排序 Java版 package class01;import java.util.Arrays;public class Code01_SelectionSort {public static void selectionSort(int[] arr) {if (arr null || arr.length < 2) {return;}// 0 ~ N-1 找到最小值&#xff0c;在哪&#xf…...

Midjourney新功能介绍:风格参考(Style References)详解

引言 对于追求创意和一致性的艺术家和设计师们来说&#xff0c;Midjourney的最新功能——风格参考&#xff08;Style References&#xff09;&#xff0c;无疑是一个激动人心的消息。这项测试算法的发布&#xff0c;让我们得以通过简单的URL引用&#xff0c;将特定的风格应用于…...

C++ 11/14/17 智能指针

1. 简介 为了更加容易&#xff08;更加安全&#xff09;的使用动态内存&#xff0c;引入了智能指针的概念。智能指针的行为类似常规指针&#xff0c;重要的区别是它负责自动释放所指向的对象。 标准库提供的两种智能指针的区别在于管理底层指针的方法不同&#xff1a;shared_p…...

C++入门【37-C++ 拷贝构造函数】

拷贝构造函数是一种特殊的构造函数&#xff0c;它在创建对象时&#xff0c;是使用同一类中之前创建的对象来初始化新创建的对象。拷贝构造函数通常用于&#xff1a; 通过使用另一个同类型的对象来初始化新创建的对象。复制对象把它作为参数传递给函数。复制对象&#xff0c;并…...

[UI5 常用控件] 06.Splitter,ResponsiveSplitter

文章目录 前言1. Splitter1.1 属性 2. ResponsiveSplitter 前言 本章节记录常用控件Splitter,ResponsiveSplitter。主要功能是分割画面布局。 其路径分别是&#xff1a; sap.ui.layout.Splittersap.ui.layout.ResponsiveSplitter 1. Splitter 1.1 属性 orientation &#x…...

C遗漏知识(个人向)

之前C语言遗漏的一些。 数据在内存中的存储 原码、反码、补码 整数的2进制表⽰⽅法有三种&#xff0c;即 原码、反码和补码 正整数的原、反、补码都相同。 负整数的三种表⽰⽅法各不相同。 原码&#xff1a;直接将数值按照正负数的形式翻译成⼆进制得到的就是原码。 反码&…...

ERR_SSL_VERSION_OR_CIPHER_MISMATCH

我在namesilo买的域名&#xff0c;coludflare做的解析&#xff0c;华为云的SSL&#xff0c;用宝塔部署的SSL&#xff0c;访问https报错&#xff0c;http却正常&#xff1a; 报错&#xff1a;此网站无法提供安全连接www.hongkong.ioyunxin.top 使用了不受支持的协议。 ERR_SSL_…...

2.5作业

一 、程序阅读题 1、给出下面程序输出结果。 #include <iostream.h> class example {int a; public: example(int b5){ab;} void print(){aa1;cout <<a<<"";} void print()const {cout<<a<<endl;} }; void main() {example x; const e…...

linux系统lvs命令的使用

Lvs命令 LVS ipvsadm 命令的使用LVS-server安装lvs管理软件命令选项 LVS ipvsadm 命令的使用 LVS-server安装lvs管理软件 yum -y install ipvsadm 程序包&#xff1a;ipvsadm&#xff08;LVS管理工具&#xff09; 主程序&#xff1a;/usr/sbin/ipvsadm 规则保存工具&#x…...

PoEAA笔记-7.分布策略

本文摘抄自PoEAA&#xff0c;详细信息请阅读本书 7.1 分布对象的诱惑 透明性非常有用&#xff0c;但虽然有很多东西在分布对象中可以是透明的&#xff0c;但性能却不在其中&#xff0c;尽管上面的架构师是为了提高性能而使用分布组件的&#xff0c;但他的设计只会影响性能&…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...