当前位置: 首页 > 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三极管做驱动&…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...