【C++】STL二叉搜索树——map与set容器的基础结构

目录

前言

1.二叉搜索树的概念

1.1基本结构

1.2性能分析

2.二叉搜索树的实现

2.1创建

2.2插入

2.3查找与遍历

2.4删除

3.二叉搜索树类代码

前言

C++中STL的map与set容器广泛应用于实践过程中，本文将详细分析容器最基础的二叉搜索树结构，为后续map与set容器的学习打下更好基础。更多C++内容可前往->|C++主题专栏|<-

1.二叉搜索树的概念

1.1基本结构

二叉搜索树是一种便于快速查找(搜索)数据的搜索结构，也称二叉排序树。它或是棵空树，又或是满足以下性质的树：

二叉搜索树的性质

• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值
• 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结点的值
• 它的左右⼦树也分别为⼆叉搜索树
• ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义

如上两棵树都是二叉搜索树，当然第二棵树的重复元素(10)可以在父节点的左子树也可以在父节点的右子树。但我们常用的一般是左边无重复元素的二叉搜索树。

1.2性能分析

以上面第一棵树为例：这种情况下的树基本为完全二叉树，其搜索性能(时间复杂度)与树的高度相同为logN。但这是最优的情况，若二叉搜索树的数据插入满足一定条件，就会形成类似单支树的情况(如下图)，这种情况下的搜索性能就会降为O(N)。

因此综合考虑，普通搜索二叉树的搜索性能就是O(N)，但这样的效率显然不够理想，后面在实际应用时使用的是优化过平衡二叉树(AVL树、红黑树)。

其次对于查找功能，在数组中的二分查找算法也能实现O(logN)级别的查找效率，但二分查找算法对比于二叉搜索树有着明显的缺点：

二分查找的缺点

1. 需要存储在⽀持下标随机访问的结构中，并且有序
2. 插⼊和删除数据效率很低。存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据

这里二叉搜索树的价值也更为显著。

2.二叉搜索树的实现

二叉搜索树的核心功能是增、删、查功能的实现，修改数据值的话主要会破坏搜索结构，进而大大降低效率，因此一般不会实现。下面会从逻辑->代码依次实现各部分功能。

2.1创建

二叉搜索的底层结构还是一个链式二叉树，因此需要结点，主体部分用根来连接各个结点即可。结点中需要储存数据，以及左右孩子结点。但要注意的是搜索结构中显示进行搜索的数据我们一般称为关键字(key)。

其次结点的构造函数只需保证让key值的构造，左右孩子指针置空即可。代码如下：

#pragma once
#include<iostream>
using namespace std;//树结点
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(K x):_key(x),_left(nullptr),_right(nullptr){}
};//二叉搜索树
template<class K>
class BSTree
{
private:typedef BSTNode<K> Node
public:private:Node* _root = nullptr;
};

2.2插入

插入分为为空插入与非空插入。当树为空的时候只需让根结点指向新结点即可。

当树非空时，按照二叉搜索树的性质，插入值比当前结点大就往右子树走，插入值比当前结点小就往左子树走。

当遇见插入值与当前结点相同时就可以直接返回，表示结构中已有此值。但为了区分void返回的插入成功与失败，我们插入函数的返回类似设置为bool。

以在下图树中插入5为例：

                                        

        

这里最需要注意的是最后一部得到5应该插入的位置时，那个位置是为空的，因此需要在过程中记录应该插入位置的父结点。代码如下：

//插入
bool insert(const K& key)
{//分为根为空或不为空if (_root == nullptr){_root = new Node(key);return true;}//不为空则寻找合适位置Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else if(key == cur->_key){return false; //不插入重复数据}}//插入左还是右if (key > parent->_key){parent->_right = new Node(key);}else{parent->_left = new Node(key);}return true;
}

除了迭代的方式插入，也可通过递归进行插入：

private://递归插入bool _insert(Node*& root, const K& x){if (root == nullptr){root = new Node(x);return true;}if (root->_key == x){return false;}return root->_key > x ? _insert(root->_left, x) : _insert(root->_right, x);}public://递归插入bool REinsert(const K& x){return _insert(_root, x);}

这里最值得注意的是递归插入利用引用特性，能直接修改最后空位置的结点。

2.3查找与遍历

二叉搜索树的查找逻辑与插入类似，不同的是遇见相同的值就返回当前结点，若树遍历完没找到就返回空。但查找的前提是树不为空。

二叉搜索树的遍历主要实现方式为中序遍历，这部分主要注意的是在类中显示成员函数实现递归，后面代码实现后再进行分析。

private://方便函数内部传参void _inorder(Node* root){if (root == nullptr){return;}_inorder(root->_left);cout << root->_key << ' ';_inorder(root->_right);}
public://遍历——中序遍历void inorder(){_inorder(_root);cout << endl;}//查找Node* find(const K& x){assert(_root != nullptr);Node* cur = _root;while (cur){if (cur->_key < x){cur = cur->_right;}else if (cur->_key > x){cur = cur->_left;}else if(cur->_key == x){return cur;}}return nullptr;}

 递归调用时因要传参数，而在类外部无法直接传树的根结点，因此可以直接在类中进行内部函数嵌套，进而实现递归调用。

2.4删除

二叉搜索树的删除是最复杂的，因为当结点删除时可能也会涉及搜索结构的破坏，但这里的破坏情况会比修改简单。

具体删除情况可以分为以下三种(均以下图树为例)：

                ​​​​​​​        

1.要删除结点N左右孩⼦均为空。这时可以直接将改结点删除，并将父节点置为空。

        

2.要删除的结点N左孩⼦或右孩子为空，另一孩子结点不为空。这种情况下要删改结点，可以直接让该结点的父亲指向该结点的孩子结点。

3.要删除的结点N左右孩⼦结点均不为空。这种情况⽆法直接删除N结点，因为N的两个孩⼦⽆处安放，只能⽤替换法删除。找N左⼦树的值最⼤结点R(最右结点)或者N右⼦树的值最⼩结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满⾜⼆叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转⽽变成删除R结点，R结点符合情况2或情况3，可以直接删除。

可以看到这里本质是让其变为第一种情况再进行删除。

综上进行代码实现：

public://删除bool erase(const K& x){//内部查找Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->_key < x){cur = cur->_right;}else if (cur->_key > x){cur = cur->_left;}else //找到了,进行分情况删除{if(cur->_left == nullptr) //左孩子为空{if (cur != _root){//父亲指向不为空的右if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}else{_root = cur->_right;}delete cur;}else if(cur->_right == nullptr) //右孩子为空{if (cur != _root){//父亲指向不为空的右if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}else{_root = cur->_left;}delete cur;}else //左右都不为空{//查找合适结点——左子树最大Node* curLeftmax = cur->_left;Node* maxParent = cur;while (curLeftmax->_right){maxParent = curLeftmax;curLeftmax = curLeftmax->_right;}//交换key值swap(cur->_key, curLeftmax->_key);if (curLeftmax == maxParent->_left)maxParent->_left = curLeftmax->_right;elsemaxParent->_right = curLeftmax->_right;delete curLeftmax;}return true;}}return false;}

这里实际情况并没有将第一种分化出来，因为当被删除结点的孩子都为空时，其父亲无论指向左孩子还是右孩子仍然同样置空。

其次是最后一种情况只交换两个结点的值，不用再进行复杂的结点迁移，利于直接保持原树顺序。

3.二叉搜索树类代码

#pragma once
#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;//树结点
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(K x):_key(x),_left(nullptr),_right(nullptr){}
};//二叉搜索树
template<class K>
class BSTree
{
private:typedef BSTNode<K> Node;//方便函数内部传参void _inorder(Node* root){if (root == nullptr){return;}_inorder(root->_left);cout << root->_key << ' ';_inorder(root->_right);}//递归插入bool _insert(Node*& root, const K& x){if (root == nullptr){root = new Node(x);return true;}if (root->_key == x){return false;}return root->_key > x ? _insert(root->_left, x) : _insert(root->_right, x);}public:BSTree() = default;//调用默认构造即可//插入bool insert(const K& key){//分为根为空或不为空if (_root == nullptr){_root = new Node(key);return true;}//不为空则寻找合适位置Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (key > cur->_key){cur = cur->_right;}else if (key < cur->_key){cur = cur->_left;}else if(key == cur->_key){return false; //不插入重复数据}}if (key > parent->_key){parent->_right = new Node(key);}else{parent->_left = new Node(key);}return true;}//递归插入bool REinsert(const K& x){return _insert(_root, x);}//删除bool erase(const K& x){//内部查找Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->_key < x){cur = cur->_right;}else if (cur->_key > x){cur = cur->_left;}else //找到了,进行分情况删除{if(cur->_left == nullptr) //左孩子为空{if (cur != _root){//父亲指向不为空的右if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}else{_root = cur->_right;}delete cur;}else if(cur->_right == nullptr) //右孩子为空{if (cur != _root){//父亲指向不为空的右if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}else{_root = cur->_left;}delete cur;}else //左右都不为空{//查找合适结点——左子树最大Node* curLeftmax = cur->_left;Node* maxParent = cur;while (curLeftmax->_right){maxParent = curLeftmax;curLeftmax = curLeftmax->_right;}//交换key值swap(cur->_key, curLeftmax->_key);if (curLeftmax == maxParent->_left)maxParent->_left = curLeftmax->_right;elsemaxParent->_right = curLeftmax->_right;delete curLeftmax;}return true;}}return false;}//遍历——中序遍历void inorder(){_inorder(_root);cout << endl;}//查找Node* find(const K& x){assert(_root != nullptr);Node* cur = _root;while (cur){if (cur->_key < x){cur = cur->_right;}else if (cur->_key > x){cur = cur->_left;}else if(cur->_key == x){return cur;}}return nullptr;}private:Node* _root = nullptr;
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/web/92765.shtml
繁体地址，请注明出处：http://hk.pswp.cn/web/92765.shtml

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

相关文章

基于Spring Boot和SSE的实时消息推送系统

基于Spring Boot和SSE的实时消息推送系统

一、SSE技术深度解析 1.1 协议工作原理 #mermaid-svg-u7ZBlEsXcn68R5a8 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-u7ZBlEsXcn68R5a8 .error-icon{fill:#552222;}#mermaid-svg-u7ZBlEsXcn68R5a8 .error-text{fi…
阅读更多...
Day 40 训练和测试的规范写法

Day 40 训练和测试的规范写法

知识点回顾&#xff1a; 彩色和灰度图片测试和训练的规范写法&#xff1a;封装在函数中展平操作&#xff1a;除第一个维度batchsize外全部展平dropout操作&#xff1a;训练阶段随机丢弃神经元&#xff0c;测试阶段eval模式关闭dropout 作业&#xff1a;仔细学习下测试和训练代…
阅读更多...
分析代码并回答问题

分析代码并回答问题

代码 <template><div>Counter: {{ counter }}</div><div>Double Counter: {{ doubleCounter }}</div> </template><script setup lang"ts"> import { ref, computed } from "vue";const counter ref(0);const …
阅读更多...
在macOS上扫描192.168.1.0/24子网的所有IP地址

在macOS上扫描192.168.1.0/24子网的所有IP地址

在macOS上扫描192.168.1.0/24子网的所有IP地址&#xff0c;可以通过终端命令实现。以下是几种常用方法&#xff1a; 使用ping命令循环扫描 打开终端执行以下脚本&#xff0c;会逐个ping测试192.168.1.1到192.168.1.254的地址&#xff0c;并过滤出有响应的IP&#xff1a; for i …
阅读更多...
Java基础05——类型转换(本文为个人学习笔记，内容整理自哔哩哔哩UP主【遇见狂神说】的公开课程。 ＞ 所有知识点归属原作者，仅作非商业用途分享）

Java基础05——类型转换(本文为个人学习笔记，内容整理自哔哩哔哩UP主【遇见狂神说】的公开课程。 ＞ 所有知识点归属原作者，仅作非商业用途分享）

Java基础05——类型转换 类型转换 由于Java是强类型语言&#xff0c;所以要进行有些运算的时候&#xff0c;需要用到类型转换。 如&#xff1a;byte(占1个字节)&#xff0c;short(占2个字节)&#xff0c;char(占2个字节)→int(4个字节)→long(占8个字节)→float(占4个字节)→do…
阅读更多...
mysql基础（二）五分钟掌握全量与增量备份

mysql基础（二）五分钟掌握全量与增量备份

全量备份 Linux环境 数据备份 数据库的备份与恢复有多中方法&#xff0c;通过mysql自带的mysqldump工具可对数据库进行备份。语法&#xff1a; mysqldump -u username -p password --databases db_name > file_name .sql说明&#xff1a; -u参数指定用户名&#xff0c;usern…
阅读更多...
使用Windbg分析多线程死锁项目实战问题分享

使用Windbg分析多线程死锁项目实战问题分享

目录 1、问题描述 2、使用.effmach x86命令切换到32位上下文 3、切换到UI线程&#xff0c;发现UI线程死锁了 4、使用!locks命令查看临界区锁的详细信息&#xff0c;遇到了问题 5、使用dt命令查看临界区对象信息&#xff0c;找到发生死锁的多个线程 6、用户态锁与内核态锁…
阅读更多...
防火墙组网方式总结

防火墙组网方式总结

一、部署模式&#xff1a;灵活适配多样网络环境下一代防火墙&#xff08;NGAF&#xff09;具备极强的网络适应能力&#xff0c;支持五种核心部署模式&#xff0c;可根据不同网络需求灵活选择。路由模式&#xff1a;防火墙相当于路由器&#xff0c;位于内外网之间负责路由寻址&a…
阅读更多...
AI大模型：（二）5.1 文生视频（Text-to-Video）模型发展史

AI大模型：（二）5.1 文生视频（Text-to-Video）模型发展史

目录 1.介绍 2.发展历史 2.1.早期探索阶段（2015-2019） 2.1.1.技术萌芽期 2.1.2.RNN/LSTM时代 2.2.技术突破期（2020-2021） 2.2.1 Transformer引入视频生成 2.2.2 扩散模型的兴起 2.3.商业化突破期（2022-2023） 2.3.1 产品化里程碑 2.3.2 竞争格局形成 2.4.革命…
阅读更多...
14mm寻北仪能否塞进液压支架生死缝隙？

14mm寻北仪能否塞进液压支架生死缝隙？

在煤矿井下世界的方寸之间&#xff0c;液压支架的每个关键节点都承载着千钧重压。顶梁铰接点、立柱顶端、掩护梁角落&#xff0c;恰恰是空间最为局促的“禁区”。ER-MNS-10A MEMS寻北仪应运而生&#xff01;它采用了先进的MEMS陀螺技术&#xff0c;以14mm至薄高度、40g极致轻盈…
阅读更多...
python之浅拷贝深拷贝

python之浅拷贝深拷贝

文章目录潜拷贝(shallow copy)深拷贝(deep copy)总结一下python的浅拷贝和深拷贝.潜拷贝(shallow copy) python中潜拷贝指的是:构造一个新的复合对象&#xff0c;然后将原对象中的对象引用插入其中 平常开发过程中潜拷贝是比深拷贝更常见的场景. 比如编程中使用到的一些基本的…
阅读更多...
普通大学本科生如何入门强化学习？

普通大学本科生如何入门强化学习？

问题:你平时是如何紧跟大型语言模型和智能体技术前沿的&#xff1f;有哪些具体的学习和跟踪方式&#xff1f;回答:我会通过“输入-内化-实践”结合的方式跟踪前沿。首先&#xff0c;学术动态方面&#xff0c;每天花10分钟浏览arXiv的http://cs.CL和http://cs.AI板块&#xff0c…
阅读更多...
新手向:Python实现数据可视化图表生成

新手向:Python实现数据可视化图表生成

Python数据可视化入门&#xff1a;从零开始生成图表数据可视化是数据分析过程中不可或缺的关键环节&#xff0c;它通过将抽象的数字信息转化为直观的图形展示&#xff0c;帮助分析师和决策者更快速、更准确地发现数据中隐藏的模式、规律和发展趋势。在当今大数据时代&#xff0…
阅读更多...
VBA即用型代码手册：计算选择的单词数Count Words in Selection

VBA即用型代码手册：计算选择的单词数Count Words in Selection

我给VBA下的定义&#xff1a;VBA是个人小型自动化处理的有效工具。可以大大提高自己的劳动效率&#xff0c;而且可以提高数据的准确性。我这里专注VBA,将我多年的经验汇集在VBA系列九套教程中。作为我的学员要利用我的积木编程思想&#xff0c;积木编程最重要的是积木如何搭建及…
阅读更多...
DNS（域名系统）

DNS（域名系统）

分层结构根域名&#xff08;ipv4&#xff0c;13台&#xff09;&#xff0c;二级域名&#xff0c;三级域名……相关记录A将域名解析为ipv4地址AAAA将域名解析为ipv6地址MX指名该区域为邮件服务区PTR反向查询将主机名解析为域名NS记录服务器的名字CNAME别名查询方式递归查询迭代查…
阅读更多...
【大模型】强化学习算法总结

【大模型】强化学习算法总结

角色和术语定义 State&#xff1a;状态Action&#xff1a;动作Policy/actor model&#xff1a;策略模型&#xff0c;用于决策行动的主要模型Critic/value model&#xff1a;价值模型&#xff0c;用于评判某个行动的价值大小Reward model&#xff1a;奖励模型&#xff0c;用于给…
阅读更多...
基于梅特卡夫定律的开源链动2+1模式AI智能名片S2B2C商城小程序价值重构研究

基于梅特卡夫定律的开源链动2+1模式AI智能名片S2B2C商城小程序价值重构研究

摘要&#xff1a;梅特卡夫定律揭示了网络价值与用户数量的平方关系&#xff0c;在互联网经济中&#xff0c;连接的深度与形式正因人的参与发生质变。本文以开源链动21模式、AI智能名片与S2B2C商城小程序的协同应用为研究对象&#xff0c;通过实证分析其在社群团购、下沉市场等场…
阅读更多...
Ubuntu22.04安装CH340驱动及串口

Ubuntu22.04安装CH340驱动及串口

一、CH340驱动安装 1.1 查看USB设备能否被识别 CtrlAltT打开终端&#xff1a; lsusb 插入设备前&#xff1a; 插入设备后&#xff1a; 输出中包含ID 1a86:7523 QinHeng Electronics CH340 serial converter的信息&#xff0c;这表明CH340设备已经被系统识别。 1.2 查看USB转串…
阅读更多...
CPU缓存（CPU Cache）和TLB（Translation Lookaside Buffer）缓存现代计算机体系结构中用于提高性能的关键技术

CPU缓存（CPU Cache）和TLB（Translation Lookaside Buffer）缓存现代计算机体系结构中用于提高性能的关键技术

CPU缓存&#xff08;CPU Cache&#xff09;和TLB&#xff08;Translation Lookaside Buffer&#xff09;缓存是现代计算机体系结构中用于提高性能的关键技术。它们通过减少CPU访问数据和指令的延迟来提高系统的整体效率。以下是对这两者的详细解释&#xff1a; 1. CPU 缓存 CPU…
阅读更多...
唐扬·高并发系统设计40问

唐扬·高并发系统设计40问

课程下载&#xff1a;https://download.csdn.net/download/m0_66047725/91644703 00开篇词 _ 为什么你要学习高并发系统设计&#xff1f;.pdf 00开篇词丨为什么你要学习高并发系统设计&#xff1f;.mp3 01 _ 高并发系统&#xff1a;它的通用设计方法是什么&#xff1f;.pdf …
阅读更多...
最新文章

Copyright @ 2022~2023