Cpp二叉搜索树的讲解与实现(21)

文章目录

  • 前言
  • 一、二叉搜索树的概念
    • 定义
    • 特点
  • 二、二叉树的实现
    • 基本框架
    • 查找
    • 插入
    • 删除
      • 当只有0 ~ 1个孩子的时候
      • 当有2个孩子的时候
  • 三、二叉树的应用
    • K模型
    • KV模型
  • 四、二叉树的性能分析
  • 总结


前言

这是全新的一个篇章呢,二叉搜索树是我们接下来学习set、map的前提
迈过它吧,关关难过关关过!

正文开始!


一、二叉搜索树的概念

定义

  二叉搜索树(Binary search tree)是基于二叉树的一种改进版本。因为 普通二叉树没有实际价值,无法进行插入、删除等操作(无意义),但二叉搜索树就不一样了,二叉搜索树对于数据的存储有严格要求:左节点比根小,右节点比根大

因此 二叉搜索树 的查找效率极高,具有一定的实际价值

  所以将数据存入 二叉搜索树 中进行查找时,理想情况下只需要花费 logN 的时间(二分思想)

  这就是 二叉搜索树 名字的由来,搜索(查找)速度很快

特点

  二叉树的基本特点:左比根小,右比根大

  1. 若某个节点的 左 节点不为空,则 左 节点的值一定比当前节点的值 小,且其 左 子树的所有节点都比它 小
  2. 若某个节点的 右 节点不为空,则 右 节点的值一定比当前节点的值 大,且其 右 子树的所有节点都比它 大
  3. 二叉搜索树的每一个节点的 根、左 、右 都满足基本特点

另外,中序遍历的结果为升序

二、二叉树的实现

二叉搜索树的源代码

基本框架

  跟普通的二叉树一样,二叉搜索树也需要节点类,同时将节点指针作为二叉搜索树的成员变量

template <class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key = K()):_key(key),_left(nullptr),_right(nullptr){}};template <class K>
class BSTree
{typedef BSTNode<K> Node;
public:BSTree():_root(nullptr){}private:Node* _root;
};

查找

  得益于二叉搜索树的特性,我们可以比较插入数字和当前节点的值,当比当前节点大的时候的时候往右走,反之则往左,若 cur 为空,那么返回 false ,若找到,则返回 true
在这里插入图片描述

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;else return true;}return false;
}

插入

  插入其实过程和查找差不多,只不过如果中途找到了就返回 false 表示二叉搜索树中已经有该数字,如果成功走到空了就开始插入
在这里插入图片描述

  只不过我们需要注意,当搜索树为空树的时候,我们必须新建立一个节点,将指针赋给这个根节点,另外,我们需要申请一个指针变量 parent 来记录父节点,方便后续链接

bool Insert(const K& key)
{// 如果为空树,则直接建立一个节点// 将其地址存放在_root上if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;// 一直循环到cur为空while (cur) {if (key > cur->_key) {parent = cur;cur = cur->_right;}else if (key < cur->_key) {parent = cur;cur = cur->_left;}else {// 如果中途发现BS树已有key,则插入失败// BS树中没有重复元素,依据定义return false;}}// 此时建立一个节点,将其地址赋值给curcur = new Node(key);// 此时需要根据值的大小来判断parent左链还是右链if (key > parent->_key)parent->_right = cur;else parent->_left = cur;return true;
}

删除

  删除可就复杂了,要考虑很多情况!

  我们发现如果我们要删除一个节点,并且在二叉搜索树中已经确定找到了该节点,可能有三种情况:

  1. 该节点没有孩子,即要删除的是叶子节点
  2. 该节点只有一个孩子,可能是左孩子为空,也有可能是有孩子为空
  3. 该节点有两个孩子,这种情况比较复杂,要考虑比较复杂的情况

当只有0 ~ 1个孩子的时候

  我们先来看第二种情况,当找到要删除的节点且该节点只有一个孩子后,此时显然父节点链上当前节点的子节点就可以了,这样不会破坏二叉搜索树的结构

二叉搜索树的右子树的值一定大于该节点的值,同样的,左子树的值一定小于该节点的值

  于是,我们就想着再销毁当前节点之前,先判断是父节点的左边链接还是右边链接,这很简单,我们检查一下 parent 左右指针哪个指向 cur 就行,同时,我们也要思考一下子节点与 cur 的链接关系,很简单,这也是直接判断一下就可以

其实,这种方法囊括了第一第二种情况,你可以思考一下为什么

// 如果左孩子为空
// 这时候就要parent就要链到cur的右边去
if (cur->_left == nullptr) {if (parent->_left == cur)parent->_left = cur->_right;else parent->_right = cur->_right;// 删除delete cur;cur = nullptr;return true;
}// 如果右孩子为空
// 这时候就要parent就要链到cur的左边去
else if (cur->_right == nullptr) {if (parent->_left == cur)parent->_left = cur->_left;else parent->_right = cur->_left;// 删除delete cur;cur = nullptr;return true;
}

右子树为空
在这里插入图片描述

左子树为空
在这里插入图片描述

当有2个孩子的时候

在这里插入图片描述

  当左右孩子节点都不为空的时候,我们也要想想,万一把 cur 给删掉了,要换那一个替上来?

  关于这个问题,我们还是要把握二叉搜索树的一个核心特性,就是左子树所有节点的值一定比根节点小,右子树所有节点的值一定比根节点大

  那么只要将左子树最大的值和右子树最小的值找到,此时我们又要想,将两个其中之一的值替代父节点的值即可,然后再销毁节点,那么这样会不会破坏二叉树的结构呢?

  显然不会,只要能正确销毁并正确链接,那么就没关系,在这里我们选择找到右子树的最小值,这很简单,因为一个二叉搜索树的最小值就是最左边那个,那么我们同样用 rightMin 标记右子树的最小节点 ,用 rightMinP 标记其父节点,又为了防止 rightMinP 进不去循环,我们给 rightMinP 赋值 cur


Node* rightMinP = cur;
Node* rightMin = cur->_right;// 找到右子树的最小节点
while (rightMin->_left) {rightMinP = rightMin;rightMin = rightMin->_left;
}// 替代,这时候转换成就要删除rightMin这个节点了
// 这个时候就需要有它的父亲
cur->_key = rightMin->_key;// 因为rightMin必然是最左节点
// 所以rightMinP必然是链接rightMin的右孩子
// 同时rightMinP是左链还是右链这不确定,需要判断一下
if (rightMinP->_left == rightMin)rightMinP->_left = rightMin->_right;
else rightMinP->_right = rightMin->_right;delete rightMin;
rightMin = nullptr;return true;

  但是但是!!我们发现写到这里后,当删到最后只剩几个节点之后,报错了!

  我们再回看代码,发现我们的逻辑是先找到删除节点,再用父亲节点去链接当前节点的子节点,关键是,有没有可能一开始我们就找到了要删除的节点,父亲节点没进循环,也就是说,没有父亲节点,这很不好,针对这种情况,我们就要移动根节点

if (parent == nullptr) {_root = _root->_right;delete cur;cur = nullptr;return true;
}

三、二叉树的应用

K模型

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

我们上述代码实现的也就是这种

  举个例子,给一个单词word,判断该单词是否拼写正确,具体方式如下:

  1. 以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树
  2. 在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误

KV模型

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

  比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英文单词与其对应的中文<word, chinese>就构成一种键值对

  再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出现次数就是<word, count>就构成一种键值对

KV模型也就是在K模型的基础上加上value的值,请试试吧!

四、二叉树的性能分析

  如果我问你二叉搜索树的查找时间复杂度为多少,你可能会不假思索的回答出是O(logN),但是,假如我给一个递减数列呢,是不是就退化成单支树了?

  所以理想状态下是O(logN),最坏情况下是O(N)


总结

  看了性能分析,你可能会想怎么让二叉树的性能达到最优?不急,AVL树和红黑树已经在路上了!~

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

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

相关文章

Elasticsearch —— ES 环境搭建、概念、基本操作、文档操作、SpringBoot继承ES

文章中会用到的文件&#xff0c;如果官网下不了可以在这下 链接: https://pan.baidu.com/s/1SeRdqLo0E0CmaVJdoZs_nQ?pwdxr76 提取码: xr76 一、 ES 环境搭建 注&#xff1a;环境搭建过程中的命令窗口不能关闭&#xff0c;关闭了服务就会关闭&#xff08;除了修改设置后重启的…

第八届御网杯线下赛Pwn方向题解

由于最近比赛有点多&#xff0c;而且赶上招新&#xff0c;导致原本应该及时总结的比赛搁置了&#xff0c;总结来说还是得多练&#xff0c;因为时间很短像这种线下赛&#xff0c;一般只有几个小时&#xff0c;所以思路一定要清晰&#xff0c;我还是经验太少了&#xff0c;导致比…

Ethernet 系列(6)-- 基础学习::OSI Model

&#xff08;写在前面&#xff1a;最近在学习车载以太网的知识&#xff0c;顺便记录一下知识点。&#xff09; OSI&#xff08;Open System Interconnect &#xff09;模型是一种网络通信框架&#xff0c;由国际标准化组织&#xff08;‌ISO&#xff09;在1985年提出&#xff0…

Java 字符流详解

在 Java 的 I/O 体系中&#xff0c;字符流&#xff08;Reader 和 Writer&#xff09;是专门用于处理文本数据的输入输出流。与字节流不同&#xff0c;字符流以字符为单位进行读取和写入&#xff0c;能够更好地处理文本信息&#xff0c;尤其是包含多字节字符&#xff08;如中文&…

Linux 多线程编程

韦东山的例程所谓线程&#xff0c;就是操作系统所能调度的最小单位。普通的进程&#xff0c;只有一个线程在执行对应的逻辑。我们可以通过多线程编程&#xff0c;使一个进程可以去执行多个不同的任务。相比多进程编程而言&#xff0c;线程享有共享资源&#xff0c;即在进程中出…

后端:Spring-1

文章目录 1. 了解 spring(Spring Framework)2. 基于maven搭建Spring框架2.1 纯xml配置方式来实现Spring2.2 注解方式来实现Spring3. Java Config类来实现Spring 2.4 总结 1. 了解 spring(Spring Framework) 传统方式构建spring(指的是Spring Framework)项目&#xff0c;导入依…

【C++动态规划 01背包】2787. 将一个数字表示成幂的和的方案数

本文涉及知识点 C动态规划 C背包问题 LeetCode2787. 将一个数字表示成幂的和的方案数 给你两个 正 整数 n 和 x 。 请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说&#xff0c;你需要返回互不相同整数 [n1, n2, …, nk] 的集合数目&#xff0c;满…

Python爬虫的京东大冒险:如何高效获取商品详情的秘籍

在这个由代码编织的电商世界里&#xff0c;京东商品详情就像是被锁在高塔中的公主&#xff0c;等待着勇敢的Python爬虫骑士去解救。今天&#xff0c;我们要讲述的是如何成为一名Python爬虫骑士&#xff0c;携带你的代码长矛&#xff0c;穿梭在API的数据森林中&#xff0c;高效获…

SpringBoot【实用篇】- 测试

文章目录 目标&#xff1a;1.加载测试专用属性3.Web环境模拟测试2.加载测试专用配置4.数据层测试回滚5.测试用例数据设定 目标&#xff1a; 加载测试专用属性加载测试专用配置Web环境模拟测试数据层测试回滚测试用例数据设定 1.加载测试专用属性 我们在前面讲配置高级的时候…

vfx特效有多烧钱?云渲染农场减少vfx特效成本

特效制作一直是电影制作中的烧钱大户&#xff0c;尤其是视觉特效&#xff08;VFX&#xff09;的高昂成本让许多项目望而却步。但随着云渲染农场技术的发展&#xff0c;VFX特效的成本得到了有效控制&#xff0c;为电影工业带来了革命性的变化。 在电影工业中&#xff0c;VFX特效…

任何python安装gdal出现的问题

Releases cgohlke/geospatial-wheels GitHubGeospatial library wheels for Python on Windows. Contribute to cgohlke/geospatial-wheels development by creating an account on GitHub.https://github.com/cgohlke/geospatial-wheels/releases 各种乱七八糟的gdal库问题…

tensorflow案例4--人脸识别(损失函数选取,调用VGG16模型以及改进写法)

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 前言 这个模型结构算上之前的pytorch版本的&#xff0c;算是花了不少时间&#xff0c;但是效果一直没有达到理想情况&#xff0c;主要是验证集和训练集准确率…

SPA和SSR

单页面应用程序(SPA) 单页面应用(SPA)全称是:Single-page application, SPA应用是在客户端呈现的(术语称:CRS)。 SPA应用默认只返回一个空HTML页面&#xff0c;如:body只有<div id"app"></div>而整个应用程序的内容都是通过JavaScript动态加载&#xf…

【 纷享销客-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…

基于SpringBoot和PostGIS的世界各国邻国可视化实践

目录 前言 一、空间数据查询基础 1、空间数据库基础 2、空间相邻查询 二、SpringBoot后台功能设计 1、后台查询接口的实现 2、业务接口设计 三、Leaflet进行WebGIS开发 1、整体结构介绍 2、相邻国家展示可视化 四、成果展示 1、印度及其邻国 2、乌克兰及其邻国 3、…

Python之groupby()及aggregate()方法

目录 数据准备df.describe()思考1 分组 pd.groupby()思考2 df.aggregate()思考1 现在有一份titanic_train.csv&#xff0c;包含泰坦尼克号乘客信息及获救情况的明细数据&#xff0c;我们需要使用一些聚合函数&#xff0c;统计相关指标。 数据准备 import pandas as pd df pd.…

Unity 二次元三渲二

三渲二 注意&#xff1a;Unity必须是2022.3LTS及以上和URP项目&#xff01;&#xff01;&#xff01; 下载三渲二插件 【如何将原神的角色导入Unity】全网最细致教程&#xff0c;全程干货。不使用任何收费插件&#xff0c;使用Spring Bone对头发和衣服进行物理模拟。_原神 步…

Unity计算二维向量夹角余弦值和正弦值的优化方法参考

如果不考虑优化问题&#xff0c;计算两个向量的余弦值或者正弦值可以直接使用类似的方法&#xff1a; [SerializeField] Vector2 v1, v2;void Start() {float valCos Mathf.Acos(Vector2.SignedAngle(v1, v2));float valSin Mathf.Asin(Vector2.SignedAngle(v1, v2)); } 但是…

深度|谁在为OpenAI和Anthropic的AI编程竞赛提供“军火”?已赚得盆满钵满

图片来源&#xff1a;Unsplash AI 开发者之所以一致认为编程的重要性&#xff0c;是有原因的&#xff1a;大型语言模型编程能力越强&#xff0c;它回答与软件无关的其他类型问题的能力也越强。 去年秋天&#xff0c;几位 Google 人工智能领导者与初创公司 CEO Jonathan Siddh…

2024年北京市安全员-A证证模拟考试题库及北京市安全员-A证理论考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年北京市安全员-A证证模拟考试题库及北京市安全员-A证理论考试试题是由安全生产模拟考试一点通提供&#xff0c;北京市安全员-A证证模拟考试题库是根据北京市安全员-A证最新版教材&#xff0c;北京市安全员-A证大…