【C++笔记】数据结构进阶之二叉搜索树(BSTree)

【C++笔记】数据结构进阶之二叉搜索树(BSTree)

🔥个人主页大白的编程日记

🔥专栏C++笔记


文章目录

  • 【C++笔记】数据结构进阶之二叉搜索树(BSTree)
    • 前言
    • 一.二叉搜索树的概念
    • 二.二叉搜索树的性能分析
    • 三.二叉搜索树的实现
      • 3.1二叉树的中序遍历
      • 3.2二叉搜索树的插入
      • 3.3二叉搜索树的查找
      • 3.4二叉搜索树的删除
    • 四.二叉搜索树key和key/value使用场景\
      • 4.1key搜索场景
      • 4.2key/value搜索场景
      • 4.3key_value结构的实现
      • 4.4二叉搜索树的拷贝构造和析构
    • 后言

前言

哈喽,各位小伙伴大家好!上期我们讲了C++三大特性之多态。今天我们来讲一下二叉搜索树(BSTree)。话不多说,我们进入正题!向大厂冲锋
在这里插入图片描述

一.二叉搜索树的概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
• 若它的左子树不为空,则左子树上所有结点的值都小于等于根结点的值
• 若它的右子树不为空,则右子树上所有结点的值都⼤于等于根结点的值
• 它的左右子树也分别为二叉搜索树
• ⼆叉搜索树中可以支持插入相等的值,也可以不支持插人相等的值,具体看使用场景定义,后续我们学习map/set/multimap/multiset系列容器底层就是二叉搜索树,其中map/set不之持插入相等值,multimap/multiset支持插如相等值

在这里插入图片描述

二.二叉搜索树的性能分析

在这里插入图片描述

二叉搜索树最多查找高度次。因此二叉搜索树的性能取决的树的高度。

  • 最优情况
    最优情况下,二叉搜索树为完全⼆叉树(或者接近完全⼆叉树),其高度为: log2 N

  • 最坏情况
    最差情况下,⼆叉搜索树退化为单⽀树(或者类似单⽀),其⾼度为: N在这里插入图片描述

所以综合而言⼆叉搜索树增删查改时间复杂度为: O(N)。

那么这样的效率显然是无法满足我们需求的,我们后续需要继续讲解⼆叉搜索树的变形,平衡二叉搜索树AVL树和红黑树,才能适用于我们在内存中存储和搜索数据。

  • 二分查找
    另外需要说明的是,二分查找也可以实现 O(log2 N) 级别的查找效率,但是而分查找有两大缺陷:
  1. 需要存储在支持下标随机访问的结构中,并且有序。
  2. 插入和删除数据效率很低,因为存储在下标随机访问的结构中,插入和删除数据⼀般需要挪动数据。

这里也就体现出了平衡⼆叉搜索树的价值。

三.二叉搜索树的实现

3.1二叉树的中序遍历


因为_root是私有成员,所以我们可以这样多套一层调用。

void Inorder()
{_Inorder(_root);cout << endl;
}
void _Inorder(const node* root)
{if (root == nullptr){return;}_Inorder(root->left);cout << root->_key << " ";_Inorder(root->right);
}

3.2二叉搜索树的插入

插入的具体过程如下:

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

bool Insert(const k& x)
{if (_root == nullptr)//插入根节点{_root = new node(x);return true;}node* cur = _root;node* parent = nullptr;//记录父亲节点while (cur){//介质不冗余/*if (x < cur->_key){parent = cur;cur = cur->left;}else if (x > cur->_key){parent = cur;cur = cur->right;}else{return false;}*///介质冗余if (x <= cur->_key)//相等插入左子树{parent = cur;cur = cur->left;}else if (x > cur->_key){parent = cur;cur = cur->right;}}if (x > parent->_key){parent->right = new node(x);}else//相等插入左子树{parent->left = new node(x);}return true;
}

介质冗余:

介质不冗余:
在这里插入图片描述

3.3二叉搜索树的查找

插⼊的具体过程如下:

  1. 树为空,则直接新增结点,赋值给root指针
  2. 树不空,按⼆叉搜索树性质,插入值比当前结点大往右⾛,插入值比当前结点小往左走,找到空位
    置,插入新结点。
  3. 如果支持插入相等的值,插⼊值跟当前结点相等的值可以往右走,也可以往左走,找到空位置,插入新结点。(要注意的是要保持逻辑⼀致性,插⼊相等的值不要⼀会往右走,⼀会往左走)
    在这里插入图片描述
bool Find(const k& x)
{node* cur = _root;while (cur){if (x < cur->_key)//节点在左子树{cur = cur->left;}else if (x > cur->_key)//节点在右子树{cur = cur->right;}else{return true;//找到target}}return false;
}

3.4二叉搜索树的删除

⾸先查找元素是否在二叉搜索树中,如果不存在,则返回false。
如果查找元素存在则分以下四种情况分别处理:(假设要删除的结点为N)

  • 要删除结点N左右孩子均为空
  • 要删除的结点N左孩子位空,右孩子结点不为空
  • 要删除的结点N右孩子位空,左孩子结点不为空
  • 要删除的结点N左右孩子结点均不为空

对应以上四种情况的解决方案:

  • 左右为空
    把N结点的父亲对应孩子指针指向空,直接删除N结点(情况1可以当成2或者3处理,效果是⼀样的)

  • 左空右不空
    把N结点的父亲对应孩子指针指向N的右孩子,直接删除N结点

  • 右空左不空
    把N结点的父亲对应孩子指针指向N的左孩子,直接删除N结点
    在这里插入图片描述

    如果删除根节点直接修改_root。再删除节点即可。

  • 左右均不空
    无法直接删除N结点,因为N的两个孩子无处安放,只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N,因为这两个结点中任意⼀个,放到N的位置,都满足⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换,转而变成删除R结点,R结点符合情况2或情况3,可以直接删除。
    在这里插入图片描述

bool Erase(const k& x)
{node* cur = _root;node* parent = nullptr;while (cur){if (x < cur->_key){parent = cur;cur = cur->left;}else if (x > cur->_key){parent = cur;cur = cur->right;}else//找到删除节点{if (cur->left == nullptr)//左为空{if (cur == _root)//防止删除根节点{_root = cur->right;}else//判断连接父亲的左子树还是右子树{if (cur == parent->left){parent->left = cur->right;}else{parent->right = cur->right;}}delete cur;return true;}else if (cur->right == nullptr){if (cur == _root)//防止删除根节点{_root = cur->left;}else//判断连接父亲的左子树还是右子树{if (cur == parent->left){parent->left = cur->left;}else{parent->right = cur->left;}}delete cur;return true;}else{//替代节点的父亲初始化为删除节点防止不进去循环node* replaceparent = cur;//替代节点的父亲node* replace = cur->right;while (replace->left)//寻找右子树的最小节点{replaceparent = replace;replace = replace->left;}cur->_key = replace->_key;//替换根节点//判断连接父亲的左子树还是右子树if (replace == replaceparent->left){replaceparent->left = replace->right;}else{replaceparent->right = replace->right;}delete replace;return true;}}}return false;
}

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

4.1key搜索场景

只有key作为关键码,结构中只需要存储key即可,关键码即为需要搜索到的值,搜索场景只需要判断key在不在。key的搜索场景实现的⼆叉树搜索树⽀持增删查,但是不支持修改,修改key破坏搜索树结构了。

场景1:小区无人值守车库,小区车库买了车位的业主车才能进小区,那么物业会把买了车位的业主的车牌号录入后台系统,车辆进入时扫描车牌在不在系统中,在则抬杆,不在则提示非本小区车辆,无法进入。

场景2:检查⼀篇英文 章单词拼写是否正确,将词库中所有单词放入二叉搜索树,读取文章中的单词,查找是否在⼆叉搜索树中,不在则波浪线标红提示。

4.2key/value搜索场景

每⼀个关键码key,都有与之对应的值value,value可以任意类型对象。树的结构中(结点)除了需要存储key还要存储对应的value,增/删/查还是以key为关键字⾛⼆叉搜索树的规则进行比较,可以快速查找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树支持修改,但是不支持修改key,修改key破坏搜索树性质了,可以修改value。

场景1:简单中英互译字典,树的结构中(结点)存储key(英⽂)和vlaue(中文),搜索时输入英文,则同时
查找到了英文对应的中文。

场景2:商场无人值守车库,入口进场时扫描车牌,记录车牌和入场时间,出口离场时,扫描车牌,查找入场时间,⽤当前时间-入场时间计算出停车时长,计算出停车费用,缴费后抬杆,车辆离场。

场景3:统计⼀篇文章中单词出现的次数,读取⼀个单词,查找单词是否存在,不存在这个说明第⼀次出现,(单词,1),单词存在,则++单词对应的次数。

4.3key_value结构的实现

  • 结构的定义
    把节点封装,key_value多了一个V的类型。
    同时这里using可以当成typedef使用。
//key结构
template<class k>
struct BSTNode
{using node = BSTNode<k>;k _key;node* left;node* right;BSTNode(const k& key):_key(key), left(nullptr), right(nullptr){}
};
template<class k>
class BSTree
{using node = BSTNode<k>;
public:
private:node* _root = nullptr;
};
//key_value结构
template<class k, class v>
struct BSTNode
{using node = BSTNode<k, v>;k _key;v _value;node* left;node* right;BSTNode(const k& key, const v& value):_key(key), _value(value), left(nullptr), right(nullptr){}
};
template<class k, class v>
class BSTree
{using node = BSTNode<k, v>;
public:
private:node* _root = nullptr;
};
  • 查找和删除
    查找和删除的逻辑不需要改变。但是如果想知道查找的节点的value可以返回节点指针。同时如果允许介质冗余的话,那就需要查找中序的第一个,所以我们相同值时,先保留,继续去左子树查找即可。
node* Find(const k& x)
{node* ret = nullptr;node* cur = _root;while (cur){if (x < cur->_key){cur = cur->left;}else if (x > cur->_key){cur = cur->right;}else{ret = cur;//保留当前节点cur = cur->left;//继续向左子树查找中序的第一个}}return ret;
}
、、key_value结构
  • 插入

插入只需要多插入一个value值即可,逻辑不变。

bool Insert(const k& x, const v& v)
{if (_root == nullptr)//插入根节点{_root = new node(x, v);return true;}node* cur = _root;node* parent = nullptr;//保留父亲节点while (cur){/*介质不冗余*/if (x < cur->_key){parent = cur;cur = cur->left;}else if (x > cur->_key){parent = cur;cur = cur->right;}else{return false;}//介质冗余//if (x <= cur->_key)//相等插入到左子树//{//	parent = cur;//	cur = cur->left;//}//else if (x > cur->_key)//{//	parent = cur;//	cur = cur->right;//}}if (x > parent->_key){parent->right = new node(x, v);}else//相等插入左子树{parent->left = new node(x, v);}return true;
}

4.4二叉搜索树的拷贝构造和析构

  • 拷贝构造

直接new构造根节点,再让根节点连接递归构造的左右子树即可。注意如果按照插入的思路构造,那就必须是层序遍历节点插入,否则拷贝出来的子树就不一样。

BSTree(const BSTree<k,v>& x)
{_root = Copy(x._root);
}
node* Copy( node* x)
{if (x == nullptr){return x;}node* root = new node(x->_key, x->_value);root->left =Copy(x->left);root->right = Copy(x->right);return root;
}
  • 析构
    这里先析构左右子树在析构根节点即可。
	void Destory(const node* root){if (root == nullptr){return ;}Destory(root->left);Destory(root->right);delete root;}~BSTree(){Destory(_root);_root = nullptr;}
  • 赋值

这里先拷贝tmp,然后交换_root指针,函数结束后析构tmp空间。

BSTree<k, v>& operator = (BSTree<k, v> tmp)
{swap(_root,tmp._root);return *this;
}


后言

这就是数据结构进阶之二叉搜索树(BSTree)。大家自己好好消化!今天就分享到这!感谢各位的耐心垂阅!咱们下期见!拜拜~

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

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

相关文章

无线图传下的低延迟视频传输播放技术探讨

技术背景 无线图传技术即无线图像传输技术&#xff0c;是指不用布线&#xff08;线缆&#xff09;利用无线电波来传输图像数据的技术。 一、工作原理 无线图传技术主要涉及图像采集、编码、调制、发射、接收、解调、解码和图像显示等环节。 图像采集&#xff1a;通过摄像头…

Linux的开发工具(三)

条件编译 预处理本质&#xff1a;对代码进行裁剪 像网易云音乐有vip和普通用户&#xff0c;可以通过条件编译来&#xff0c;这样只用写一份代码&#xff0c;也只用维护一份代码&#xff0c;是vip就走vip代码&#xff0c;不是就普通用户代码&#xff0c;条件编译来动态裁剪。 …

VSCode 汉化教程【简洁易懂】

VSCode【下载】【安装】【汉化】【配置C环境&#xff08;超快&#xff09;】&#xff08;Windows环境&#xff09;-CSDN博客 我们安装完成后默认是英文界面。 找到插件选项卡&#xff0c;搜索“Chinese”&#xff0c;找到简体&#xff08;更具你的需要&#xff09;&#xff08;…

Ubuntu下的Doxygen+VScode实现C/C++接口文档自动生成

Ubuntu下的DoxygenVScode实现C/C接口文档自动生成 1、 Doxygen简介 Doxygen 是一个由 C 编写的、开源的、跨平台的文档生成系统。最初主要用于生成 C 库的 API 文档&#xff0c;但目前又添加了对 C、C#、Java、Python、Fortran、PHP 等语言的支持。其从源代码中提取注释&…

Linux网络——网络层

网络层的作用&#xff1a;在复杂的网络环境中确定一个合适的路径。 一.IP协议 IP存在的意义&#xff1a;IP地址提供一种能力&#xff0c;使得数据能够从主机B跨网络、可靠的送至主机A。 1.协议头格式 能够看出IP协议的格式与TCP协议存在很多相似之处&#xff0c;同样拥有4为首…

Shiro-550反序列化漏洞分析

&#x1f338; 环境配置 代码下载地址&#xff1a;https://codeload.github.com/apache/shiro/zip/refs/tags/shiro-root-1.2.4 下载完成之后&#xff0c;需要修改一下pom文件&#xff1a; 修改一下红色框中的配置。然后配置一下tomcat&#xff1a; 点击部署&#xff0c;然后…

【Rhino】【Python】Create a series of Blocks according to Value of object Property

文章目录 1. Complete Code Display2. Detailed Code Analysis2.1 Import and Setup2.2 Function Structure and Initial Setup2.3 Object Collection and Filtering2.4 Story Management System2.5 Locating Point Processing2.6 Object Organization by Story2.7 Block Creat…

CSP/信奥赛C++语法基础刷题训练(23):洛谷P1217:[USACO1.5] 回文质数 Prime Palindromes

CSP/信奥赛C语法基础刷题训练&#xff08;23&#xff09;&#xff1a;洛谷P1217&#xff1a;[USACO1.5] 回文质数 Prime Palindromes 题目描述 因为 151 151 151 既是一个质数又是一个回文数&#xff08;从左到右和从右到左是看一样的&#xff09;&#xff0c;所以 151 151 …

【探寻密码的奥秘】-001:解开密码的神秘面纱

目录 1、密码学概述1.1、概念1.2、目的1.3、应用场景 2、密码学的历史2.1、第一时期&#xff1a;古代密码时代2.2、第二时期&#xff1a;机械密码时代2.3、第三时期&#xff1a;信息密码时代2.4、第四时期&#xff1a;现代密码时代 3、密码学的基本概念3.1、一般通信系统3.2、保…

文件操作详解(1)

1.文件&#xff0c;文件与流&#xff0c;文件指针 2.文件的打开与关闭 3.文件的读写 文件的顺序读写&#xff1a; &#xff08;1&#xff09;fgetc 和 fputc &#xff08;2&#xff09;fgets 和 fputs &#xff08;3&#xff09;fscanf 和 fprintf &#xff08;4&#x…

基于YOLOv8深度学习的人体姿态摔倒检测与语音报警系统(PyQt5界面+数据集+训练代码)

随着人口老龄化进程的加速&#xff0c;摔倒事故逐渐成为威胁老年人健康和安全的主要问题之一。研究表明&#xff0c;摔倒不仅可能导致老年人骨折、头部受伤等严重的身体损伤&#xff0c;还可能引发心理恐惧和行动能力下降&#xff0c;从而降低其生活质量和独立性。如何快速、准…

jmeter5.6.3安装教程

一、官网下载 需要提前配置好jdk的环境变量 jmeter官网&#xff1a;https://jmeter.apache.org/download_jmeter.cgi 选择点击二进制的zip文件 下载成功后&#xff0c;默认解压下一步&#xff0c;更改安装路径就行(我安装在D盘) 实用jmeter的bin目录作为系统变量 然后把这…

差分进化算法原理与复现

目录 摘要1、算法原理1.1、种群初始化1.2、变异1.3、交叉1.4、选择 2、算法实现2.1、种群初始化2.2、变异2.3、交叉2.4、选择2.5、选取终代种群中最优秀个体 摘要 如何选取一组最佳的参数&#xff0c;使得代价函数值最优&#xff1f;这是优化算法做的事&#xff0c;一个直觉的…

搜索引擎中广泛使用的文档排序算法——BM25(Best Matching 25)

在搜索场景中&#xff0c;BM25能计算每个文档与查询的匹配度&#xff0c;从中找出最相关的文档&#xff0c;并按相关性高低排序展示。 要理解BM25&#xff0c;需要掌握以下几个关键概念&#xff1a; 1. 词频&#xff08;Term Frequency, TF&#xff09;&#xff1a;某关键词在文…

C语言笔记(自定义类型:结构体、枚举、联合体 )

前言 本文对自定义类型的结构体创建、使用、结构体的存储方式和对齐方式&#xff0c;枚举的定义、使用方式以及联合体的定义、使用和存储方式展开叙述&#xff0c;如有错误&#xff0c;请各位指正。 目录 前言 1 结构体 1.1 结构体的声明 1.2 结构体的自引用 1.3 结构体变…

【C++】list模拟实现(详解)

本篇来详细说一下list的模拟实现&#xff0c;list的大体框架实现会比较简单&#xff0c;难的是list的iterator的实现。我们模拟实现的是带哨兵位头结点的list。 1.准备工作 为了不和C库里面的list冲突&#xff0c;我们在实现的时候用命名空间隔开。 //list.h #pragma once #…

数字化工厂 MES试点方案全解析(三)

目 录 三、试点实施步骤 需求分析与方案设计阶段 系统开发与测试阶段 系统部署与培训阶段 试点运行与优化阶段 总结与评估阶段 三、试点实施步骤 需求分析与方案设计阶段 1、成立由企业生产、工艺、质量、设备、IT 等多部门人员组成的项目团队&#xff0c;与 MES 供应商共…

ShuffleNet V2:高效卷积神经网络架构设计的实用指南

摘要 https://arxiv.org/pdf/1807.11164 当前&#xff0c;神经网络架构设计大多以计算复杂度的间接指标&#xff0c;即浮点运算数&#xff08;FLOPs&#xff09;为指导。然而&#xff0c;直接指标&#xff08;例如速度&#xff09;还取决于其他因素&#xff0c;如内存访问成本…

【Opencv学习】PART1-图像基础处理

目录 一、图像的读入、显示和保存 1、读入图像 imread函数 范例 显示控制参数 2、显示图像 imshow函数 范例 tips waitkey函数 含义 delay参数: tips destoryAllWindows函数 3、保存图像 imwrite函数 范例 实操 01-读入显示保存 代码 结果 二、图像处理入…

硬中断关闭后的堆栈抓取方法

一、背景 性能和稳定性是一个计算机工程里的一个永恒的主题。其中尤其稳定性这块的问题发现和问题分析及问题解决就依赖合适的对系统的观测的手段&#xff0c;帮助我们发现问题&#xff0c;识别问题原因最后才能解决问题。稳定性问题里尤其底层问题里&#xff0c;除了panic问题…