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

C++二叉搜索树

本章主要是二叉树的进阶部分,学习搜索二叉树可以更好理解后面的mapset的特性。

1.二叉搜索树概念

二叉搜索树的递归定义为:非空左子树所有元素都小于根节点的值,非空右子树所有元素都大于根节点的值,而左右子树也是二叉搜索树。

2.二叉搜索树实现

2.1.接口分析

2.1.1.查找

  1. 从根开始比较查找,比根大则往右边走查找,比根小则往左边走查找。
  2. 最多查找高度次,走到空,还没找到,则该值不存在。

2.1.2.插入

  1. 树为空,则直接新增节点,赋值给root指针
  2. 树不空,按二叉搜索树性质查找插入位置,插入新节点

2.1.3.删除

首先查找元素是否在二叉搜索树中,如果不存在,则返回false。否则要删除的结点可能分下面四种情况:

  1. 要删除的结点无孩子结点
  2. 要删除的结点只有左孩子结点
  3. 要删除的结点只有右孩子结点
  4. 要删除的结点有左、右孩子结点

看起来有待删除节点有四种情况,实际情况1可以与情况2或者3合并起来,因此真正的删除过程如下:

  1. 情况1:删除该结点且使被删除节点的双亲结点指向被删除结点的左/右孩子结点(直接删除))

  2. 情况2:在它的右子树中寻找中序下的第一个结点(关键码最小,也就是右子树中最小的结点),用它的值填补到被删除节点中,再来处理该结点的删除问题(替换法删除)

    补充:实际上情况2找左子树的最大节点也是可以的。

上述体现了一种“托孤”的现象,这和Linux中孤儿进程的托孤很是类似。

2.2.具体实现

#include <iostream>
#include <string>
using namespace std;template<typename K>//这里更加习惯写K,也就是关键值key的类型
struct BinarySearchTreeNode
{BinarySearchTreeNode<K>* _left;BinarySearchTreeNode<K>* _right;K _key; BinarySearchTreeNode(K key = K()) : _key(key), _left(nullptr), _right(nullptr) {}
};template<typename K>
class BinarySearchTree
{typedef BinarySearchTreeNode<K> Node;
public://BinarySearchTree() : _root(nullptr) {}BinarySearchTree() = default;//强制编译器生成默认的构造函数BinarySearchTree(const BinarySearchTree<K>& b){_root = copy(b._root);}BinarySearchTree<K>& operator=(BinarySearchTree<K> b)//b拷贝了一份{swap(_root, b._root);return *this;}~BinarySearchTree(){destroy(_root);}//1.插入bool insert(const K& key){/*对于第一个插入的节点就是根节点。至于数据冗余,我在这里定义不允许数据冗余,也就是不允许出现重复的数据节点。这样的搜索二叉树会受到数据先后顺序插入的影响(您也可定义允许)*///1.查看是否根节点if (_root == nullptr){_root = new Node(key);return true;}//2.寻找存放的位置Node* parent = nullptr;//存放root的父节点Node* root = _root;//遍历,从根节点开始while (root)//直到空为止{parent = root;if (root->_key < key) {root = root->_right;}else if(root->_key > key){root = root->_left;}else//root->_key == key{return false;//默认不允许重复数据}}//3.插入节点及数据root = new Node(key);if (parent->_key < key)//注意不可以直接赋值给root,不仅内存泄露还连接不上节点{parent->_right = root;}else{parent->_left = root;}return true;}bool insertR(const K& key){return _insertR(_root, key);}//2.删除bool erase(const K& key){/*寻找被删除的节点,删除后,如果是单子节点还好,如果是多子节点就需要找到一个托孤后依旧满足二叉搜索树性质的节点,因此删除有两种情况:A.被删除节点是叶子节点 或者 被删除节点的左或右孩子为空,直接将孩子节点替换被删除节点即可B.被删除节点拥有两个子节点,取右子树中最小的节点替代被删除的节点(当然也可以取左子树的最大节点)b1.最小节点没有右孩子,最小节点直接替代被删除节点,并且将最小节点的空孩子节点交给父节点领养b2.最小节点存在右孩子,最小节点直接替代被删除节点,并且将最小节点的右孩子节点交给父节点领养最后还需要注意删除根节点,根节点没有父节点的问题*/Node* parent = nullptr;Node* cur = _root;//1.寻找节点while (cur){if (cur->_key < key){parent = cur;//不可以和下一个if语句共用,会出现cur和parenat的情况,例如:test_1()中删除10的时候cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{//2.删除节点(找到了)if (cur->_left == nullptr)//2.1.左为空{if (parent == nullptr)//避免cur是根节点,没有父节点,例如:test_1()中删除11的时候{_root = cur->_right;delete cur;return true;}if (parent->_left == cur){parent->_left = cur->_right;}else//parent->_right == cur{parent->_right = cur->_right;}delete cur;}else if (cur->_right == nullptr)//2.2.右为空{if (parent == nullptr){_root = cur->_left;delete cur;return true;}if (parent->_left == cur){parent->_left = cur->_left;}else//parent->_right == cur{parent->_right = cur->_left;}delete cur;}else//2.3.左右均不为空,取左子树中最大的或者取右子树中最小的节点替代被删除的节点{Node* pminRight = cur;//注意不能为nullptr,因为有可能出现不进循环的情况Node* minRight = cur->_right;//我们选择找右数最小节点while (minRight->_left != nullptr)//找到最左节点,但是需要注意这个最左节点如果有右树,那就需要最左节点的父节点接管{pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;//替换相当于删除if (pminRight->_left == minRight)//最左节点的父节点托管最左节点的右树,注意可能有两种情况{pminRight->_left = minRight->_right;}else if (pminRight->_right == minRight)//最左节点的父节点托管最左节点的右树,注意可能有两种情况{pminRight->_right = minRight->_right;}delete minRight;}return true;}}return false;}bool eraseR(const K& key){return _eraseR(_root, key);}//3.查找bool find(const K& key){Node* root = _root;while (root){if (root->_key < key){root = root->_right;}else if (root->_key > key){root = root->_left;}else{return true;}}return false;}bool findR(const K& key){return _findR(_root, key);}//4.打印void inOrder(){_inOrder(_root);cout << endl;}private://1.销毁(提供给析构)void destroy(Node*& root){if (root == nullptr)return;destroy(root->_left);destroy(root->_right);delete root;root = nullptr;}//2.拷贝(提供给拷贝构造)Node* copy(Node* root){if (root == nullptr){return nullptr;}Node* newroot = new Node(root->_key);newroot->_left = copy(root->_left);newroot->_right = copy(root->_right);return newroot;}//3.插入(提供给递归插入)bool _insertR(Node*& root, const K& key)//注意root是引用{if (root == nullptr){root = new Node(key);//这里由于传递的是引用,那么root就是上一级递归的root->_left或者root->_rightreturn true;}if (root->_key < key){return _insertR(root->_right, key);}else if (root->_key > key){return _insertR(root->_left, key);}else{return false;}}//4.删除(提供给递归插入)bool _eraseR(Node*& root, const K& key){if (root == nullptr)return false;if (root->_key < key){return _eraseR(root->_right, key);}else if (root->_key > key){return _eraseR(root->_left, key);}else//root->_key == key{Node* del = root;//保存要删除的节点if (root->_right == nullptr){root = root->_left;}else if (root->_left == nullptr){root = root->_right;}else//左右均不为空{Node* maxleft = root->_left;while (maxleft->_right != nullptr)//找左树的最大节点{maxleft = maxleft->_right;}swap(root->_key, maxleft->_key);return _eraseR(root->_left, key);//由于左树的最大节点必有一个空孩子节点,因此使用递归删除即可,可以看到递归的删除比非递归及其的简单明了(注意不可以直接传递maxleft,这是一个局部变量)}delete del;return true;}}//5.查找(提供给递归查找)bool _findR(Node* root, const K& key){if (root == nullptr)return false;if (root->_key == key)return true;if (root->_key < key){return _isRecursionFind(root->_left, key);}else//root->_key > key{return _isRecursionFind(root->_right, key);}}//6.打印(提供给递归打印)void _inOrder(Node* root)//注意这里不能直接就拿_root当作缺省值了,因为缺省值只能是常量或者全局变量,而_root需要使用this->_root,而this指针是函数形参,不一定传过来了,别谈使用_root了{if (root == nullptr)return;_inOrder(root->_left);cout << root->_key << " ";_inOrder(root->_right);}//?.成员变量Node* _root;
};

这里我还为您提供了三个测试样例:

//普通测试
void test_1()
{BinarySearchTree<int> b;b.insert(6);b.insert(2);b.insert(1);b.insert(4);b.insert(-2);b.insert(10);b.insert(9);b.insert(11);b.inOrder();b.erase(6);b.inOrder();b.erase(2);b.inOrder();b.erase(10);b.inOrder();b.erase(1);b.inOrder();b.erase(4);b.inOrder();b.erase(9);b.inOrder();b.erase(11);b.inOrder();b.erase(-2);b.inOrder();
}
//头删测试(需要该_root为公有成员才可以测试)
void test_2()
{BinarySearchTree<int> b;b.insert(6);b.insert(2);b.insert(1);b.insert(4);b.insert(-2);b.insert(10);b.insert(9);b.insert(11);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();//b.erase(b._root->_key);//b.inOrder();
}
//递归测试
void test_3()
{BinarySearchTree<int> b;b.insertR(6);b.insertR(2);b.insertR(1);b.insertR(4);b.insertR(-2);b.insertR(10);b.insertR(9);b.insertR(11);BinarySearchTree<int> b1(b);b.inOrder();b.eraseR(6);b.inOrder();b.eraseR(2);b.inOrder();b.eraseR(10);b.inOrder();b.eraseR(1);b.inOrder();b.eraseR(4);b.inOrder();b.eraseR(9);b.inOrder();b.eraseR(11);b.inOrder();b.eraseR(-2);b.inOrder();b1.inOrder();b.inOrder();
}

3.二叉搜索树应用

3.1.Key模型

考虑“在不在”的问题,例如:

  1. 门禁系统
  2. 车库系统
  3. 单词检查、搜索…

查找对象是否在数据库中存在,这样的场景在现实中有很多。

3.2.Key/Value模型

通过一个值查找另外一个值,例如:

  1. 中英文互译
  2. 电话号码查询快递信息
  3. 验证码查询信息…

只需要在一个节点中包含一个数据对即可。

另外我们之前说过二叉搜索树一般不存储重复的元素,如果相同的元素可以让该元素绑定一个int元素形成键值对,这种情况的实际应用有:统计高频词汇。

补充:实际上,上面的这两种模型对标的是C++setmap容器,这些我们后续学习。

4.二叉搜索树分析

由于缺失平衡性,二叉搜索树在最不理想的状态(一颗斜树)查找的时间复杂度是 O ( n ) O(n) O(n),最好的效率是 O ( l o g 2 ( N ) ) O(log_{2}(N)) O(log2(N))

相关文章:

C++二叉搜索树

本章主要是二叉树的进阶部分&#xff0c;学习搜索二叉树可以更好理解后面的map和set的特性。 1.二叉搜索树概念 二叉搜索树的递归定义为&#xff1a;非空左子树所有元素都小于根节点的值&#xff0c;非空右子树所有元素都大于根节点的值&#xff0c;而左右子树也是二叉搜索树…...

elasticsearch索引按日期拆分

1.索引拆分原因 如果单个索引数据量过大会导致搜索变慢&#xff0c;而且不方便清理历史数据。 例如日志数据每天量很大&#xff0c;而且需要定期清理以往日志数据。例如原索引为sc_all_system_log&#xff0c;现按天拆分索引sc_all_system_log20220902&#xff0c;sc_all_syste…...

纯python实现大漠图色功能

大漠图色是一种自动化测试工具&#xff0c;可以用于识别屏幕上的图像并执行相应的操作。在Python中&#xff0c;可以使用第三方库pyautogui来实现大漠图色功能。具体步骤如下&#xff1a; 安装pyautogui库&#xff1a;在命令行中输入pip install pyautogui。导入pyautogui库&a…...

debounce and throtlle

debounce // 核心&#xff1a;单位时间内触发>1 则只执行最后一次。//excutioner 可以认为是执行器。执行器存在则清空&#xff0c;再赋值新的执行器。function debounce(fn, delay 500) {let excutioner null;return function () {let context this;let args arguments…...

四、数据库系统

数据库系统&#xff08;Database System&#xff09;&#xff0c;是由数据库及其管理软件组成的系统。数据库系统是为适应数据处理的需要而发展起来的一种较为理想的数据处理系统&#xff0c;也是一个为实际可运行的存储、维护和应用系统提供数据的软件系统&#xff0c;是存储介…...

Linux中的高级IO

文章目录 1.IO1.1基本介绍1.2基础io的低效性1.3如何提高IO效率1.4五种IO模型1.5非阻塞模式的设置 2.IO多路转接之Select2.1函数的基本了解2.2fd_set理解2.3完整例子代码&#xff08;会在代码中进行讲解&#xff09;2.4优缺点 3.多路转接之poll3.1poll函数的介绍3.2poll服务器3.…...

项目管理之如何估算项目工作成本

在项目管理中&#xff0c;如何估算项目工作成本是一个关键问题。为了解决这个问题&#xff0c;我们可以采用自上而下的成本限额估算法和自下而上的成本汇总估算法。这两种方法各有优缺点&#xff0c;但都可以帮助我们准确地估算项目工作成本。 自上而下的成本限额估算法 自上…...

Redis主从复制基础概念

Redis主从复制&#xff1a;提高数据可用性和性能的策略 一、概述 Redis主从复制是一种常用的高可用性策略&#xff0c;通过将数据从一个Redis服务器复制到另一个或多个Redis服务器上&#xff0c;以提高数据的可用性和读取性能。当主服务器出现故障时&#xff0c;可以快速地切…...

图数据库Neo4j概念、应用场景、安装及CQL的使用

一、图数据库概念 引用Seth Godin的说法&#xff0c;企业需要摒弃仅仅收集数据点的做法&#xff0c;开始着手建立数据之间的关联关系。数据点之间的关系甚至比单个点本身更为重要。 传统的**关系数据库管理系统(RDBMS)**并不擅长处理数据之间的关系&#xff0c;那些表状数据模…...

路由器基础(四): RIP原理与配置

路由信息协议 (Routing Information Protocol,RIP) 是最早使用的距离矢量路由协议。因为路由是以矢量(距离、方向)的方式被通告出去的&#xff0c;这里的距离是根据度量来决定的&#xff0c;所以叫“距离矢量”。 距离矢量路由算法是动态路由算法。它的工作流程是&#xff1a;…...

红外遥控开发RK3568-PWM-IR

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言1.红外遥控的发送接收工作原理2.红外协议3.红外遥控系统框图4.遥控器添加方法4.1 记录键值4.2 添加键值总结前言 提示:这里可以添加本文要记录的大概内容: 1.红外遥控的发送接收工作原理 …...

go-sync-mutex

Sync ​ Go 语言作为一个原生支持用户态进程&#xff08;Goroutine&#xff09;的语言&#xff0c;当提到并发编程、多线程编程时&#xff0c;往往都离不开锁这一概念。锁是一种并发编程中的同步原语&#xff08;Synchronization Primitives&#xff09;&#xff0c;它能保证多…...

高并发系统设计

高并发系统通用设计方法 Scala-out 横向扩展&#xff0c;分散流量&#xff0c;分布式集群部署 缺点&#xff1a;引入复杂度&#xff0c;节点之间状态维护&#xff0c;节点扩展&#xff08;上下线&#xff09; Scala-up 提升单机性能&#xff0c;比如增加内存&#xff0c;增…...

Vue3-Pinia快速入门

1.安装pinia npm install pinia -save 2.在main.js中导入并使用pinia // 导入piniaimport { createPinia } from "pinia"; const pinia createPinia();//使用pinia app.use(pinia)app.mount(#app) 3.在src目录下创建包&#xff1a;store&#xff0c;表示仓库 4…...

Python算法——插入排序

插入排序&#xff08;Insertion Sort&#xff09;是一种简单但有效的排序算法&#xff0c;它的基本思想是将数组分成已排序和未排序两部分&#xff0c;然后逐一将未排序部分的元素插入到已排序部分的正确位置。插入排序通常比冒泡排序和选择排序更高效&#xff0c;特别适用于对…...

Java21新特性

目录 一、Java21新特性 1、字符串模版 2、scoped values 3、record pattern 4、switch格式匹配 5、可以在switch中使用when 6、Unnamed Classes and Instance Main Methods 7、Structured Concurrency 一、Java21新特性 1、字符串模版 字符串模版可以让开发者更简洁的…...

4 Tensorflow图像识别模型——数据预处理

上一篇&#xff1a;3 tensorflow构建模型详解-CSDN博客 本篇开始介绍识别猫狗图片的模型&#xff0c;内容较多&#xff0c;会分为多个章节介绍。模型构建还是和之前一样的流程&#xff1a; 数据集准备数据预处理创建模型设置损失函数和优化器训练模型 本篇先介绍数据集准备&am…...

SpringBoot整合RabbitMQ学习笔记

SpringBoot整合RabbitMQ学习笔记 以下三种类型的消息&#xff0c;生产者和消费者需各自启动一个服务&#xff0c;模拟生产者服务发送消息&#xff0c;消费者服务监听消息&#xff0c;分布式开发。 一 Fanout类型信息 . RabbitMQ创建交换机和队列 在RabbitMQ控制台&#xff0c;新…...

在校园跑腿系统小程序中,如何设计高效的实时通知与消息推送系统?

1. 选择合适的消息推送服务 在校园跑腿系统小程序中&#xff0c;选择一个适合的消息推送服务。例如&#xff0c;使用WebSocket技术、Firebase Cloud Messaging (FCM)、或第三方推送服务如Pusher或OneSignal等。注册并获取相关的API密钥或访问令牌。 2. 集成服务到小程序后端…...

求极限Lim x->0 (x-sinx)*e-²x / (1-x)⅓

题目如下&#xff1a; 解题思路: 这题运用了无穷小替换、洛必达法则、求导法则 具体解题思路如下: 1、首先带入x趋近于0&#xff0c;可以得到&#xff08;0*1&#xff09;/0&#xff0c;所以可以把e的-x的平方沈略掉 然后根据无穷小替换&#xff0c;利用t趋近于0时&#xf…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...