C++二叉搜索树搜索二叉树二叉排序树

C++二叉搜索树

1. 二叉搜索树的概念

二叉搜索树BST,Binary Search Tree),也称为二叉排序树或二叉查找树。它与一般二叉树的区别在于:每个结点必须满足“左孩子大于自己,右孩子小于自己”的规则。在这种规则的约束下,二叉搜索树使用中序遍历出来的数据是一个由小到大排列的结果。

在这里插入图片描述

优点:

  1. 查找某个值最多只需要遍历高度次即可,效率高。
  2. 使用中序遍历出来的数据是有序的。

缺点:

  1. 结点的值不允许修改,否则破坏树的结构。

2. 二叉搜索树的插入

二叉搜索树的插入很简单,首先用插入的值从根结点开始比较。插入值小于结点值向左,插入值大于结点值向右,直到结点的左孩子或右孩子为空时结束,为空的位置就是插入的位置。

在这里插入图片描述

4作为插入结点的值,先找到6是插入结点的父结点,再判断4和6的大小关系,4<6,所以插入在6的左边。

在这里插入图片描述

7作为插入结点的值,先找到6是插入结点的父结点,再判断7和6的大小关系,7>6,所以插入在6的右边。

3. 二叉搜索树的删除

二叉搜索的删除需要分两种情况:

3.1 删除的结点是叶子结点

如果删除的结点是叶子结点,将该结点的父结点指针制空,再释放该结点即可。

在这里插入图片描述

3.2 删除的结点不是叶子结点

如果删除的结点不是叶子结点,可以分为三种情况讨论:

3.2.1 左子树为空

如果删除的结点的左子树为空,此时需要判断删除结点与其父子树的关系:我是父结点的左孩子,就让父结点的左指向我的右子树;我是父结点的右孩子,就让父结点的右指向我的右子树

在这里插入图片描述

在这里插入图片描述

3.2.2 右子树为空

右子树为空,原理与上相同,只是父结点改变的是左的指向。

在这里插入图片描述

在这里插入图片描述

3.2.3 左右子树不为空

如果删除结点的左右子树都不为空,那么此时就需要使用替换法的思想。替换法可以使用左子树的最大结点或右子树的最小结点作为替换结点来替换当前结点,再将替换结点删除。所谓“替换”在实际操作中不是把两个结点的值互换,而是将替换结点的值赋给原删除结点,因为替换节点最终要删除,所以不必要对其进行真正的替换操作。

使用最左结点替换:

在这里插入图片描述

使用最右结点替换:

在这里插入图片描述

4.二叉搜索树的退化问题

二叉搜索树的最优情况下,查找效率为logN。但当插入的顺序有序或部分有序时,二叉搜索树的查找效率会下降,极端情况下会退化至N

在这里插入图片描述

按{10,9,8,7,6,5,4}的顺序插入,导致二叉搜索树完全退化。

5. 参考代码

template<class K, class V>
struct BSTreeNode
{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key,const V& value):_left(nullptr),_right(nullptr),_key(key),_value(value){}
};template<class K, class V>
class BSTree
{typedef BSTreeNode<K, V> Node;
public:bool Insert(const K& key, const V& value){if (_root == nullptr){_root = new Node(key, value);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key, value);{if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key > key){cur = cur->_left;}else if (cur->_key < key){cur = cur->_right;}else{return cur;}}return nullptr;}bool Erase(const K& key){//先找到该结点Node* cur = _root;Node* parent = cur;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{//如果删除的是叶子结点,直接删除if (cur->_left == nullptr && cur->_right == nullptr){if (cur == parent->_left)parent->_left = nullptr;else if (cur == parent->_right)parent->_right = nullptr;delete cur;}//如果左为空else if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else if (cur == parent->_right){parent->_right = cur->_right;}}delete cur;}//如果右为空else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else if (cur == parent->_right){parent->_right = cur->_left;}}delete cur;}// 如果左右都不为空else{//查找右子树的最左结点替换Node* RightMinParent = cur;Node* RightMin = cur->_right;while (RightMin->_left){RightMinParent = RightMin;RightMin = RightMin->_left;}cur->_key = RightMin->_key;cur->_value = RightMin->_key;cur->_value = RightMin->_value;if (RightMinParent->_left == RightMin){RightMinParent->_left = nullptr;}else{RightMinParent->_right = nullptr;}delete RightMin;}return true;}}return false;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ":" << root->_value << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}
private:Node* _root = nullptr;
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1424328.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

echarts的柱状图使用

1. 柱状图&#xff08;柱体顶部使用外部图片 相关代码 <template><div class"out-bg"><div class"container" ref"warnChartRef"></div></div> </template><script> import * as echarts from echar…

Go微服务: 日志系统ELK核心架构设计

微服务日志系统建设 1 &#xff09;为什么需要日志系统 业务发展越来越庞大&#xff0c;服务器越来越多各种访问日志&#xff0c;应用日志&#xff0c;错误日志量越来越多&#xff0c;无法管理开发人员排查问题&#xff0c;需要到服务器上查日志 2 &#xff09;Elastic Stack…

2024年第十届中西部外语翻译大赛(1)

2024年第十届中西部外语翻译大赛 竞赛信息 “由中西部翻译协会共同体指导发起&#xff0c;各省市译协共建学术指导委员会&#xff0c;2024年第十届中西部外语翻译大赛由中西部翻译协会共同体秘书处&#xff08;武汉公仪网络科技有限公司&#xff09;承办。” - 获奖证书样图 -…

MT3038 植发

思路&#xff1a; 有两个点可以取头发&#xff0c;每个头发寿命不同。 先看点(0,0)&#xff0c;按寿命由小到大排序&#xff08;先考虑寿命短的可以移植到哪里&#xff09;。 (0,0)点头发放置的位置应该让(0,m)点的头发可以尽可能多的放置&#xff08;例如(0,0)点有一根头发…

cmu15445 2023fall project3 详细过程(下)QUERY EXECUTION

QUERY EXECUTION task3/task4 Task #3 - HashJoin Executor and Optimization1、HashJoin1.1 思路1.2 代码 2 NestedLoopJoin优化为HashJoin2.1 思路2.2 代码 Task #4 Sort Limit Executors Top-N Optimization Window Functions1、Sort1.1 思路1.2 代码 2、Limit Executors2…

100m/s高速轧制钢材 八轴测径仪检测毫无压力

关键词&#xff1a;八轴测径仪,在线测径仪,钢材测径仪,高速轧制 随着技术的提升&#xff0c;钢材的生产速度越来越快&#xff0c;一些高速生产的钢材&#xff0c;生产速度甚至达到了100m/s&#xff0c;这是一个非常快的速度。 如果汽车以120公里/小时的速度行驶&#xff0c;那么…

VMware17虚拟机安装Kali Linux2024详解

目录 简介 一、环境搭建 二、下载ISO镜像 三、新建虚拟机 为虚拟机选择合适的操作系统类型和版本 分配适当的内存、硬盘空间和其他虚拟机配置选项 四、硬件配置 编辑虚拟机设置 选择安装介质 五、界面化安装配置 简介 Kali Linux是一个基于Debian的Linux发行版&#…

启明云端ESP32-S3模组WT32-S3选型,Flash最大可选16MB,PSRAM最大可选8MB

使用ESP32-S3单芯片&#xff0c;可以完成语音连接屏控三合一功能。接下来给大家推荐一款ESP32-S3模组WT32-S3&#xff0c;Flash 最大可选 16MB,PSRAM 最大可选 8MB。核心芯片是ESP32-S3。 2.4GHz Wi-Fi(802.11b/g/n)Bluetooth 5(LE)模组&#xff0c;内置ESP32-S3系列芯片&#…

软件工程期末复习(8)需求的表达方法和状态转换图

需求的表达方法 系统模型 需求分析的任务就是借助于当前系统的逻辑模型导出目标系统的逻辑模型&#xff0c;解决目标系统 “做什么” 的问题 通常软件开发项目是要实现目标系统的物理模型。目标系统的具体物理模型是由它的逻辑模型经实例化&#xff0c;即具体到某个业务领域而…

【Linux】常用指令、热键与权限管理

一、常用指令 &#xff08;1&#xff09;ls 功能&#xff1a;列出指定目录下的所有子目录与文件 用法&#xff1a;ls &#xff08;选项&#xff09; &#xff08;目录或文件名&#xff09; 常用选项&#xff1a; -a&#xff1a;列出目录下的所有文件&#xff0c;包括隐藏…

【Redis】Redis面试和工作中十有八九会遇到的问题

1. 数据类型 常用的Redis数据类型有5种&#xff0c;分别是&#xff1a; String、List、Set、SortedSet、Hash 还有一些高级数据类型&#xff0c;比如Bitmap、HyperLogLog、GEO等&#xff0c;其底层都是基于上述5种基本数据类型。因此在Redis的源码中&#xff0c;其实只有5种数…

45°和68°焕新上市,五粮液完成产品体系化布局

执笔 | 尼 奥 编辑 | 扬 灵 如今&#xff0c;白酒行业正经历周期性调整&#xff0c;头部化和品牌化集中趋势日益显著。五粮液在这一关键时刻&#xff0c;敏锐地捕捉到市场机遇&#xff0c;通过产品焕新&#xff0c;进一步完善和丰富了其代际系列产品体系。 这一举措不仅巩…

Shell之常用命令

目录 1.排序工具--sort命令 1.1 快读查找一个目录中最大文件 2.去重工具--uniq命令 2.1 分析判断远程登录错误次数&#xff0c;禁止该用户远程登录 3.修改工具--tr命令 4.列截取工具--cut命令 5.分割文件工具--split命令 6.合并文件列--paste命令 7.扫描工具--eval命令…

VMware Workstation 17.5.2 Pro 发布,产品订阅模式首个重大变更

VMware Workstation 17.5.2 Pro 发布&#xff0c;产品订阅模式首个重大变更 基于 x86 的 Windows、Linux 桌面虚拟化软件 请访问原文链接&#xff1a;https://sysin.org/blog/vmware-workstation-17/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页…

失业焦虑如何缓解心情?流静冥想

失业焦虑如何缓解心情&#xff1f;人生旅途&#xff0c;失业犹如山重水复&#xff0c;焦虑似迷雾遮望眼。古语云&#xff1a;“山不厌高&#xff0c;海不厌深。”心之向往&#xff0c;冥想便是那披荆斩棘之斧&#xff0c;如何带你走出困境&#xff1f; “静以修身”&#xff0c…

TikTok Shop认知课 打通TK小店全流程

资料 001-先导课.mp4 002-如何用思维导图工具做课程笔记.mp4 003-TTS入驻模式.mp4 004-如何获取店铺.mp4 005-TTS店铺注册全流程,mp4 006-店铺整体运营思路.mp4 007-运营的几个误区.mp4 008-新店起店准备工作,mp4 009-规店铺风控注意事项,mp4 010-店铺基础设置之店铺…

C语言指针的初级练习

前言 从0开始记录我的学习历程&#xff0c;我会尽我所能&#xff0c;写出最最大白话的文章&#xff0c;希望能够帮到你&#xff0c;谢谢。 提示&#xff1a;文章作者为初学者&#xff0c;有问题请评论指正&#xff0c;感谢。 哥们嗷 不知道你和我是否一样在学习C语言指针的时…

非成对意象翻译中的内容制约范式再思考

Rethinking the Paradigm of Content Constraints in Unpaired Image-to-Image Translation 非成对意象翻译中的内容制约范式再思考 Xiuding Cai1 2, Yaoyao Zhu1 2, Dong Miao1 2, Linjie Fu1 2, Yu Yao1 2 蔡秀定 1 2 、朱瑶瑶 1 2 、苗东 1 2 、付林杰 1 2 、余瑶 1 2 Corre…

精选合作伙伴:如何挑选最适合您小程序商城开发的软件公司

在选择一家合适的软件公司来协助您开发并运营小程序商城时&#xff0c;选择过程无疑是一项关键而复杂的任务。市场上的软件公司繁多&#xff0c;各具特色&#xff0c;那么&#xff0c;如何在这众多的选择中找到最适合您的合作伙伴呢&#xff1f;以下将从需求梳理、公司实力评估…

VC++6.0 常用的文件对话框和目录选择对话框

1&#xff0c;文件对话框 //1,弹出文件打开对话框CString strFileName "";char szFilter[] {"exe files(*.exe)|*.exe|All Files(*.*)|*.*|"};CFileDialog dlg(TRUE,NULL,NULL,OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT,szFilter,NULL);if(dlg.DoModal() …