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

数据结构——二叉搜索树

一、二叉搜索树概念

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

(1)若它的左子树不为空,则左子树上的所有节点的值都小于根节点的值;

(2)若它的右子树不为空,则右子树上的所有节点的值都大于根节点的值;

(3)它的左右子树也分别为二叉搜索树。

二、二叉搜索树操作

1.二叉搜索树的查找

(1)若根节点为空,则直接返回false,否则进行后续操作;

(2)如果根节点key==查找key,返回ture,否则进行后续操作;

(3)若根节点key>查找key,则在其左子树内进行查找,否则在其右子树内进行查找;

(4)递归上述过程。

2.二叉搜索树的插入

(1)若树为空,则直接插入;

(2)若树不为空,则按二叉搜索树性质查找插入位置,然后插入。

3.二叉搜索树的删除

        首先查找待删除元素是否在二叉搜索树中,没有则直接返回,否则要删除的节点可分为以下四种情况:

(1)待删除节点无孩子节点;

(2)待删除节点只有左孩子;

(3)待删除节点只有右孩子;

(4)待删除节点左右孩子都有。

删除方法:

情况(1):删除方法与情况(2)和(3)相同;

情况(2):删除该节点,并使被删除节点的双亲节点指向被删除节点的左孩子节点;

情况(3):删除该节点,并使被删除节点的双亲节点指向被删除节点的右孩子;

情况(4):在它的右子树中寻找中序下的第一个节点(值最小的节点),用它的值覆盖掉被删除节点,在处理该节点的删除问题。或找它左子树中最大的节点。

三、二叉搜索的实现

1.代码实现

template<class T>
struct BSTNode {BSTNode(const T& value = T()): _left(nullptr), _right(nullptr), _value(value){}BSTNode<T>* _left;BSTNode<T>* _right;T _value;
};//约定value唯一
template<class T>
class BinarySearchTree {typedef BSTNode<T> Node;
public:BinarySearchTree(): _root(nullptr){}~BinarySearchTree() {Destroy(_root);}//插入bool Insert(const T& value) {//空树if (_root == nullptr) {_root = new Node(value);return true;}//非空Node* cur = _root;Node* parent = nullptr;//保存cur双亲节点//查找插入位置while (cur) {parent = cur;if (value < cur->_value) {cur = cur->_left;}else if (value > cur->_value) {cur = cur->_right;}else {//待插入节点已存在return false;}}//插入新节点cur = new Node(value);if (value > parent->_value) {parent->_right = cur;}else {parent->_left = cur;}return true;}//查找Node* Find(const T& value) {Node* cur = _root;while (cur) {if (value == cur->_value) {return cur;}else if (value < cur->_value) {cur = cur->_left;}else {cur = cur->_right;}}return cur;}//删除bool Erase(const T& value) {if (_root == nullptr) return false;Node* cur = _root;Node* parent = nullptr;//查找待删除节点while (cur) {//parent = cur;不能在这里记录双亲节点,因为有可能cur已经是待删除节点,会直接breakif (value == cur->_value) {break;}else if (value < cur->_value) {parent = cur;cur = cur->_left;}else {parent = cur;cur = cur->_right;}}if (cur == nullptr) return false;//没有待删除节点//删除节点if (cur->_left == nullptr) {//情况1和2if (parent == nullptr) {//是根节点且左孩子为空_root = cur->_right;}else {//不是根节点if (cur == parent->_left) parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr) {//情况1和3if (parent == nullptr) {//是根节点且右孩子为空_root = cur->_left;}else {//不是根节点if (cur == parent->_left) parent->_left = cur->_left;else parent->_right = cur->_left;}delete cur;}else {//情况4//查找该节点右子树最小值(或左子树的最大值)Node* prev = cur;Node* node = cur->_right;while (node->_left) {prev = node;node = node->_left;}//覆盖节点值cur->_value = node->_value;//删除节点,该节点的左孩子肯定为空if (node == prev->_left) prev->_left = node->_right;else prev->_right = node->_right;delete node;}return true;}//中序遍历void InOrder() {_InOrder(_root);std::cout << std::endl;}private://中序遍历void _InOrder(Node* root) {if (root == nullptr) return;_InOrder(root->_left);std::cout << root->_value << " ";_InOrder(root->_right);}//销毁void Destroy(Node*& root) {//利用后续遍历销毁if (root == nullptr) return;Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}private:Node* _root;
};

2.性能分析

        二叉搜索树的插入、删除操作都必须先进行查找,查找效率代表了二叉搜索树的各个操作的性能。而二叉树的结构,取决于给定的序列:

(1)最优情况下:二叉搜索树为完全二叉树,其平均比较次数为log_{2}^{N}

(2)最坏情况下:二叉搜索树退化为单支树,其平均比较次数为N/2;

所以二叉搜索树的查找、插入、删除时间复杂度都是O(N)。

相关文章:

数据结构——二叉搜索树

一、二叉搜索树概念 二叉搜索树又叫二叉排序树&#xff0c;它或是空树&#xff0c;或是具有以下性质的二叉树&#xff1a; &#xff08;1&#xff09;若它的左子树不为空&#xff0c;则左子树上的所有节点的值都小于根节点的值&#xff1b; &#xff08;2&#xff09;若它的…...

23年5月高项学习笔记3---项目管理概述

项目是创造独特的产品、服务或成果而进行的临时性的工作 独特&#xff1a;每个项目都不一样 可交付成果&#xff1a;某一过程&#xff0c;阶段或项目完成时形成的独特的并且可验证的产品、服务或成果。 临时的&#xff1a;明确的起点和终点、 -------- 项目集&#xff1a; 相…...

【组织架构】中国铁路成都局集团有限公司

0 参考 中国铁路成都局集团有限公司 1 公司介绍 中国铁路成都局集团有限公司&#xff0c;是中国国家铁路集团有限公司管理的18个铁路局集团有限公司之一&#xff0c;简称“成局”&#xff0c;地处中国西南&#xff0c;管辖范围辐射四川、贵州、重庆地区。管内地形复杂&#x…...

剧前爆米花--爪哇岛寻宝】java多线程案例——单例模式、阻塞队列及生产者消费者模型、定时器、线程池

作者&#xff1a;困了电视剧 专栏&#xff1a;《JavaEE初阶》 文章分布&#xff1a;这是关于java多线程案例的文章&#xff0c;进行了对单例模式、阻塞队列及生产者消费者模型、定时器和线程池的讲解&#xff0c;希望对你有所帮助&#xff01; 目录 单例模式 懒汉模式实现 饿…...

Guitar Pro8中文版更新说明及系统要求介绍

Guitar Pro吉他软件是初学作曲&#xff0c;特别是同时又初学吉他的朋友们的良师益友&#xff0c;是一款极佳的初级软件&#xff0c;是非实时作曲软件之中的一件佳作。Guitar Pro在吉他和弦、把位的显示、推算、查询、调用等方面&#xff0c;也异常方便、简洁、直观和浩瀚&#…...

【id:19】【20分】A. 三数论大小(引用)

题目描述 输入三个整数&#xff0c;然后按照从大到小的顺序输出数值。 要求&#xff1a;定义一个函数&#xff0c;无返回值&#xff0c;函数参数是三个整数参数的引用&#xff0c;例如int &a, int &b, int &c。在函数内对三个参数进行排序。主函数调用这个函数进行…...

To_Heart—总结——FWT(快速沃尔什变换)

目录闲话拿来求什么或与异或闲话 这个比FFT简单了很多呢&#xff0c;&#xff0c;大概是我可以学懂的水平&#xff01; 好像是叫 快速沃尔什变换 &#xff1f; 拿来求什么 以 FFT 来类比。我们 FFT 可以在 O(nlogn)\mathrm{O(nlogn)}O(nlogn) 的复杂度下实现求解&#xff1…...

Google巨大漏洞让Win10、11翻车,小姐姐马赛克白打了

早年间电脑截图这项技能未被大多数人掌握时&#xff0c;许多人应该都使用过手机拍屏幕这个原始的方式。 但由于较低的画面质量极其影响其他用户的观感&#xff0c;常常受到大家的调侃。 但到了 Win10、11 &#xff0c;预装的截图工具让门槛大幅降低。 WinShiftS 就能快速打开…...

腾讯云服务器部署内网穿透(让其他人在不同ip可以访问我们localhost端口的主机项目)(nps开源项目)

首先打开shell连接我们的云服务器 然后我们再opt目录下面创建一个文件夹用来存放我们的压缩包和文件 mkdir /opt/nps 这个是它官方的安装图解.所以我们按照这个docker安装过程来: 然后我们用docker安装镜像.这样的话比较简单一点 docker pull ffdfgdfg/nps 然后我们查看docker…...

IDS、恶意软件、免杀技术、反病毒技术、APT、对称加密、非对称加密以及SSL的工作过程的技术介绍

IDS的简单介绍IDS是&#xff1a;入侵检测系统&#xff08;intrusion detection system&#xff0c;简称“IDS”&#xff09;是一种对网络传输进行即时监视&#xff0c;在发现可疑传输时发出警报或者采取主动反应措施的网络安全设备。它与其他网络安全设备的不同之处便在于&…...

怎么把pdf转换成高清图片

怎么把pdf转换成高清图片&#xff1f;可以使用以下两种方法&#xff1a; 方法一&#xff1a;使用Adobe Acrobat Pro DC 1、打开需要转换的PDF文件&#xff0c;点击“文件”菜单中的“导出为”&#xff0c;在弹出的菜单中选择“图像”&#xff0c;然后选择“JPEG”。 2、在“…...

MATLAB 系统辨识 + PID 自动调参

系统辨识 PID 自动调参 文章目录系统辨识 PID 自动调参1. 导入数据1.1 从 Excel 中导入数据2. 系统辨识3. PID 自动调参1. 导入数据 1.1 从 Excel 中导入数据 如果不是从Excel中导入可以跳过该步骤 导入函数&#xff1a; [num,txt,raw]xlsread(xxx\xxx.xlsx);num返回的是…...

【vue3】组合式API之setup()介绍与reactive()函数的使用·上

>&#x1f609;博主&#xff1a;初映CY的前说(前端领域) ,&#x1f4d2;本文核心&#xff1a;setup()概念、 reactive()的使用 【前言】vue3作为vue2的升级版&#xff0c;有着很多的新特性&#xff0c;其中就包括了组合式API&#xff0c;也就是是 Composition API。学习组合…...

爬虫Day3 csv和bs4

爬虫Day3 csv和bs4 一、CSV的读和写 1. 什么是csv文件 csv文件叫做&#xff1a;逗号分隔值文件&#xff0c;像Excel文件一样以行列的形式保存数据&#xff0c;保存数据的时候同一行的多列数据用逗号隔开。 2. csv文件的读写操作 1) csv文件读操作 from csv import reader…...

nnAudio的简单介绍

官方实现 https://github.com/KinWaiCheuk/nnAudio&#xff1b; 论文实现&#xff1a; nnAudio: An on-the-Fly GPU Audio to Spectrogram Conversion Toolbox Using 1D Convolutional Neural Networks&#xff1b; 以下先对文章解读&#xff1a; abstract 在本文中&#x…...

【id:134】【20分】B. 求最大值最小值(引用)

题目描述 编写函数void find(int *num,int n,int &minIndex,int &maxIndex)&#xff0c;求数组num(元素为num[0]&#xff0c;num[1]&#xff0c;...&#xff0c;num[n-1]&#xff09;中取最小值、最大值的元素下标minIndex,maxIndex&#xff08;若有相同最值&#xff0…...

Java 面向对象

一、Java 8 增强的包装类 Java是面向对象的编程语言&#xff0c;但它也包含了8种基本数据类型&#xff0c;这8种基本数据类型不支持面向对象的编程机制&#xff0c;基本数据类型的数据也不具备对象的特性。&#xff08;没有成员变量、方法可以被调用&#xff09;。Java之所以提…...

五、传输层

&#xff08;一&#xff09;TCP传输控制协议 可靠的、面向连接的字节流服务&#xff0c;全双工&#xff0c;有端口寻址功能 1、TCP的三种机制 1.使用序号对分段的数据进行标记&#xff0c;便于调整数据包 2.TCP使用确认、校验和和定时器系统提供可靠性 3.TCP使用可变大小的…...

Thinkphp 6.0一对一关联查询

本节课我们来了解关联模型中&#xff0c;一对一关联查询的使用方法。 一&#xff0e;hasOne 模式 1. hasOne 模式&#xff0c;适合主表关联附表&#xff0c;具体设置方式如下: hasOne(关联模型,[外键,主键]); return $this->hasOne(Profile::class,user_id, id); 关联模型&…...

基于51单片机的自动打铃打鸣作息报时系统AT89C51数码管三极管时钟电路

wx供重浩&#xff1a;创享日记 对话框发送&#xff1a;单片机打铃 获取完整无水印论文报告说明&#xff08;含源码程序、电路原理图和仿真图&#xff09; 本次设计中的LED数码管电子时钟电路采用24小时制记时方式,本次设计采用AT89C51单片机的扩展芯片和6个PNP三极管做驱动&…...

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

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

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

算法刷题-回溯

今天给大家分享的还是一道关于dfs回溯的问题&#xff0c;对于这类问题大家还是要多刷和总结&#xff0c;总体难度还是偏大。 对于回溯问题有几个关键点&#xff1a; 1.首先对于这类回溯可以节点可以随机选择的问题&#xff0c;要做mian函数中循环调用dfs&#xff08;i&#x…...

Linux入门课的思维导图

耗时两周&#xff0c;终于把慕课网上的Linux的基础入门课实操、总结完了&#xff01; 第一次以Blog的形式做学习记录&#xff0c;过程很有意思&#xff0c;但也很耗时。 课程时长5h&#xff0c;涉及到很多专有名词&#xff0c;要去逐个查找&#xff0c;以前接触过的概念因为时…...

中科院1区顶刊|IF14+:多组学MR联合单细胞时空分析,锁定心血管代谢疾病的免疫治疗新靶点

中科院1区顶刊|IF14&#xff1a;多组学MR联合单细胞时空分析&#xff0c;锁定心血管代谢疾病的免疫治疗新靶点 当下&#xff0c;免疫与代谢性疾病的关联研究已成为生命科学领域的前沿热点。随着研究的深入&#xff0c;我们愈发清晰地认识到免疫系统与代谢系统之间存在着极为复…...