搜索二叉树的算法解析与实例演示
目录
- 一.搜索二叉树的特性与实现
- 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的基本语法,包括变量、数据类型、运算符、控制流等方面的内容。我们将详细介绍每个主题的基本概念、语法规则和常见应用ÿ…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准
城市路内停车管理常因行道树遮挡、高位设备盲区等问题,导致车牌识别率低、逃费率高,传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法,正成为破局关键。该设备安装于车位侧方0.5-0.7米高度,直接规避树枝遮…...

Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解
文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献
Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译: ### 胃肠道癌症的发病率呈上升趋势,且有年轻化倾向(Bray等人,2018&#x…...
LUA+Reids实现库存秒杀预扣减 记录流水 以及自己的思考
目录 lua脚本 记录流水 记录流水的作用 流水什么时候删除 我们在做库存扣减的时候,显示基于Lua脚本和Redis实现的预扣减 这样可以在秒杀扣减的时候保证操作的原子性和高效性 lua脚本 // ... 已有代码 ...Overridepublic InventoryResponse decrease(Inventor…...
基于Uniapp的HarmonyOS 5.0体育应用开发攻略
一、技术架构设计 1.混合开发框架选型 (1)使用Uniapp 3.8版本支持ArkTS编译 (2)通过uni-harmony插件调用原生能力 (3)分层架构设计: graph TDA[UI层] -->|Vue语法| B(Uniapp框架)B --&g…...