当前位置: 首页 > news >正文

C++从零开始的打怪升级之路(day44)

这是关于一个普通双非本科大一学生的C++的学习记录贴

在此前,我学了一点点C语言还有简单的数据结构,如果有小伙伴想和我一起学习的,可以私信我交流分享学习资料

那么开启正题

今天分享的是关于二叉搜索树的知识点

1.二叉搜索树概念

二叉搜索树又叫做二叉排序树,有以下性质(或为空树)

1.左子树结点所有结点的值都小于根节点的值

2.右子树结点所有结点的值都大于根节点的值

3.它的左右子树也都是二叉搜索树

2.二叉搜索树操作

1.查找

a.从根开始比较,查找,如果比跟大往右走,比跟小则往左走

b.最多查找高度次,走到为空还没找到,则这个值不存在

2.插入

a.树为空,直接新增结点,赋值给给_root

b.树不为空,类似查找根据性质找到插入位置,插入新结点

3.删除

首先查找元素是否在二叉搜索树中,如果不存在返回false,存在分为以下几种情况

a.要删除的结点没有左结点

b.要删除的结点没有右结点

c.要删除的结点有左右孩子结点

d.要删除的结点无孩子结点

其中d可以按照a或者b办法解决

情况a:删除该结点且使删除结点的父亲结点指向删除结点的孩子结点——直接删除

情况b:类似于a

情况c:在右子树中找到最小结点(或者在左子树中找到最大节点),用他的值填补到被删除的结点上,再删除此结点——替换法删除

3.二叉搜索树模拟实现

下面给出了模拟实现代码以及测试代码

namespace wkl
{template<class K>struct BSTreeNode{BSTreeNode* _left;BSTreeNode* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>class BSTree{typedef BSTreeNode<K> Node;public:bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}//找到空位,开始插入cur = new Node(key);if (key > parent->_key)parent->_right = cur;elseparent->_left = cur;return true;}void _InOrder(Node* root){if (!root)return;_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}bool Find(const K& key){Node* cur = _root;while (cur){if (key > cur->_key)cur = cur->_right;else if (key < cur->_key)cur = cur->_left;elsereturn true;}return false;}bool Erase(const K& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{//开始删除//1.左为空//2.右为空//3.左右均不为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur->_left;elseparent->_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;//改为删除rightMinif (rightMinParent->_left == rightMin)rightMinParent->_left = rightMin->_right;elserightMinParent->_right = rightMin->_right;delete rightMin;}return true;}}return false;}private:Node* _root = nullptr;};void BSTree_Test1(){BSTree<int> BST;int a[] = { 5,3,4,1,7,8,2,6,0,9 };for (auto e : a){BST.Insert(e);}BST.InOrder();int i = 0;for (i = 0; i < 20; i += 2){cout << i << "::";if (BST.Find(i))cout << "Yes";elsecout << "No";cout << endl;}}void BSTree_Test2(){BSTree<int> BST;int a[] = { 5,3,4,1,7,8,2,6,0,9 };for (auto e : a){BST.Insert(e);}BST.InOrder();/*BST.Erase(7);BST.InOrder();*/for (auto e : a){BST.Erase(e);BST.InOrder();}}
}

4.二叉搜索树的应用

1.K值模型

K值模型只有key作为关键码,结构中只存储key,关键码即为需要搜索到的值

2.KV模型

每一个关键码都有与之对应的多个Value,即<Key,Value>的键值对

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

插入和删除都必须先查找,查找效率代表了二叉搜索树的各个操作的性能

最好情况下:二叉树平衡,查找时间复杂度为O(lgN)

最坏情况下:二叉树插入数据接近有序,树长而不平衡,查找时间复杂度为O(N)

新手写博客,有不对的位置希望大佬们能够指出,也谢谢大家能看到这里,让我们一起学习进步吧!

相关文章:

C++从零开始的打怪升级之路(day44)

这是关于一个普通双非本科大一学生的C的学习记录贴 在此前&#xff0c;我学了一点点C语言还有简单的数据结构&#xff0c;如果有小伙伴想和我一起学习的&#xff0c;可以私信我交流分享学习资料 那么开启正题 今天分享的是关于二叉搜索树的知识点 1.二叉搜索树概念 二叉搜…...

[C++核心编程](七):类和对象——运算符重载*

目录 四则运算符重载 左移运算符重载 递增运算符重载 赋值运算符重载 关系运算符重载 函数调用运算符重载 对已有的运算符重新进行定义&#xff0c;赋予其另一种功能&#xff0c;以适应不同的数据类型 四则运算符重载 对自定义数据类型实现四则运算&#xff08;加减乘除&…...

什么是MVC和MVVM

**MVC和MVVM是两种流行的软件架构模式&#xff0c;它们在前端开发中被广泛采用来组织代码和管理应用程序的复杂性**。具体如下&#xff1a; MVC&#xff08;Model-View-Controller&#xff09;&#xff1a; 1. 模型&#xff08;Model&#xff09;&#xff1a;负责管理数据和业…...

物体检测-系列教程23:YOLOV5 源码解析13 (SPP层、Flatten模块、Concat模块、Classify模块)

&#x1f60e;&#x1f60e;&#x1f60e;物体检测-系列教程 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在Pycharm中进行 本篇文章配套的代码资源已经上传 点我下载源码 17、SPP模块 17.1 SPP类 SPP是一种特殊的池化策略&#xff0c;最初在YOLOv3-SPP中被使用…...

2024.3.6每日一题

LeetCode 找出数组中的 K -or 值 题目链接&#xff1a;2917. 找出数组中的 K-or 值 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 nums 中的 K-or 是一个满足以下条件的非负整数&#xff1a; 只有在 nums 中&…...

YOLOSHOW - YOLOv5 / YOLOv7 / YOLOv8 / YOLOv9 基于 Pyside6 的图形化界面

YOLOSHOW 是一个基于 PySide6&#xff08;Qt for Python&#xff09;开发的图形化界面应用程序&#xff0c;主要用于集成和可视化YOLO系列&#xff08;包括但不限于YOLOv5、YOLOv7、YOLOv8、YOLOv9&#xff09;的目标检测模型。YOLOSHOW 提供了一个用户友好的交互界面&#xff…...

sql高级

sql高级 SQL SELECT TOP 子句 SELECT TOP 子句用于规定要返回的记录的数目。 SELECT TOP 子句对于拥有数千条记录的大型表来说&#xff0c;是非常有用的。 **注意:**并非所有的数据库系统都支持 SELECT TOP 语句。 MySQL 支持 LIMIT 语句来选取指定的条数数据&#xff0c; O…...

更快更强,Claude 3全面超越GPT4,能归纳15万单词

ChatGPT4和Gemini Ultra被Claude 3 AI模型超越了&#xff1f; 3月4日周一&#xff0c;人工智能公司Anthropic推出了Claude 3系列AI模型和新型聊天机器人&#xff0c;其中包括Opus、Sonnet和Haiku三种模型&#xff0c;该公司声称&#xff0c;这是迄今为止它们开发的最快速、最强…...

devc++小游戏3.8.5

导航&#xff1a; Dev-c跑酷小游戏 1.0.0 devc跑酷小游戏1.2.5 devc跑酷游戏1.2.6 devc跑酷游戏2.0.0 devc跑酷游戏2.0.1 devc跑酷游戏2.4.0 devc跑酷小游戏3.5.0 更新内容 重磅回归&#xff0c;存档搞定&#xff01;&#xff01;&#xff01; 每一关需要前一关已…...

Java网络通信TCP

目录 TCP两个核心类 服务端 1.用ServerSocker类创建对象并且手动指定端口号 2.accept阻塞连接服务端与客户端 3.给客户端提供处理业务方法 4.处理业务 整体代码 客户端 1.创建Socket对象&#xff0c;并连接服务端的ip与端口号 2.获取Socket流对象&#xff0c;写入数据…...

层级锁笔记

注意看test_hierarchy_lock函数&#xff1a;如果thread t2的不注释&#xff0c;就会报错。 这是因为层级锁 更强调单个线程内上锁的顺序。 线程t2已经获取了hmtx2&#xff0c;再试图获取hmtx1就会因为违反层级顺序而抛出异常。 #include <mutex> #include <thread&g…...

基于SpringBoot+Vue 的专家医院预约挂号系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

计算机基础专升本笔记十二-Excel常用快捷键大全

计算机基础专升本笔记十二-Excel常用快捷键大全 Excel常用快捷键 按键作用Ctrl 0隐藏列Ctrl 1设置单元格格式Ctrl 2添加或取消字体加粗Ctrl 3添加或取消字体倾斜Ctrl 4添加或取消下划线Ctrl 5添加或取消删除线Ctrl 6隐藏或显示图形Ctrl 7隐藏工具栏Ctrl 8隐藏或显示…...

制作耳机壳的UV树脂和塑料材质相比优势有哪些?

制作耳机壳的UV树脂相比塑料材质有以下优势&#xff1a; 高强度与耐磨性&#xff1a;UV树脂具有高强度和耐磨性&#xff0c;能够更好地保护耳机内部零件&#xff0c;延长耳机使用寿命。相比之下&#xff0c;塑料材质可能较易磨损或刮伤。耐高温&#xff1a;UV树脂具有较好的耐…...

JS(JavaScript)中如何实现,复选框checkbox多选功能

起始界面&#xff1a; 代码元素&#xff1a; <p><input type"checkbox" id"checkedAll"> 全选按钮</p><p><input type"checkbox" class"cl"> 选项1</p><p><input type"checkbox&qu…...

直接修改zynq petalinux编译出来的rootfs.cpio.gz文件内容

xilinx zynq petalinux 默认编译打包出的SPI flash烧写启动文件是BOOT.BIN&#xff0c;然而每次需要修改rootfs内的文件时都要重新build rootfs 然后再 package一次才能生成新的BOOT.bin文件&#xff0c;地球人都知道petalinux编译一次是很耗时间的&#xff0c;那么有没有什么简…...

什么是 Golang 类型断言

类型断言&#xff1a;用于检查某个接口是否包含某个具体类型&#xff0c;语法x.(T)&#xff0c;x是一个接口类型表达式&#xff0c;T是具体的类型&#xff0c;如果x包含的值可以被转换成T类型&#xff0c;则是ok 在Go语言中&#xff0c;任何类型的值都属于空接口类型。空接口类…...

mysql数据库root权限读写文件

如果没有shell&#xff0c;只有数据库权限的情况下&#xff1a; 1. udf 提权提示没有目录&#xff1a;使用数据流创建目录 1. select xxx into outfile C:\\phpstudy_pro\\Extensions\\MySQL5.5.29\\lib\::$INDEX_ALLOCATION;2. select xxx into outfile C:\\phpstudy_pro\…...

力扣爆刷第88天之hot100五连刷26-30

力扣爆刷第88天之hot100五连刷26-30 文章目录 力扣爆刷第88天之hot100五连刷26-30一、142. 环形链表 II二、21. 合并两个有序链表三、2. 两数相加四、19. 删除链表的倒数第 N 个结点五、24. 两两交换链表中的节点 一、142. 环形链表 II 题目链接&#xff1a;https://leetcode.…...

Ethersacn的交易数据是什么样的(2)

分析 Raw Transanction RLP&#xff08;Recursive Length Prefix&#xff09;是一种以太坊中用于序列化数据的编码方式。它被用于将各种数据结构转换为二进制格式&#xff0c;以便在以太坊中传输和存储。RLP 是一种递归的编码方式&#xff0c;允许对复杂的数据结构进行编码。所…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...