★ C++进阶篇 ★ 二叉搜索树

Ciallo～(∠・ω< )⌒☆ ~ 今天，我将继续和大家一起学习C++进阶篇第三章----二叉搜索树 ~

 

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

澄岚主页：椎名澄嵐-CSDN博客

C++基础篇专栏：★ C++基础篇 ★_椎名澄嵐的博客-CSDN博客

C++进阶篇专栏：★ C++进阶篇 ★_椎名澄嵐的博客-CSDN博客

❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

目录

一  二叉搜索树的概念

二  二叉搜索树的性能分析

三  二叉搜索树的实现

3.1 二叉搜索树的基础结构

3.2 二叉搜索树的插入

3.3 二叉搜索树的中序遍历

3.4 二叉搜索树的查找

3.5 二叉搜索树的删除

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

4.1 key搜索场景

4.2 key/value搜索场景

一  二叉搜索树的概念

二叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:

  • 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值
  • 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值
  • 它的左右子树也分别为⼆叉搜索树
  • 二叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值

二  二叉搜索树的性能分析

最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其高度为： O(log N)

最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为： O( N/2 )

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

这样的效率显然是⽆法满⾜我们需求的，后续我们会继续学习⼆叉搜索树的变形，平衡二叉搜索树AVL树和红黑树，才能适⽤于我们在内存中存储和搜索数据。

三  二叉搜索树的实现

3.1 二叉搜索树的基础结构

  • 二叉树搜索的结点
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;using Node = BSTNode<K>; // 相同效果public:// ...private:Node* _root = nullptr;
};

3.2 二叉搜索树的插入

  • 树为空，则直接新增结点，赋值给root指针
  • 树不空，按⼆叉搜索树性质，插⼊值比1当前结点大往右走，插入值⽐当前结点小往左走，找到空位置，插⼊新结点。
  • 如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插⼊新结点。
bool _Insert(const K& key)
{// 树为空，则直接新增结点，赋值给root指针if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;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 (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

 

3.3 二叉搜索树的中序遍历

public:void InOrder(){_InOrder(_root);}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}

因为私有的成员函数调用时要传root变量，而root变量是私有的，所以要再写一个公有的函数在类里拿到root调用私有的中序遍历。

3.4 二叉搜索树的查找

  • 从根开始比较，查找x，x比根的值大则往右查找，x比根值小则往左查找。
  • 最多查找高度次，⾛到到空，还没找到，这个值不存在。
  • 如果不支持插⼊相等的值，找到x即可返回
  • 如果支持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。
bool Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return true;}}return false;
}

3.5 二叉搜索树的删除

⾸先查找元素是否在二叉搜索树中，如果不存在，则返回false。

查找元素存在时有四种情况：

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

解决方案：把N结点的⽗亲对应孩⼦指针指向N的右孩⼦，直接删除N结点

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

解决方案：把N结点的⽗亲对应孩⼦指针指向N的左孩⼦，直接删除N结点

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

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

bool Erase(const K& key)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else // 删除{if (cur->_left == nullptr) // 左为空{if (cur == _root) // 若删左为空时的根{_root = cur->_right; // 原根的右结点给根}if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;}else if(cur->_right == nullptr) // 右为空{if (cur == _root){_root = cur->_left;}if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}else // 左右都不为空{Node* replaceParent = cur;					Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if(replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}return false;
}

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

4.1 key搜索场景

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

  • 场景1：⼩区⽆⼈值守⻋库，⼩区⻋库买了⻋位的业主⻋才能进⼩区，那么物业会把买了⻋位的业主的⻋牌号录⼊后台系统，⻋辆进⼊时扫描⻋牌在不在系统中，在则抬杆，不在则提⽰⾮本⼩区⻋辆，⽆法进⼊。
  • 场景2：检查⼀篇英⽂⽂章单词拼写是否正确，将词库中所有单词放⼊⼆叉搜索树，读取⽂章中的单词，查找是否在⼆叉搜索树中，不在则波浪线标红提⽰。

4.2 key/value搜索场景

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

  • 场景1：简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中⽂)，搜索时输⼊英⽂，则同时查找到了英⽂对应的中⽂。
  • 场景2：商场⽆⼈值守⻋库，⼊⼝进场时扫描⻋牌，记录⻋牌和⼊场时间，出⼝离场时，扫描⻋牌，查找⼊场时间，⽤当前时间-⼊场时间计算出停⻋时⻓，计算出停⻋费⽤，缴费后抬杆，⻋辆离场。
namespace 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 V& value):_key(key),_value(value), _left(nullptr), _right(nullptr){}};template<class K, class V>class BSTree{using Node = BSTNode<K, V>;public:// 强制生成构造BSTree = default;BSTree(const BSTree& t){_root = Copy(t._root);}~BSTree(){Destory(_root);_root = nullptr;}BSTree& operator=(BSTree tmp){swap(_root, tmp._root);return *this;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}void Destory(Node* root){if (root == nullptr){return;}Destory(root->_left);Destory(root->_right);delete root;}bool Insert(const K& key, const V& value){// 树为空，则直接新增结点，赋值给root指针if (_root == nullptr){_root = new Node(key, value);return true;}Node* cur = _root;Node* parent = nullptr;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 (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;}bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else // 删除{if (cur->_left == nullptr) // 左为空{if (cur == _root) // 若删左为空时的根{_root = cur->_right; // 原根的右结点给根}if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr) // 右为空{if (cur == _root){_root = cur->_left;}if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}delete cur;}else // 左右都不为空{Node* replaceParent = cur;Node* replace = cur->_right;while (replace->_left){replaceParent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceParent->_left == replace)replaceParent->_left = replace->_right;elsereplaceParent->_right = replace->_right;delete replace;}return true;}}return false;}Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return cur;}}return nullptr;}void InOrder(){_InOrder(_root);cout << endl;}private:void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ':' << root->_value << ' ';_InOrder(root->_right);}private:Node* _root = nullptr;};
}

~ 完 ~

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

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

相关文章

从零开始学习TinyWebServer

从零开始学习TinyWebServer

写在前面 项目参考&#xff1a;https://github.com/qinguoyi/TinyWebServer 写作框架/图参考&#xff1a;https://blog.csdn.net/qq_52313711/article/details/136356042?spm1001.2014.3001.5502 原本计划是&#xff0c;先将项目代码大概看一遍&#xff0c;然后再着手实现一下…
阅读更多...
SOCKS5代理为何比HTTP代理更快？

SOCKS5代理为何比HTTP代理更快？

在代理类型的选择上&#xff0c;SOCKS5代理经常被认为比HTTP代理更快&#xff0c;这是因为它们在工作原理和功能实现上存在较大的差异。让我们来探讨一下&#xff0c;为什么SOCKS5代理的速度通常比HTTP代理要快。 1. 协议的差异 SOCKS5代理&#xff1a;它是一个通用的代理协议…
阅读更多...
【yolo破损纸板-包装盒-快递袋缺陷检测】

【yolo破损纸板-包装盒-快递袋缺陷检测】

yolo破损纸板-包装盒-快递袋缺陷检测 破损纸质包装盒检测方盒型快递包裹检测 破损纸质包装盒检测 数据集合模型 可视化 方盒型快递包裹检测 数据集和模型 train: ../train/images val: ../valid/images test: ../test/images nc: 1 names: - box_packet可视化
阅读更多...
初识linux（2）

初识linux（2）

接着上篇的初识linux(1)来接着说没看过的可以去看看 cp指令 语法&#xff1a;cp [选项] 源文件或目录 目标文件或目录 功能: 复制文件或目录 说明: cp指令用于复制文件或目录&#xff0c;如同时指定两个以上的文件或目录&#xff0c;且最后的目的地是一个已经存在的目录&#…
阅读更多...
华为HarmonyOS地图服务 5 - 利用UI控件和手势进行地图交互

华为HarmonyOS地图服务 5 - 利用UI控件和手势进行地图交互

场景介绍 本章节将向您介绍如何使用地图的手势。 Map Kit提供了多种手势供用户与地图之间进行交互，如缩放、滚动、旋转和倾斜。这些手势默认开启，如果想要关闭某些手势，可以通过MapComponentController类提供的接口来控制手势的开关。 接口说明 以下是地图的控件和手势相…
阅读更多...
安卓数据存储——SharedPreferences

安卓数据存储——SharedPreferences

共享参数 SharedPreferences 1、sharedPreferences是Android的一个轻量级存储工具&#xff0c;采用的存储结构是key - value的键值对方式 2、共享参数的存储介质是符合XML规范的配置文件。保存路径是&#xff1a;/data/data/应用包名/shared_prefs/文件名.xml 使用场景&…
阅读更多...
OpenCV特征检测(7)角点检测函数goodFeaturesToTrack()的使用

OpenCV特征检测(7)角点检测函数goodFeaturesToTrack()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 确定图像上的强角点。 该函数根据 240中所描述的方法查找图像中最显著的角点或者指定图像区域内的最显著角点。 函数使用 cornerMinEigenVal 或…
阅读更多...
线性表一（vector）

线性表一（vector）

#include<bits/stdc.h> using namespace std; vector<int> a(5,2);//定义一个初始长度为5&#xff0c;每个元素值为2的可变数组 vector<char> b(3);//定义一个初始长度为3&#xff0c;每个元素为默认值的可变数组 vector<int> v;//定义一个长度为0的可…
阅读更多...
go 读取excel数据存储到mysql

go 读取excel数据存储到mysql

一、安装依赖 go get github.com/go-sql-driver/mysql go get github.com/jmoiron/sqlx 二、main.go package mainimport ("fmt""github.com/jmoiron/sqlx""log" ) import "github.com/tealeg/xlsx" import _ "github.com/go-s…
阅读更多...
用户态缓存：链式缓冲区（Chain Buffer）

用户态缓存：链式缓冲区（Chain Buffer）

目录 链式缓冲区&#xff08;Chain Buffer&#xff09;简介 为什么选择链式缓冲区&#xff1f; 代码解析 1. 头文件与类型定义 2. 结构体定义 3. 宏定义与常量 4. 环形缓冲区的基本操作 5. 其他辅助函数 6. 数据读写操作的详细实现 7. 总结 8. 结合之前的内容 9. 具…
阅读更多...
vue2+elementUI实现handleSelectionChange批量删除-前后端

vue2+elementUI实现handleSelectionChange批量删除-前后端

功能需求&#xff1a;实现选中一个或多个执行批量删除操作 在elementUI官网选择一个表格样式模板&#xff0c;Element - The worlds most popular Vue UI framework 这里采用的是 将代码复制到前端&#xff0c;这里是index.vue <template><el-button type"dang…
阅读更多...
人工智能有助于解决 IT/OT 集成安全挑战

人工智能有助于解决 IT/OT 集成安全挑战

思科的一项研究表明&#xff0c;信息技术 (IT) 和运营技术 (OT) 融合所带来的安全问题可以通过人工智能 (AI) 解决&#xff0c;尽管该技术也可能被恶意行为者利用。 该报告由思科和 Sapio Research 联合发布&#xff0c;对 17 个国家的 1,000 名行业专业人士进行了调查&#x…
阅读更多...
如何在Java中实现用户列表的下载功能

如何在Java中实现用户列表的下载功能

在现代的Web应用中&#xff0c;用户管理是一个常见的需求。用户可能需要查看和下载他们的个人信息或者用户列表。本文将介绍如何使用Java和Spring框架实现用户列表的下载功能&#xff0c;具体采用Excel格式。 一、项目准备 首先&#xff0c;确保你的项目中已经引入了Spring B…
阅读更多...
PAT甲级-1086 Tree Traversals Again

PAT甲级-1086 Tree Traversals Again

题目 题目大意 题目给出二叉树的节点个数&#xff0c;并给出用栈遍历树的过程。要求输出树的后序遍历&#xff0c;不能有多余空格。 思路 可以看出&#xff0c;栈遍历输出的是树的中序遍历&#xff0c;而依次push进栈的是先序遍历的顺序。题目要求后序&#xff0c;即已知先序…
阅读更多...
MySQL缓冲池详解

MySQL缓冲池详解

Buffer Pool 本文参考开源项目&#xff1a;小林coding在线文档&#xff1b; 01-缓冲池概述 ​ 在MySQL查询数据的时候&#xff0c;是通过存储引擎去磁盘做IO来获取数据库中的数据&#xff0c;这样每次查询一条数据都要去做一次或者多次磁盘的IO&#xff0c;无疑是非常慢的。…
阅读更多...
mxnet系统架构

mxnet系统架构

mxnet系统架构 MXNet 是一个高性能、灵活的深度学习框架&#xff0c;最早由李沐&#xff08;Mu Li&#xff09;等人开发&#xff0c;并且得到了 Amazon 的支持。它支持多种语言&#xff08;包括 Python、Scala、C、R、Julia、Perl 等&#xff09;&#xff0c;并以其灵活的编程…
阅读更多...
EfficientNet V1 V2

EfficientNet V1 V2

v1 论文地址&#xff1a;https://arxiv.org/abs/1905.11946 网络深度、宽度和图像分辨率&#xff0c;进行了栅格搜索&#xff08;Grid Search&#xff09;&#xff0c;找到了最优的几种搭配。 v2 论文地址&#xff1a;https://arxiv.org/abs/2104.00298 Fused-MBConv 到搜…
阅读更多...
SpringBoot教程（三十） | SpringBoot集成Shiro权限框架（shiro-spring 方式）

SpringBoot教程（三十） | SpringBoot集成Shiro权限框架（shiro-spring 方式）

SpringBoot教程&#xff08;三十&#xff09; | SpringBoot集成Shiro权限框架&#xff08;shiro-spring方式&#xff09; 一、 什么是Shiro二、Shiro 组件核心组件其他组件 三、流程说明shiro的运行流程 四、SpringBoot 集成 Shiro1. 添加 Shiro 相关 maven2. 添加 其他 maven3…
阅读更多...
6种解决msvcp140_ATOMIC_WAIT.dll丢失的方法分享

6种解决msvcp140_ATOMIC_WAIT.dll丢失的方法分享

日常生活工作中&#xff0c;电脑已经成为我们生活和工作中不可或缺的工具。然而&#xff0c;在使用过程中&#xff0c;我们也会遇到各种问题&#xff0c;其中之一就是电脑中的msvcp140_ATOMIC_WAIT.dll文件丢失。这个问题可能会导致电脑运行不稳定&#xff0c;甚至无法正常启动…
阅读更多...
7-51 7-52 两个有序链表序列并集 和 交集

7-51 7-52 两个有序链表序列并集 和 交集

7-51代码&#xff1a;&#xff08;map) #include<iostream> #include<map> using namespace std; map<int,int>mp; int cnt,cnttp; void scan(){while(1){int x; scanf("%d",&x);if(x-1) break;mp[x];cnt;} } int main(){scan();scan();if(!…
阅读更多...
最新文章

Copyright @ 2022~2023