C++进阶(3): 二叉搜索树

二叉搜索树的概念

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

  • 若它的左子树不为空,则左子树上所有的节点的值都小于等于 根节点的值
  • 若它的右子树不为空,则右子树上所有的节点的值都大于等于 根节点的值
  • 它的左右子树也分别为二叉搜索树
  • 二叉搜索树可以支持插入相同的值(multimap/multiset),也可以不支持插入相等的值(map/set)

二叉搜索树的性能分析

  1. 最优的情况:二叉搜索树为完全二叉树(或者接近完全二叉树),它的高度是:O(log2 N)
  2. 最坏的情况:二叉搜索树退化为单支树(类似于单支),它的高度是:O(N/2)

所以综合而言二叉搜索树增删改时间复杂度是:O(N)
但是这样的效率显然无法满足我们的需求,后续的博客我将介绍二叉搜索树的变形,平衡二叉树AVL树和红黑树,才能适用于我们在内存在存储和搜索数据。

最好的情况
最坏的情况

二叉搜索树的插入

不用递归,采用更简单的循环

插入的具体步骤如下:

  1. 树为空,则直接新增节点,赋值给root指针
  2. 树不为空,按照二叉搜索树性质,插入值比当前节点大往右走,插入值比当前节点小往左走,找到空位置,插入新节点。
  3. 如果支持插入相同的值,插入值跟当前节点相等的值可以往右走,也可以往走左走,找到空位置,插入新节点(要注意保持逻辑的一致性,插入相同的值不要一会向右走,一会向左走)

二叉搜索树的查找

  1. 从根节点开始比较,查找x,x比根节点的值大则向右边走查找,x比根节点的值小则向左边走查找
  2. 最多查找高度次,走到空时,还没找到x,那么这个值在这个二叉搜索树中不存在
  3. 如果不支持插入相同的值,则找到x后可以直接返回
  4. 如果支持插入相同的值,则意味着可能存在多个x,一般要求查找中序的第一个x

二叉搜索树的删除

首先查找元素是否在二叉搜索树中,如果不存在,则返回false
如果查找元素存在则分为以下四个情况进行分别处理:(假设要删除的节点为N)(分类依据:孩子的个数)

  1. 要删除的节点N左右孩子均为空(即N为叶子节点)
  2. 要删除的节点N左孩子为空,右孩子不为空
  3. 要删除的节点N左孩子不为空,右孩子为空
  4. 要删除的节点N左右孩子均不为空

对于以上四种情况的解决办法:

  1. 把N节点的父亲对应孩子指针指向空,直接删除N节点(1可以和2.3一起处理)
  2. 把N节点的父亲对应孩子指针指向N的右孩子,直接删除N节点
  3. 把N节点的父亲对应孩子指针指向N的左孩子,直接删除N节点
  4. 无法直接删除N节点,因为N的两个孩子无处安放,只能采用替代法将其删除:将N左子树的最大值的节点R(最右节点)或者N右子树的最小值的节点R(最左节点)代替N,因为这两个节点中任意一个,放到N的节点,都满足二叉搜索树的规则。代替N的意思就是N和R的两个节点的值交换,转而变成删除R节点,R节点符合情况2或者情况3,可以直接删除
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

实现代码

template<class K>struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};//搜索二叉树:
template<class K>class BSTree
{typedef BSTNode<K> Node;public:bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);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);if (parent->_key > key){parent->_left = cur;}else{parent->_right = cur;}return true;}bool 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 true;}return false;}}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{if (nullptr == cur->_left){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else if (parent->_right = cur){parent->_right = cur->_right;}}delete cur;return true;}else if (nullptr == cur->_right){if (nullptr == parent){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{Node* leftMaxP = cur;Node* leftMax = cur->_left;while (leftMax->right){leftMaxP = leftMax;leftMax = leftMax->_right;}cur->_key = leftMax->_key;if (leftMaxP->_left == leftMax){leftMaxP->_left = leftMax->_left;}else{leftMaxP->_right = leftMax->_left;}delete leftMax;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}
private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}private:Node* _root = nullptr;
};

二叉搜索树key和key/value使用场景

key搜索场景

只有key作为关键码,在二叉树结构中只需要存储key即可,搜索场景只需要判断key在不在。key的搜索场景支持二叉树的增删查,而不支持二叉树的修改,会破坏二叉树的结构。

key/value搜索场景

每一个关键码key,都有与它对应的值value,value可以是任何类型对象。树的结构中(每个节点)除了需要存储key,还需要存储value,增/删/查还是以key为关键字走二叉树的规则进行比较,可以快速找到与key对应的value。并且key/value的搜索场景支持了二叉树的修改,但是仍然不可以修改key,只可以修改value。

key/value二叉搜索树代码实现

	template<class K, class V>struct BSTNode{K _key;V _value;BSTNode<K, V>* _left;BSTNode<K, V>* _right;BSTNode(const K& key, const K& value):_key(key), _value(value), _left(nullptr), _right(nullptr){}};//搜索二叉树:template<class K, class V>class BSTree{typedef BSTNode<K, V> Node;public:BSTree() = default;BSTree(const BSTree<K, V>& m){_root = Copy(m._root);}BSTree<K, V>& operator=(BSTree<K, V> m){swap(_root, m._root);return *this;}~BSTree(){Destroy(_root);_root = nullptr;}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* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key > key){parent = cur;cur = cur->_left;}else if (cur->_key < key){parent = cur;cur = cur->_right;}else{if (nullptr == cur->_left){if (nullptr == parent){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;return true;}else if (nullptr == cur->_right){if (nullptr == parent){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else{Node* rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin){rightMinP->_left = rightMin->_right;}else{rightMinP->_right = rightMin->_right;}delete rightMin;return true;}}}return false;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (nullptr == root){return;}_InOrder(root->_left);cout << root->_key << ':' << root->_value << endl;_InOrder(root->right);}void Destroy(Node* root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (nullptr == root){return nullptr;}Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}private:Node* _root = nullptr;};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

指针(4)

目录 1. 数组名的理解 但是有两个例外 sizeof(数组名)&#xff0c; • &数组名 2. ⼀维数组传参的本质 2.1指针打印数组 3.冒泡排序 4.二级指针 5 指针数组 5.1 指针数组模拟二维数组 1. 数组名的理解 前面数组中提到 数组名的地址就是首元素的地址&#xff0c; 代…

国庆节快乐

葡萄城在这里祝大家国庆快快乐&#xff1a; 10月葡萄城活动&#xff1a; 公开课 【从软件应用走向数据应用——葡萄城技术赋能数据挖掘】 新版本发布&#xff1a; 活字格 V10.0 Update1新版本发布

【cache】浅析四种常用的缓存淘汰算法 FIFO/LRU/LFU/W-TinyLFU

本文浅析淘汰策略与工作中结合使用、选取&#xff0c;并非针对算法本身如何实现的 文章目录 FIFOLFULRUW-TinyLFU实践与优化监控与调整 FIFO first input first output &#xff0c; 先进先出&#xff0c;即最早存入的元素最先取出&#xff0c; 典型数据结构代表&#xff1a;…

2024年10月1日历史上的今天大事件早读

989年10月1日 北宋政治家范仲淹出生 1814年10月1日 反法联盟各参加国在奥地利首都维也纳召开会议 1927年10月1日 苏联开始实施第一个五年计划 1930年10月1日 中国收回威海卫租界 1931年10月1日 日本人在东北拼凑伪政权 1938年10月1日 大型纪录片《延安与八路军》开拍 194…

65.【C语言】联合体

目录 目录 1.定义 2.格式 3.例题 答案速查 分析 4.练习 答案速查 分析 5.相同成员的联合体和结构体的对比 6.联合体的大小计算 2条规则 答案速查 分析 练习 答案速查 分析 7.联合体的优点 8.匿名联合体 1.定义 和结构体有所不同,顾名思义:所有成员联合使用同…

VS code user setting 与 workspace setting 的区别

VS code user setting 与 workspace setting 的区别 引言正文引言 相信有不少开始接触 VS code 的小伙伴会有疑问,user setting 与 workspace setting 有什么区别呢?这里我们来说明一下 正文 首先,当我们使用 Ctrl + Shift + P 打开搜索输入 setting 后,可以弹出 4 个se…

【2023工业3D异常检测文献】M3DM: 基于混合融合的多模态工业异常检测方法

Multimodal Industrial Anomaly Detection via Hybrid Fusion 1、Background 随着3D传感器的发展&#xff0c;最近发布了具有2D图像和3D点云数据的MVTec-3D AD数据集&#xff0c;促进了多模态工业异常检测的研究。 无监督异常检测的核心思想是找出正常表示与异常之间的差异。…

Android Studio Dolphin 中Gradle下载慢的解决方法

我用的版本Android Studio Dolphin | 2021.3.1 Patch 1 1.Gradle自身的版本下载慢 解决办法&#xff1a;修改gradle\wrapper\gradle-wrapper.properties中的distributionUrl 将https\://services.gradle.org/distributions为https\://mirrors.cloud.tencent.com/gradle dis…

2024 maya的散布工具sppaint3d使用指南

目前工具其实可以分为三个版本 1 最老的原版 时间还是2011年的&#xff0c;只支持python2版的maya 2 作者python3更新版 后来作者看maya直到2022上还是没有类似好用方便的工具&#xff0c;于是更新到了2022版本 这个是原作者更新的2022版本&#xff0c;改成了python3&#…

SpringBoot——基础配置

但是还需要删除pom.xml中的标签——模板的文件也同样操作 banner的选项——关闭 控制台 日志 banner图片的位置——还会分辨颜色 在 Java 的日志框架&#xff08;如 Logback、Log4j2 等&#xff09;中&#xff0c;logging.level.root主要用于设置根日志记录器的日志级别…

IIS开启后https访问出错net::ERR_CERT_INVALID

安装ArcGIS server和portal等&#xff0c;按照说明上&#xff0c;先开启iis&#xff0c;在安装server、datastore、portal、webadapter等&#xff0c;遇到一些问题&#xff1a; 问题1 访问http正常&#xff0c;访问https出错&#xff1a; 解决方案 从这里找到解决方案&…

TDesign组件库+vue3+ts 如何视觉上合并相同内容的table列?(自定义合并table列)

背景 当table的某一列的某些内容相同时&#xff0c;需要在视觉上合并这一部分的内容为同个单元格 如上图所示&#xff0c;比如需要合并当申请人为同个字段的列。 解决代码 <t-table:data"filteredData":columns"columns":rowspan-and-colspan"…

宝塔部署vue项目出现的各种问题

使用宝塔面板&#xff0c;网站页面&#xff0c;构建php静态网页 问题一&#xff1a;图片等静态资源无法加载 找到真正请求的url&#xff0c; 然后在项目目录下面创建对应的目录&#xff0c;将资源放入 问题二&#xff1a;刷新出现404 在这里任意位置添加 ## 添加上这个配…

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-28

计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-28 目录 文章目录 计算机前沿技术-人工智能算法-大语言模型-最新研究进展-2024-09-28目录前言1. Cognitive phantoms in LLMs through the lens of latent variables摘要研究背景问题与挑战创新点算法模型实验效果…

业务封装与映射 -- AMP BMP GMP

概述 不同单板支持不同的封装模式&#xff0c;主要包括: AMP (Asynchronous Mapping Procedure&#xff0c;异步映射规程)BMP (Bit-synchronous Mapping Procedure&#xff0c;比特同步映射规程)GMP (Generic Mapping Procedure&#xff0c;通用映射规程) AMP/BMP&#xff1a…

解决VS Code工具在终端执行命令的时候无法加载文件

错误&#xff1a;tsc : 无法加载文件 E:\KTSP\WaitForMe\install\nodejs\node_global\tsc.ps1,因为在此系统上禁止运行脚本 问题原因&#xff1a;由于windwos11上默认上关闭了运行脚本的策略&#xff0c;所以我们要设置允许执行脚本 1.WinX打开终端管理员输入 Get-ExecutionP…

【每天学个新注解】Day 10 Lombok注解简解(九)—@Accessors

在之前的几天&#xff0c;我们系统学习了Lombok的常见注解&#xff0c;并且将其官网stable中的所有注解都讲解了一编&#xff0c;接下来会通过两到三天的时间将Lombok目前正在试验的&#xff08;experimental&#xff09;注解简单过一遍&#xff0c;以下为experimental状态的所…

uniapp框架中实现文件选择上传组件,可以选择图片、视频等任意文件并上传到当前绑定的服务空间

前言 uni-file-picker是uniapp中的一个文件选择器组件,用于选择本地文件并返回选择的文件路径或文件信息。该组件支持选择单个文件或多个文件,可以设置文件的类型、大小限制,并且可以进行文件预览。 提示:以下是本篇文章正文内容,下面案例可供参考 uni-file-picker组件具…

学习记录:js算法(五十):二叉树的右视图

文章目录 二叉树的右视图我的思路网上思路 总结 二叉树的右视图 给定一个二叉树的 根节点 root&#xff0c;想象自己站在它的右侧&#xff0c;按照从顶部到底部的顺序&#xff0c;返回从右侧所能看到的节点值。 图一&#xff1a; 示例 1:如图一 输入: [1,2,3,null,5,null,4] …

SigmaStudio控件Cross Mixer\Signal Merger算法效果分析

衰减与叠加混音算法验证分析一 CH2:输入源为-20dB正弦波1khz CH1叠加混音&#xff1a;参考混音算法https://blog.csdn.net/weixin_48408892/article/details/129878036?spm1001.2014.3001.5502 Ch0衰减混音&#xff1a;外部多个输入源做混音时&#xff0c;建议参考该算法控件&…