搜索二叉树的算法解析与实例演示
目录
- 一.搜索二叉树的特性与实现
- 1.特点
- 2.实现
- 二.搜索二叉树的性能
一.搜索二叉树的特性与实现
1.特点
二叉搜索树是特殊的二叉树,它有着更严格的数据结构特点:
(1)非空左子树的所有键值小于其根结点的键值。
(2)非空右子树的所有键值大于其根结点的键值。
(3)左、右子树都是二叉搜索树
如下图所示就是一株典型的搜索二叉树:
这种结构中序遍历的结果是升序的,以上特性可以帮助我们解决很多问题。例如查找
2.实现
搜索二叉树的查找功能逻辑较简单,根据要查找的值依次与当前节点键值比较,如果小于就在左树继续寻找反之在右树查找。
bool find(const T& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->left;}else if (cur->_key < key){cur = cur->right;}else{return true;}}return false;}
插入功能首先要查找到要插入的值应该放的地方,接着判断自己是父节点的左树还有右树然后进行插入,当查找到与要插入的值相同的键值时,插入失败,因为搜索二叉树不允许有相同的值存在,需要注意的是当此树为空树时,直接插入值即可:
bool Insert(const T& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parents = nullptr;while (cur){if (cur->_key < key){parents = cur;cur = cur->right;}else if (cur->_key > key){parents = cur;cur = cur->left;}else{return false;}}cur = new Node(key);if (parents->_key > key ){parents->left = cur;}else{parents->right = cur;}return true;}
需要重点理解是接下来的删除功能:要删除某个键值 首先需要找到这个结点,大体逻辑与find功能相似,不同的是在找到时如何删除这个结点。这时候分为三种情况:结点左子树为空/结点右子树为空/左右子树都不为空。左或右子树为空时逻辑较简单使用托孤法即可,首先判断是否为根节点如果是则直接将根节点赋值为根节点的右或左结点接着判断自己是父节点的左/右结点,接着让父节点的左/右直接指向我的左或右结点。 当左右子树都不为空时需要使用到替换法,将要删除的结点与左子树的最大结点的键值或者右子树的最小节点的键值替换(因为要保证搜索二叉树的特性),之后删除即可。
bool Erase(const T& key){Node* cur = _root;Node* parents = nullptr;if (cur == nullptr)return false;while (cur){if (cur->_key > key){parents = cur;cur = cur->left;}else if (cur->_key < key){parents = cur;cur = cur->right;}else{if (cur->left == nullptr){ if (cur == _root){_root = cur->right;}else{if (parents->left == cur){parents->left = cur->right;}else{parents->right = cur->right;}}}else if (cur->right == nullptr){if (cur == _root){_root = cur->left;}else{if (parents->left == cur){parents->left = cur->left;}else{parents->right = cur->left;}}}else//左子树和右子树都不为空{Node* parents = cur;Node* leftmax = cur->left;while (leftmax->right){parents = leftmax;leftmax = leftmax->right;}swap(cur->_key, leftmax->_key);if (parents->left == leftmax){parents->left = leftmax->left;}else{parents->right = leftmax->left;}cur = leftmax;}delete cur;return true;}}return false;}
以上讲解的是非递归版的实现,递归版的查找 插入 删除代码更为简洁,但是更难理解。
因为在类外调用成员函数无法向函数传参成员变量,所以在类中进行一些封装:
public:bool findR(const T& key){return _findR(_root, key);}private:bool _findR(Node* root, const T& key){if (root == nullptr){return false;}if (root->_key > key){return _findR(root->left, key);}else if (root->_key < key){return _findR(root->right.key);}else{return true;}}
查找与删除功能同样使用了封装:
public:bool InsertR(const T& key){return _InsertR(_root, key);}bool EraseR(const T& key){return _EraseR(_root, key);}private:bool _EraseR(Node*& root, const T& key){if (root == nullptr){return false;}if (root->_key > key){return _EraseR(root->left, key);}else if (root->_key < key){return _EraseR(root->right,key);}else{Node* del = root;if (root->left == nullptr){root = root->right;}else if (root->right == nullptr){root = root->left;}else{Node* leftMax = root->left;while (leftMax->right){leftMax = leftMax->right;}swap(root->_key, leftMax->_key);return _EraseR(root->left, key);}delete del;return true;}}bool _InsertR(Node*& root, const T& key){if (root == nullptr){root = new Node(key);//神之一手return true;}if (root->_key > key){return _InsertR(root->left, key);}else if (root->_key < key){return _InsertR(root->right.key);}else{return false;}}
二.搜索二叉树的性能
查找的性能在搜索二叉树为完全二叉树或者满二叉树或者接近时,时间复杂度是logN,
在极端情况下,时间复杂度平均为N/2.
相关文章:

搜索二叉树的算法解析与实例演示
目录 一.搜索二叉树的特性与实现1.特点2.实现二.搜索二叉树的性能 一.搜索二叉树的特性与实现 1.特点 二叉搜索树是特殊的二叉树,它有着更严格的数据结构特点: (1)非空左子树的所有键值小于其根结点的键值。 (2&…...

研磨设计模式day13组合模式
目录 场景 不用模式实现 代码实现 有何问题 解决方案 代码改造 组合模式优缺点 思考 何时选用 场景 不用模式实现 代码实现 叶子对象 package day14组合模式;/*** 叶子对象*/ public class Leaf {/*** 叶子对象的名字*/private String name "";/**…...
Linux命令(73)之zip
linux命令之zip 1.zip介绍 linux命令zip是用来压缩文件及解压缩文件名称后缀为".zip"的文件 2.zip用法 zip [参数] filename[.zip] zip常用参数 参数说明-r压缩递归处理-d从压缩文件内删除指定的文件-T检查备份文件是否正确无误-u更换较新的文件到压缩文件内-q不…...

深入理解Reactor模型的原理与应用
1、什么是Reactor模型 Reactor意思是“反应堆”,是一种事件驱动机制。 和普通函数调用的不同之处在于:应用程序不是主动的调用某个 API 完成处理,而是恰恰相反,Reactor逆置了事件处理流程,应用程序需要提供相应的接口并…...
微信小程序开发的投票评选系统设计与实现
摘要 越来越多信息化融入到我们生活当中的同时,也在改变着我们的生活和学习方式,当然,变化最明显的除了我们普通民众之外,要数高校学生的生活方式以及校园信息化的变革。智慧是改变生活和生产的一种来源,那么智慧的体…...

【校招VIP】算法考点之堆排
考点介绍: 排序算法属于数据结构和算法的基础内容,并且也是大厂笔试中的高频考点。 堆排序是使用一棵树存储序列这个课树只保证跟节点是这棵树中的最小值,但并不保证其他节点是按顺序的。因此他的排序是每次从堆中取得堆顶,取得 n…...

关于yarn安装时报“node“ is incompatible with this module的解决办法
前提: 在用vue写一个h5页面时,当在用yarn安装时,提示如下错误: The engine “node” is incompatible with this module. Expected version "^14.18.0 || ^16.14.0 || >18. 解决办法 我是使用命令忽略错误:…...

开源利器推荐:美团动态线程池框架的接入分享及效果展示
前言 蛮早前有些过关于线程池的使用及参数的一些参考配置,有兴趣的可以翻看以前的博文,但终究无法解决线程池的动态监控和实时修改。 以前读过美团早期发布的动态线程池框架的思路相关文章,但想要独自实现不是一件容易的事。 去年,…...

Linux目录结构与文件管理 (02)(四)
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、查看文件内容 二、创建文件 三、删除文件 四、 移动文件 五、复制文件 六、编辑文件内容 总结 前言 今天是在昨天的基础上继续学习,主要…...

对1GHz脉冲多普勒雷达进行快速和慢速处理生成5个移动目标的距离多普勒图研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

uni.uploadFile上传 PHP接收不到
开始这样,后端$file $request->file(file);接收不到 数据跑到param中去了 去掉Content-Type,就能接收到了 param只剩下...

2023年高教社杯 国赛数学建模思路 - 复盘:光照强度计算的优化模型
文章目录 0 赛题思路1 问题要求2 假设约定3 符号约定4 建立模型5 模型求解6 实现代码 建模资料 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 问题要求 现在已知一个教室长为15米,宽为12米&…...

Netty简易聊天室
文章目录 本文目的参考说明环境说明maven依赖日志配置单元测试 功能介绍开发步骤 本文目的 通过一个简易的聊天室案例,讲述Netty的基本使用。同时分享案例代码。项目中用到了log4j2,junit5,同时分享这些基础组件的使用。项目中用到了awt&…...

Flutter Cannot run with sound null safety, because the following dependencies
flutter sdk 版本升级到2.0或者更高的版本后,运行之前的代码会报错 Error: Cannot run with sound null safety, because the following dependencies dont support null safety:- package:flutter_swiper- package:flutter_page_indicator- package:transformer_p…...

利用改进的遗传算法(种群隔离与个体迁移)mpi并行解决tsp问题
序 关于tsp问题的概述以及如何使用遗传算法进行求解已经在上一篇文章中说明了:遗传算法解决TSP问题. 但是,作为一种演化算法,遗传算法还存在着许多问题,比如早熟的情况,很容易在算法前期就已经收敛了,大量…...

【C++】—— C++11之线程库
前言: 在本期,我将给大家介绍的是 C11 中新引进的知识,即关于线程库的相关知识。 目录 (一)线程库的介绍 1、线程库的由来 2、线程库的简单介绍 (二)线程函数参数 (三…...
前端面试:【性能优化】前端缓存、CDN、懒加载和预加载
亲爱的前端开发者,Web性能对用户体验至关重要。如果你想让你的网站更快、更具吸引力,就需要关注前端性能优化。在这篇文章中,我们将深入探讨四个关键的性能优化策略:前端缓存、CDN(内容分发网络)、懒加载和…...

民族传统文化分享系统uniapp 微信小程序
管理员、用户可通过Android系统手机打开系统,注册登录后可进行管理员后端;首页、个人中心、用户管理、知识分类管理、知识资源管理、用户分享管理、意见反馈、系统管理,用户前端;首页、知识资源、用户分享、我的等。 本系统的使用…...
netty(二):NIO——处理可写事件
处理可写事件 什么情况下需要注册可写事件? 在服务端一次性无法把数据发送完的情况下,需要注册可写事件 服务端一次性是否能够把数据全部发送完成取决于服务端的缓冲区大小,该缓冲区不受程序控制 注册可写事件的步骤 判断ByteBuffer是否仍…...
PHP基本语法解析与应用指南
PHP(Hypertext Preprocessor)是一种广泛应用的开源脚本语言,特别适用于Web开发。本文将深入探讨PHP的基本语法,包括变量、数据类型、运算符、控制流等方面的内容。我们将详细介绍每个主题的基本概念、语法规则和常见应用ÿ…...

【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...

Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...
Linux安全加固:从攻防视角构建系统免疫
Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...

Qt的学习(一)
1.什么是Qt Qt特指用来进行桌面应用开发(电脑上写的程序)涉及到的一套技术Qt无法开发网页前端,也不能开发移动应用。 客户端开发的重要任务:编写和用户交互的界面。一般来说和用户交互的界面,有两种典型风格&…...