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

C++——二叉树排序树

文章目录

    • 1 二叉搜索树概念
    • 2 二叉搜索树操作与模拟实现
      • 2.1 二叉搜索树的查找
      • 非递归版本
      • 递归版本
      • 2.2 二叉搜索树的插入
      • 非递归版本
      • 递归版本
      • 2.3 二叉搜索树的删除
      • 非递归版本
      • 递归版本
    • 3 二叉搜索树的应用(K模型、KV模型)
    • 4 二叉搜索树的性能分析

1 二叉搜索树概念

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:

  • 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树
  • 一般情况下二叉搜索树的数据是不能重复的
    在这里插入图片描述

2 二叉搜索树操作与模拟实现

完整代码K模型和KV模型代码链接
结点定义:

template<class K>
struct BSTreeNode
{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
};typedef BSTreeNode<K> Node;

2.1 二叉搜索树的查找

在这里插入图片描述

a、从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。
b、最多查找高度次,走到到空,还没找到,这个值不存在。

代码实现:

非递归版本

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;
}

递归版本

bool _FindR(Node* root, const K& key)
{if (root == nullptr)//没找到return false;if (root->_key < key)//被查找到的值大于当前结点,去右树找return _FindR(root->_right, key);else if (root->_key > key)//被查找到的值小于当前结点,去左树找return _FindR(root->_left, key);else//找到了return true;
}

2.2 二叉搜索树的插入

插入的具体过程如下:
a. 树为空,则直接新增节点,给root指针赋值
b. 树不空,按二叉搜索树性质查找插入位置,插入新节点
在这里插入图片描述

代码实现:

非递归版本

bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;//记录父节点Node* cur = _root;//_root成员变量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此时为nullptr//父节点parent也被记录cur = new Node(key);if (parent->_key < key)//寻找该正确的插入位置{parent->_right = cur;}else{parent->_left = cur;}return true;
}

递归版本

可以考虑再增加一个parent参数。
但下面的方法更加巧妙
下面代码传root的引用两个用处:
1、如果传进来的就是一颗空树,直接给root赋值就可以了,比较容易理解.
2、因为传的是引用,所以root也是上一步递归传入的root->right或者root->_left的别名,非常巧妙的是root = new Node(key);就等价于root->right=new Node(key);或者root->_left=new Node(key);,刚好把结点就赋值到正确的位置,省去了上面非递归方法的还需要记录父节点的步骤。

bool _InsertR(Node*& root, const K& key)//注意细节传的是root的引用
{	if (root == nullptr){root = new Node(key);return true;}if (root->_key < key)//插入的值比当前的结点的值大,就往右树走。return _InsertR(root->_right, key);else if (root->_key > key)//插入的值比当前的结点的值小,就往左树走。return _InsertR(root->_left, key);else//插入的值和当前结点的值相等,不需要插入,返回falsereturn false;
}

下面是插入9的代码调试,可以发现确实root和上一步root->left的地址是一样的,可见引用在C++中的作用是多么大。

在这里插入图片描述

2.3 二叉搜索树的删除

首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情况:
a. 要删除的结点无孩子结点(例如1、4、7、13)
b. 要删除的结点只有左孩子结点(例如14)
c. 要删除的结点只有右孩子结点(例如10)
d. 要删除的结点有左、右孩子结点(例如3、6、8)
看起来删除节点有4种情况,实际情况a可以与情况b或者c合并起来,因此真正的删除过程如下:

  • 情况b:删除该结点,并且使该删除节点的双亲结点指向该删除节点的左孩子结点——直接删除(托孤)
  • 情况c:删除该结点,并且使该删除节点的双亲结点指向该删除结点的右孩子结点——直接删除(托孤)
  • 情况d:
    找被删除结点 左子树的最大 或者 右子树的最小 用它的值填补到被删除节点中(这样才能保证二叉排序树的结构不被破坏),再来删除这个 左子树最大 或者 右子树最小结点——替换法删除。

针对情况d,下面图中,想删除8用左子树的最大或者右子树的最小
那么由于二叉排序树特殊的结构其实
左子树的最大 也就是 左子树的最右结点——从上往下遍历,第一个没有右孩子的结点——7
右子树的最小 也就是 右子树的最左结点——从上往下遍历,第一个没有左孩子的结点——10

在这里插入图片描述

代码实现:
提前声明:下面非递归和递归版本都用的是右子树的最小结点来进行替换删除的。
具体细节详解在下面代码注释中:一边看图一边看代码注释效果更佳!

非递归版本

bool Erase(const K& key)
{Node* parent = nullptr;//记录父节点Node* cur = _root;//_root成员变量while (cur){//能找到开始删除if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else//被删除目标已经找到,就存在cur里{if (cur->_left == nullptr)//被删除结点的左为空——只有右孩子{//if (parent == nullptr)//如果被删除的就是根节点if (cur == _root)//如果被删除的就是根节点{_root = cur->_right;}else{if (parent->_left == cur)//如果我是父亲结点的左孩子{parent->_left = cur->_right;}else//如果我是父亲结点的右孩子{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr)//被删除结点右为空——只有左孩子{//if (parent == nullptr)//如果被删除的就是根节点if (cur == _root)//如果被删除的就是根节点{_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else//被删除的结点左右子树都不为空,替换删除{// 开始找右子树的最小节点Node* parent = cur; //细节赋值curNode* minRight = cur->_right;while (minRight->_left){parent = minRight;minRight = minRight->_left;}//运行到这里已经找到了右子树最小结点cur->_key = minRight->_key;//直接覆盖被删除结点的值,或者让右子树和被删除结点交换都可以//minRight是右子树的最左结点——一定没有左孩子//而且要特别注意:删除3和删除8结点是不一样的,一定要考虑全面if (minRight == parent->_left)//删除8结点的情况,对于10结点的处理{parent->_left = minRight->_right;}else//删除3结点的情况,对于4结点的处理{parent->_right = minRight->_right;}delete minRight;}return true;}}//找不到需要被删除的节点返回falsereturn false;
}

递归版本

bool _EraseR(Node*& root, const K& key)
{if (root == nullptr)//没有找到 或者 root一开始传入的就是一个空树{return false;}//开始找要被删除的结点并将其删除if (root->_key < key)//要被删除的值比当前的值大就再去右树找{return _EraseR(root->_right, key);}else if (root->_key > key)//要被删除的值比当前的值小就再去左树找{return _EraseR(root->_left, key);}else//找到了!!!开始删除{Node* del = root;//记录当前结点,方便后面delete//被删除结点只有左孩子,例如14if (root->_right == nullptr){root = root->_left;//被赋值的root也是上一层递归root->_right的别名}//被删除结点只有右孩子,例如:10else if (root->_left == nullptr){root = root->_right;//被赋值的root也是上一层递归root->_left的别名}else//被删除结点有两个孩子{Node* minRight = root->_right;//找右子树的最左——最小while (minRight->_left){minRight = minRight->_left;}//让被删除结点跟最小值交换swap(root->_key, minRight->_key);// 交换完右子树还是一颗二叉排序树// 转换成在子树中去删除节点return _EraseR(root->_right, key);}delete del;return true;}
}

完整代码K模型和KV模型代码链接

3 二叉搜索树的应用(K模型、KV模型)

  1. K模型:K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值。比如:给一个单词word,判断该单词是否拼写正确,具体方式如下:
  • 以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树
  • 在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误。
  1. KV模型:每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方式在现实生活中非常常见:
  • 比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英文单词与其对应的中文<word, chinese>就构成一种键值对;
  • 再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出现次数就是<word, count>就构成一种键值对。

4 二叉搜索树的性能分析

插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。
但对于同一个关键码集合,如果各关键码插入的次序不同,可能得到不同结构的二叉搜索树:
在这里插入图片描述
最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其平均比较次数为:log2Nlog_2 Nlog2N
最差情况下,二叉搜索树退化为单支树(或者类似单支),其平均比较次数为:N{N}N

相关文章:

C++——二叉树排序树

文章目录1 二叉搜索树概念2 二叉搜索树操作与模拟实现2.1 二叉搜索树的查找非递归版本递归版本2.2 二叉搜索树的插入非递归版本递归版本2.3 二叉搜索树的删除非递归版本递归版本3 二叉搜索树的应用&#xff08;K模型、KV模型&#xff09;4 二叉搜索树的性能分析1 二叉搜索树概念…...

深拷贝浅拷贝的区别?如何实现一个深拷贝?

一、数据类型存储 JavaScript中存在两大数据类型&#xff1a; 基本类型 Number String null Undefined Boolean symbol引用类型 array object function 基本类型数据保存在在栈内存中 引用类型数据保存在堆内存中&#xff0c;引用数据类型的变量是一个指向堆内存中实际对象的…...

Linux应用编程下连接本地数据库进行增删改查系列操作

文章目录前言一、常用SQL操作语句二、相关函数解析三、连接本地数据库四、编译运行五、程序源码前言 本篇为C语言应用编程下连接Linux本地数据库进行增删改查系列操作。 在此之前&#xff0c;首先当然是你需要具备一定的数据库基础&#xff0c;所以下面我先列出部分常用的SQL…...

图论学习03

图神经网络模型介绍 将图神经网络分为基于谱域上的模型和基于空域上的模型&#xff0c;并按照发展顺序详解每个类别中的重要模型。 基于谱域的图神经网络 谱域上的图卷积在图学习迈向深度学习的发展历程上起到了关键性的作用。三个具有代表性的谱域图神经网络 谱图卷积网络切…...

解决qt中cmake单独存放 .ui, .cpp, .h文件

设想 项目文件较多&#xff0c;全部放在一个目录下就像依托答辩。 希望能将头文件放入include&#xff0c;ui文件放入ui&#xff0c;源文件放入src。 为了将Qt代码和一般非Qt代码分离开&#xff0c;进一步地&#xff1a; 将Qt源文件放入qt_src&#xff0c;普通源文件放入sr…...

操作系统(day12)-- 基本分段存储,段页式存储

基本分段存储管理方式 不会产生内部碎片&#xff0c;会产生外部碎片 分段 按照程序自身的逻辑关系划分为 若干个段&#xff0c;每个段都有一个段名&#xff0c;每段从0开始编址 分段存储管理方式中一个段表项由段号&#xff08;隐含&#xff09;、段长、基地址 分段的段表项固…...

疯狂弹出请插入多卷集的最后一张磁盘窗口

整个人嘛了&#xff0c;今天插上U盘&#xff0c;跟tmd中了病毒一样&#xff0c; 屏幕疯狂弹出窗口&#xff0c; 提示请插入多卷集的最后一张磁盘&#xff01; 点确定之后他继续弹出&#xff0c;点取消它也继续弹出&#xff0c; 关掉一个又弹出来一个&#xff0c;妈的&#x…...

Spark12: SparkSQL入门

一、SparkSQL Spark SQL和我们之前讲Hive的时候说的hive on spark是不一样的。hive on spark是表示把底层的mapreduce引擎替换为spark引擎。而Spark SQL是Spark自己实现的一套SQL处理引擎。Spark SQL是Spark中的一个模块&#xff0c;主要用于进行结构化数据的处理。它提供的最核…...

show profile和trance分析SQL

目录 一.show profile分析SQL 二.trance分析优化器执行计划 一.show profile分析SQL Mysql从5.0.37版本开始增加了对show profiles和show profile语句的支持。show profiles能够在做SQL优化时帮助我们了解时间都耗费到哪里去了。。 通过have_profiling参数&#xff0c;能够…...

[AI生成图片] 效果最好的Midjourney 的介绍和使用

Midjourney介绍&#xff1a; 是一个文本生成图片的扩散模型&#xff0c;能够根据输入的任何文本生成令人难以置信的图像&#xff0c;让数十亿人在几秒钟内创造惊人的艺术。为方便用户控制和快速生成图片&#xff0c;打开后在页面底部输入文本内容&#xff0c;稍等一小会&#…...

Vue.use( ) 的核心原理

首先来思考几个问题&#xff1a; Vue.use是什么&#xff1f; vue.use() 是vue提供的一个静态方法&#xff0c;主要是为了注册插件&#xff0c;增加vue的功能。 Vue.use( plugin ) plugin只能是Object 或 Function vue.use()做了什么工作&#xff1f; 该js如果是对象 该对象…...

idea同时编辑多行-winmac都支持

1背景介绍 idea编辑器非常强大&#xff0c;其中一个功能非常优秀&#xff0c;很多程序员也非常喜欢用。这个功能能够大大大提高工作效率-------------多行代码同时编辑 2win 2.1方法1 按住alt鼠标左键上/下拖动即可 这样选中多行后&#xff0c;可以直接多行编辑。 优点&a…...

亿级高并发电商项目-- 实战篇 --万达商城项目 十一(编写商品搜索功能、操作商品同步到ES、安装RabbitMQ与Erlang,配置监听队列与消息队列)

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是小童&#xff0c;Java开发工程师&#xff0c;CSDN博客博主&#xff0c;Java领域新星创作者 &#x1f4d5;系列专栏&#xff1a;前端、Java、Java中间件大全、微信小程序、微信支付、若依框架、Spring全家桶 &#x1f4…...

数据结构概述和稀疏数组

数据结构和算法内容介绍 1&#xff09;算法是程序的灵魂&#xff0c;优秀的程序可以在海量数据计算时&#xff0c;仍然保持高速计算 数据结构和算法概述 1&#xff09;程序 数据结构算法 2&#xff09;学好数据结构可以编写出更加漂亮&#xff0c;更加有效率的代码 3&…...

宝塔搭建实战人才求职管理系统adminm前端vue源码(三)

大家好啊&#xff0c;我是测评君&#xff0c;欢迎来到web测评。 上一期给大家分享骑士cms后台admin前端vue在本地运行打包、宝塔发布部署的方式&#xff0c;本期给大家分享&#xff0c;后台adminm移动端后台vue前端怎么在本地运行&#xff0c;打包&#xff0c;实现线上功能更新…...

服务器是干什么用的?

首先&#xff0c;什么是服务器&#xff1f;服务器是提供计算服务器和网络服务的设备。服务器和计算机由CPU、硬盘、内存、系统总线等组成。比如我们访问一个网站&#xff0c;点击这个网站会发出访问请求&#xff0c;服务器会响应服务请求&#xff0c;进行相应的处理&#xff0c…...

C++ 之结构体与共用体

文章目录参考描述结构体使用&#xff08;基本&#xff09;声明初始化先创建后初始化C 11 列表初始化使用&#xff08;进阶&#xff09;结构数组声明&#xff08;拓展&#xff09;声明及创建声明及初始化匿名结构体细节外部声明与内部声明成员赋值共用体存储空间匿名共用体同化尾…...

Java基础知识汇总(良心总结)

1. 前言 本文章是对Java基础知识进行了汇总&#xff0c;方便大家学习。 申明&#xff1a;文章的内容均来自黑马程序员&#xff0c;博主只是将其搬到了CSDN上以共享给大家学习 2. 目录 Day01 Java学习笔记之《开章》 Day02 Java学习笔记之《运算符》 Day03 Java学习笔记之《流程…...

InnoDB之Undo log格式

1. 前言 InnoDB有两大日志模块&#xff0c;分别是redo log和undo log。为了避免磁盘随机写&#xff0c;InnoDB设计了redo log&#xff0c;数据写入时只写缓冲页和redo log&#xff0c;脏页由后台线程异步刷盘&#xff0c;哪怕系统崩溃也能根据redo log恢复数据。但是我们漏了一…...

一问学习StreamAPI终端操作

Java Stream管道流是用于简化集合类元素处理的java API。 在使用的过程中分为三个阶段&#xff1a; 将集合、数组、或行文本文件转换为java Stream管道流管道流式数据处理操作&#xff0c;处理管道中的每一个元素。上一个管道中的输出元素作为下一个管道的输入元素。管道流结果…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

Sklearn 机器学习 缺失值处理 获取填充失值的统计值

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...